AtCoder Beginner Contest 135 D - 今日から始める競プロ日記
はじめに
AtCoder Beginner Contest ( ABC ) 135 に参加（2019/07/27）。
今回はCまで解いた。
DはDP（動的計画法）の典型問題らしかったけど分からんかった。
なので解説動画を見て自分なりにまとめてみる。
参考
AtCoder Beginner Contest 135 の公式解説動画。ありがたい。
結果
- パフォーマンス：882
- レート：683 → 706 (+23)
D - Digits Parade
数字（ 0 - 9 ）と ? からなる文字列 S が与えられる。
? は数字に置き換えることができる。
その文字列を整数とみなしたとき、13 で割って 5 余る数は何通りあるか数える問題。
答えは大きくなる可能性があるから10^9+7で割った余りを答える。
各桁ごとに余りを考える
文字列 S は最大で長さ10^5になるので、
何も考えずに全通りを 13 で割って余りが 5 になるかどうか数えると、
計算量は最大で10^(10^5)になるから時間内には解けない。
そのため解き方を工夫する必要がある。
そこで、各桁ごとに余りを考えていくことが大切。
例として274を13で割ったときの余りを考えてみる。
まず、274は1×4と10×7と100×2の3つに分解できる（これが各桁ごとに見るということ）。
この3つの値をそれぞれ13で割って余りを求める。
ここで求められた各桁の余りの和を求める。
5 + 5 + 4 = 14
この合計を13で割って余りを求めると、14 % 13 = 1で余りは1となる。
つまり、274を 13 で割ると余りは 1 ということになる。
? を含んでいる場合
例として?44について考える。
?44についても先ほどと同様に考えてみる。
上の図のように、?44を 13 で割ると、余り = 4 + 1 + ( ? × 9 )となる。
このとき、? に 0 ～ 9 を入れることで、全通りの余りを求めることができる。
余りの計算はこんな感じ。
4 + 1 + 0 = 5 → 5 4 + 1 + 9 = 14 → 1 4 + 1 + 18 = 23 → 10 4 + 1 + 27 = 32 → 6 4 + 1 + 36 = 41 → 2 4 + 1 + 45 = 50 → 11 4 + 1 + 54 = 59 → 7 4 + 1 + 63 = 68 → 3 4 + 1 + 72 = 77 → 12 4 + 1 + 81 = 86 → 8
このようにして、? を含んだ整数でも余りを求めることができる。
動的計画法（DP）を用いて解く
動的計画法を用いると効率よく計算を行うことができる。
さっき例としてあげた274 % 13は、
4 % 13 = 4 70 % 13 = 5 200 % 13 = 5
より、
4 + 5 + 5 = 14 14 % 13 = 1
という計算を行って、余りが 1 ということが分かった。
これを以下のように表で表す。
（この表では、0 + 4 + 5 + 5 = 14 → 1という計算が行われている。）
この表から分かる通り、一つ前の桁の余りの個数から、次の桁の余りの個数を計算して求めることができる。
一度計算した結果を記録していくことで、効率的に全通りの計算を行うことができる。
計算量のオーダーはおそらくO(N)のはず（違うかな？）。
? を含んだ整数のDP
先ほど例にあげた?44でも、このDPで計算してみる。
? がある場合、? に 0～9 を入れて10通りにおける余りの計算を行うことになる。
これは以下のように表で表す。
また、この余りの計算は余りの数分だけ行う（つまり 0 ～ 12 の 13回）。
コード
コードは公式の解説動画を参考にしました。
ありがとうございます。
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;
int main()
{
string S;
cin >> S;
// ( mod 13 )
const int N = 13;
//dp配列
vector<int64_t> dp(N);
// 0%13=0なので余り0の個数を1にする
dp[0] = 1;
//答えはこれで割った余りを出力
int64_t mod = 1e9+7;
//何の位かを表す（1の位、10の位、100の位、......）
int64_t mul = 1;
//文字列を一桁ずつ見ていく（1の位から見ていくよ）
for(int i = S.size()-1; i >= 0; i--)
{
//更新したdp配列
vector<int64_t> nextDP(N);
char c = S[i];
if(c == '?')
{
//'?'が0-9の場合をそれぞれ考えていく
for(int k = 0; k < 10; k++)
{
//各余りの個数を更新
for(int j = 0; j < N; j++)
{
//一つ前のdp配列のインデックス j から、
//次のdp配列のインデックスは K * mul 分だけずれる
//（上で説明した表の"+4"みたいなこと）
nextDP[(k * mul + j) % 13] += dp[j];
nextDP[(k * mul + j) % 13] %= mod;
}
}
}
else
{
//文字cをintに変換
int k = (int)(c - '0');
//各余りの個数を更新
for(int j = 0; j < N; j++)
{
//一つ前のdp配列のインデックス j から、
//次のdp配列のインデックスは K * mul 分だけずれる
//（上で説明した表の"+4"みたいなこと）
nextDP[(k * mul + j) % 13] += dp[j];
nextDP[(k * mul + j) % 13] %= mod;
}
}
//dp配列を更新
dp = nextDP;
//次の位に更新
mul *= 10;
//ここで余りをとっても結果は変わらない
mul %= N;
}
//余り5の個数を出力
cout << dp[5] << endl;
return 0;
}
おわりに
もっと簡単にスマートに説明できそう。
おそらく私が完璧に理解できていない。
