[AtCoder] ABC135 D – Digits Parade (400点)

2020年1月17日AtCoder剰余, 動的計画法, 400点, 数字の文字列, 桁ごと

問題へのリンク

問題

一部が ? で与えられる数字の文字列 S について、13で割って5余る数で考えられる物は何通りあるか。
答えを 1e9+7 で割った余りで答えよ。

制約

  • \(1 \leq |S| \leq 10^5\)

考え方

まずは単純に全探索することを考えて見ます。10の「?の数」乗 通りの数が考えられるので、それぞれに対して13で割って5余る数かを確かめていると、制限時間内に計算を終了することができません。

そこで、何らかの高速化が必要になります。今回のように、文字列で入力が与えられるような非常に桁数が大きい問題は「桁ごとに考える」とうまくいく場合があります。

1桁目から順に、何通りあるのかを考えていきます。

dp[i][j] := i 桁までの数として考えられる物のうち、余りが j となるのは何通りか

とすると、実は動的計画法で計算できることに気が付きます。配列の大きさは最大でも \(10^5 \times 13\) となるので、十分計算できる大きさです。

なぜ13で割るのか(なぜ13でなければならないのか)を考えてみると、動的計画法に気が付きやすいかもしれません。これが更に大きい値だと配列を確保できない場合があるからです。

解法

dp[i][k] := i 桁までの数として考えられる物のうち、余りが kとなるのは何通りか

として、動的計画法により更新していきます。( i は 0 始まり)

S[i]が ? でない時(数字 j の時)は、0桁目からi-1桁目までの数が決まっているとすると、\( j \cdot 10 ^ i\) だけ数が増加することになります。

つまり、元の数を13で割った余りを k とすると、余りは\(( k + j \cdot 10 ^ i )\%13\)になるはずです。

i-1桁目までの数で余りが k だったものは、全て余り\(( k + j \cdot 10 ^ i )\%13\)になるので、以下のように更新すれば良いことになります。

dp[i][\(( k + j \cdot 10 ^ i )\%13\)] += dp[i-1][k]

S[i]が ? の時は、j を0から9までに変化させて同様の更新を行えば良いです。

ソースコード