7K12 blog

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

EDPC S - Digit Sum

f:id:tkr987:20200522214124p:plain

https://atcoder.jp/contests/dp/submissions/11937787

  • 初期値は rep(j, 0, 10) if (j == CtoL(K[0])) dp[0][j % D][stEQ] += 1; など
  • K以下の整数全てとmod(D)全てで繰り返しは rep(i, 0, Size(K)) rep(j, 0, 10) rep(k, 0, D)
  • 状態は state::LT (less than), state::EQ(equal)
  • 出力は0を除くので dp[Size(K) - 1][0][EQ] + dp[Size(K) - 1][0][LT] - 1;

f:id:tkr987:20200522222200p:plain

dp[i][mod][state] := S[i]桁目までの合計がmod(D)で状態(LT, EQ)な個数、と定義する。

ただし、LTはless than(Kより小さい)、EQはequal(Kと等しい)とする。dp遷移の注意点として、i桁目がK[i]<S[i]だったとしても前の桁で既にT<Kの状態(state::LT)なら採用できる。ただし、S[i]は全ての桁を文字列として持つ必要がなく、一桁ぶんの情報で良いのでS[i]=jとする。jがK[i]と同じかK[i]未満かK[i]超過かで場合分けして、それぞれ状態(LT, EQ)の遷移を書く。初期値は0から9をmod(D)取ったとき同じ値になる可能性があるので=1としないで+=1することにも注意する。