7K12 blog

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

E - Almost Everywhere Zero

f:id:tkr987:20200615234845p:plain

https://atcoder.jp/contests/abc154/submissions/14394556

  • 桁DPは状態 EQ (equal: 同値) と LT (less than: 未満) を持つのが定跡
  • 初期値は dp[0][0][state::EQ] = 1;
  • 繰り返しは rep(j, 1, Size(N)) rep(k, 0, K + 1)
  • 更新は if (k + 1 <= K) dp[j][k + 1][state::LT] += dp[j - 1][k][state::LT] * 9; など
  • 出力は dp.back()[K][state::EQ] + dp.back()[K][state::LT];

f:id:tkr987:20200616001801p:plain

dp[j][k][st] := 状態stにおけるj桁目までにk個[0, K]の0以外の数字を持つようなXの組み合わせ数 と定義し、各桁に対して下記のようなDP式で処理する。

  • stについて [st::EQ]から[st::LT]へと状態が変わるDP式
  • stについて [st::EQ]や[st::LT]のまま状態が変わらないDP式
  • kについて [k]から[k+1]になるDP式
  • kについて [k]のまま不変のDP式

細かい注意点として N[j] = 0 のとき X[j] < N[j] が存在しないので、N[j] = 0 と N[j] ≠ 0 で場合分けすると良いかと思う。また、Nの先頭にダミーを入れておくと実装が楽になると思う。