pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

yukicoder No.315 世界のなんとか3.5

問題文

http://yukicoder.me/problems/766

解法

制約からして桁DP。桁DPを知らない人用に「桁DP入門」という記事を書いた。むしろこっちがメインの記事。

pekempey.hatenablog.com

次のようなDPが思いつく。

dp[i][j][k][l][m]:=i桁目まで見ていてj,k,l,mであるような数の総数

・j: A未満であることが確定
・k: mod 3の値
・l: すでに3を選んでいる
・m: mod Pの値

しかしこれでは状態数がヤバイ。そこで次のようなmod Pの性質を使う。

  • 下3桁が8の倍数なら8の倍数になる
  • 下4桁が80の倍数なら80の倍数になる
  • 下5桁が800の倍数なら800の倍数になる
\[N=a_0+10 a_1+10^2a_2+10^3a_3\cdots\] と展開してmod 8を取ってみれば、 \[N \equiv a_0+10 a_1+10^2a_2\quad(\bmod 8)\] になる。つまり下3桁が8の倍数ならNも8の倍数。80,800の倍数の時も同様に正しいことが示せる。

よってN-6桁目ぐらいまでは、

dp[i][j][k][l]:=i桁目まで見ていてj,k,lであるような数の総数

・j: A未満であることが確定
・k: mod 3の値
・l: すでに3を選んでいる

というDPをして、N-6桁目以降は

dp2[i][j][k][l][m]:=i桁目まで見ていてj,k,l,mであるような数の総数

・j: A未満であることが確定
・k: mod 3の値
・l: すでに3を選んでいる
・m: mod Pの値

というDPをすればいい。そもそも6桁もない場合は愚直に計算するか、少しDPの処理を工夫する必要がある。

yukicoder No.315 世界のなんとか3.5

ひとこと

世界のなんとか3を解くときに下3桁だけ見ることは考えていたので、今回の問題はさほど頭使わずにできた。でもdpテーブルの0 fillし忘れてたのはダメ。