7K12 blog

猫でも分かるアルゴリズム解説

ABC135 D - Digits Parade

f:id:tkr987:20200731212519p:plain

https://atcoder.jp/contests/abc135/submissions/15552119

  • 桁DPで処理する
  • 初期値は dp[0][0] = 1
  • 繰り返しは rep(i, 1, Size(S))
  • 更新は if (S[i] == '?') rep(j, 0, 13) rep(k, 0, 10) dp[i][(j * 10 + k) % 13] += dp[i - 1][j] など
  • 出力は dp.back()[5]

f:id:tkr987:20200731225158p:plain
|S|が最大 10^5桁あるので桁DPで処理する。dp[i][m] := i桁目の剰余がmになる組み合わせの数とする。S[i] = s のとき、dp[i][(s + m) % 13] += dp[i-1][m] の遷移をして、i-1桁目の組み合わせ数をi桁目の組み合わせ数に加算していく処理をする。1桁前の情報を次の桁に活かせる理由は、割り算の筆算で考えると分かりやすい。

if (S[i] == '?')  rep(j, 0, 13) rep(k, 0, 10) dp[i][(j * 10 + k) % 13] += dp[i - 1][j];

else rep(j, 0, 13) dp[i][(j * 10 + CtoL(S[i])) % 13] += dp[i - 1][j];

S[i] = ? のとき、剰余の範囲[0, 13)とS[i]の範囲[0, 10)全て遷移する必要があるので、二重ループになることに注意する。Sの先頭にダミーの'0'を追加してdp[0][0] = 1で初期化すると実装が楽になる。計算量は O(10^2 |S|)になる。