20か月前公開・20か月前更新・5 min read

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

AtCoder

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

ABC263 E-Sugoroku3 (difficulty:1659)

[期待値DP,サイコロの出目0があり]

やぁ。瑞々しぃにぼしだよ

今日はね、リアルタイムコンテスト後でもなんでもないけど、解けるかどうか分からない状態で記事を書き始めました。

解説は読んだんだけど、コードは読んでいない状態で、解けそうになったので書いてみることにします。

この問題は、公式動画解説（すぬけさんのやつ）がまだなくて、解説を読んでもうーんうーん…期待値DP…???って感じで難しいな、って思っている問題です

記事を書きながら解きます。頑張ります。

前提知識

前提知識というのもおこがましいですが、僕は今回の問題を理解するために、Sugoroku2(diff2154)を頑張って解けるようになりました。

正確には、解説を理解しました。

~~青Diffを解くために黄diffを理解するって頭狂ってるだろ~~

解くぞー

Sugoroku3

問題文
- - N個のマス目があります。Nマス目以上に行けばゴールです
  - 1マス目からN-1マス目までについて、各マスにさいころが置いてありますが、それらのサイコロN個は、マスによって出目が違います
  - iマス目においてあるさいころは、0以上 $A_i$ 以下の整数を等確率で出すさいころです
  - ゴールするまでに振るさいころの回数の期待値mod998244353を求めてください
思ったこと
- 出目０のサイコロ…？？？？？？？？？？？？？？？？？？？？？？？？？？？
- 期待値のmodってなんだよ…

わけがわかりません。この問題を見た段階では期待値DPを解いたことが無いのですが、『スゴロクの問題はゴールからスタートに向けてDP』みたいなのが常識だったような気がします。しかし、出目が0…わけが分からない。

ちなみにこの回のABCは2完でめちゃくちゃ腹が立った。まあ分からないので解説を読んだり、『Sugoroku2』を頑張って理解してきました。そのうえで学んだことは、

$DP[i]$ を求めるためには、 $DP[i+0],DP[i+1],...,DP[i+A_i]$ が必要ということで、 $DP[i]$ を求めるために $DP[i+0](=DP[i])$ が必要というわけの分からないことが発生している
- しかし、式変形をすることで、 $DP[i] = (DP[i]が現れない式)$ に変形できる
- （ここは、公式解説Nyaanさんがおすすめです。是非読んで、手を動かすといいと思う)

そして、思ったことは

mod998244353と書いてあるが、ACLのmodintを使えばできそう？（逆元とかはなんかmodintが勝手にうまいことしてくれるんじゃないか？)(って~~りゅうき~~フォロワーが言ってた)
解説に『セグ木』とか『累積和』って言葉が出てきて難しそう…何に使うんだろう

こんな感じです。

ってことで、現状で書けそうな範囲で、コーディングをしていきたいとおもう。

コーディングするぞ。って思った段階で、どうせだし気持ちたれ流し記事かくかって思い立った。

この段階での気づき

そういえば、 $DP[i] = (DP[i+1]+DP[i+2]+...+DP[i]+A_i)みたいな式$ になって、 $A_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;
}

こんな感じかな？(提出コード)

さすがに通らない。甘くない（サンプルすら通ってません)
サンプル２の出力が 166374061でした。２倍したらサンプル合います。何だこりゃ

なんか、惜しいところまで来てるんじゃね？って気がします。

よく見ると、

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]の結果が含まれた累積和は、sums[i+A[i]+1]です
- ってことで、sigmaは $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;
}