Magicode logo
Magicode
0
5 min read

非解説 ABC263 E-Sugoroku3(diff:1659)

https://cdn.apollon.ai/media/notebox/64f1580c-6bba-4027-a7ff-bf02428f15a9.jpeg

ABC263 E-Sugoroku3 (difficulty:1659)

[期待値DP,サイコロの出目0があり]
やぁ。瑞々しぃにぼしだよ
今日はね、リアルタイムコンテスト後でもなんでもないけど、解けるかどうか分からない状態で記事を書き始めました。
解説は読んだんだけど、コードは読んでいない状態で、解けそうになったので書いてみることにします。
この問題は、公式動画解説(すぬけさんのやつ)がまだなくて、解説を読んでもうーんうーん…期待値DP…???って感じで難しいな、って思っている問題です
記事を書きながら解きます。頑張ります。

前提知識

前提知識というのもおこがましいですが、僕は今回の問題を理解するために、Sugoroku2(diff2154)を頑張って解けるようになりました。
正確には、解説を理解しました。
  • 青Diffを解くために黄diffを理解するって頭狂ってるだろ

解くぞー

  • 問題文
      • N個のマス目があります。Nマス目以上に行けばゴールです
      • 1マス目からN-1マス目までについて、各マスにさいころが置いてありますが、それらのサイコロN個は、マスによって出目が違います
      • iマス目においてあるさいころは、0以上AiA_i 以下の整数を等確率で出すさいころです
      • ゴールするまでに振るさいころの回数の期待値mod998244353を求めてください
  • 思ったこと
    • 出目0のサイコロ…???????????????????????????
    • 期待値のmodってなんだよ…
わけがわかりません。この問題を見た段階では期待値DPを解いたことが無いのですが、『スゴロクの問題はゴールからスタートに向けてDP』みたいなのが常識だったような気がします。しかし、出目が0…わけが分からない。
ちなみにこの回のABCは2完でめちゃくちゃ腹が立った。まあ分からないので解説を読んだり、『Sugoroku2』を頑張って理解してきました。そのうえで学んだことは、
  • DP[i]DP[i]を求めるためには、DP[i+0],DP[i+1],...,DP[i+Ai]DP[i+0],DP[i+1],...,DP[i+A_i]が必要ということで、DP[i]DP[i]を求めるためにDP[i+0](=DP[i])DP[i+0](=DP[i])が必要というわけの分からないことが発生している
    • しかし、式変形をすることで、DP[i]=(DP[i]が現れない式)DP[i] = (DP[i]が現れない式)に変形できる
    • (ここは、公式解説Nyaanさんがおすすめです。是非読んで、手を動かすといいと思う)
そして、思ったことは
  • mod998244353と書いてあるが、ACLのmodintを使えばできそう?(逆元とかはなんかmodintが勝手にうまいことしてくれるんじゃないか?)(ってりゅうきフォロワーが言ってた)
  • 解説に『セグ木』とか『累積和』って言葉が出てきて難しそう…何に使うんだろう
こんな感じです。
ってことで、現状で書けそうな範囲で、コーディングをしていきたいとおもう。
  • コーディングするぞ。って思った段階で、どうせだし気持ちたれ流し記事かくかって思い立った。
この段階での気づき
  • そういえば、DP[i]=(DP[i+1]+DP[i+2]+...+DP[i]+Ai)みたいな式DP[i] = (DP[i+1]+DP[i+2]+...+DP[i]+A_i)みたいな式になって、AiA_iがiによって異なるから、そこを楽に求めるために累積和とかを使うんだなって気づいた。

コーディングver1

  • 累積和の配列を作るんだけど、普段と累積の順番が逆(❓)だから、だるそう…
mint dp[400'005];
int main()
{
	int n;
	cin >> n;
	vector<int> A(n+1);
	rep(i,n-1) cin >> A[i+1];
	vector<mint> sums(2*n+500,0); // 累積和 sums[i]は、dp[i]を含む
	for(int i = n-1; i >= 1; i--){
		// dp[i] = (sigma(dp[i+j]) / A_i) + 1/A_i + 1
		// 1 <= j <= A_i
		mint sigma = dp[i+1] - dp[i+A[i]+1]; // ☆
		dp[i] = sigma / mint(A[i]) + 1 / mint(A[i]) + 1;
		sums[i] = sums[i+1] + dp[i];
	}
	cout << dp[1].val() << endl;
}
こんな感じかな?(提出コード)
  • さすがに通らない。甘くない(サンプルすら通ってません)
  • サンプル2の出力が 166374061でした。2倍したらサンプル合います。何だこりゃ
なんか、惜しいところまで来てるんじゃね?って気がします。
よく見ると、
mint sigma = dp[i+1] - dp[i+A[i]+1];
こいつが間違ってますね。
mint sigma = sums[i+1] - sums[i+A[i]+1];
です。
  • ちなみに、sigmaを求めるときの、累積和(sums)の添え字ごねごねは、図に書いてどうにかこうにか乗り切りましょうね♡
    • ちょっとだけいうと、dp[i]を求めるときは、dp[i+1]までを含んだもの累積和が欲しくて、これはsums[i+1]に含まれています。
    • さらに言うと、dp[i]を求めるときは、dp[i+A[i]]を含めた累積和が欲しいので、dp[i+A[i]+1]dp[i+A[i]+1] は不要です。
      • dp[i+A[i]+1]の結果が含まれた累積和は、sums[i+A[i]+1]です
    • ってことで、sigmaはsums[i+1]sums[i+A[i]+1]sums[i+1] - sums[i+A[i]+1]

コーディングver2

  • ということで、sigmaを直してサンプルを試す 
int main()
{
	int n;
	cin >> n;
	vector<int> A(n+1);
	rep(i,n-1) cin >> A[i+1];
	vector<mint> sums(2*n+500,0); // 累積和 sums[i]は、dp[i]を含む
	for(int i = n-1; i >= 1; i--){
		// dp[i] = (sigma(dp[i+j]) / A_i) + 1/A_i + 1
		// 1 <= j <= A_i
		mint sigma = sums[i+1] - sums[i+A[i]+1];
		dp[i] = (sigma / mint(A[i])) + (1 / mint(A[i])) + 1;
		sums[i] = sums[i+1] + dp[i];
	}
	cout << dp[1].val() << endl;
}
  • サンプル合う
  • 投げる
  • WJ…
  • AC
ACしました
天才かもしれません…

これから期待値DP入門する方へのアドバイス

  • 自分も期待値DP2問目だし、解いてから1週間も経ってないけど、何か言います
  • 出目0は、数式変形をしたらなんかいい感じになる
  • 振り出しに戻る場合は、DP[0]を予め定義しておいて、ごねごねしたら行ける(難しいけど)
  • とりあえず、基本はdp[i]=(dp[i+1]+...+dp[i+出目の最大値]を含んだ式)+1dp[i] = (dp[i+1] + ... + dp[i+出目の最大値]を含んだ式) + 1みたいなノリ
  • 後は気合
個人的には
  • 期待値DP難しすぎる(青diff, 黄diff)

感想

ACできたんで記事終わります。
解説も何もしていないような気がしますが、まあええやろ。
そういえば今週は大学の研究室が休みなのですが、いろいろとやらなきゃいけないことがたまっています。期待値DPしている場合ではありません。
  • ACLのmodint使ったら勝手にうまいこと言って草
    • 逆元履修しなくていいや
  • 累積和もいつもと向きが逆だけどやってみたらできた

最後に

水色コーダーをボコボコにするABCやめてください。

Discussion

コメントにはログインが必要です。