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

ABC263 E-Sugoroku3 (difficulty:1659)

前提知識

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

解くぞー

• 問題文

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

• 思ったこと
  • 出目０のサイコロ…？？？？？？？？？？？？？？？？？？？？？？？？？？？
  • 期待値のmodってなんだよ…

• $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;
}

• サンプル合う
• 投げる
• WJ…
• AC

• 提出コードはこちら

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

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

• 期待値DP難しすぎる（青diff, 黄diff)

感想

• ACLのmodint使ったら勝手にうまいこと言って草
  • 逆元履修しなくていいや
• 累積和もいつもと向きが逆だけどやってみたらできた

最後に