https://atcoder.jp/contests/abc195/submissions/21508217
- 初期値は dp[N][0]=1
- 繰り返しは repr(i, N - 1, -1) rep(j, 0, 7)
- 更新は if (X[i] == 'T') dp[i][j] = dp[i + 1][j] || dp[i + 1][(j + CtoL(S[i]) * NT_NyaaMod::Pow(10, N - 1 - i, 7)) % 7]; など
- 最終目標は if (dp[0][0] == 1) output("Takahashi");
大前提として「ゲームは後ろから見る」が典型知識となる。また、桁DPとして見れば類題として ABC135D を思い出すが、DP漸化式が特殊で難しいので注意。 ABC135D のような感覚で自然に？漸化式を考えると DP[i-1][j + S[i] * pow % 7] = dp[i][j] のようにしたくなるが、少し工夫して以下のように定義する（理由は…謎…）。
DP[i][j] := i桁目の数字を適用する前でのmodがjでS[i]を適用するとdp[i+1][j+nyaa]に遷移する状態で、勝ちなら1、負けなら0
Tなら貪欲に 1 にしたくて、Aなら貪欲に 0 にしたい。TならOR演算、AならAND演算、を使うとシンプルに実装できる。
詳しく説明すると、X=T なら dp[i][j] の状態から i 桁目の数字として 0 または S[i] を適用した遷移先 dp[i+1] に 1 が存在すれば、その数字を採用することで dp[i][j] = 1 に出来る。 X=A なら dp[i][j] の状態から i 桁目の数字として 0 または S[i] を適用したときに遷移先 dp[i+1] で 0 が存在すれば、その数字を採用することで 0 にすることが出来る。Tなら遷移先に1個でも 1 があれば 1 に出来るし、Aなら遷移先が1個でも 0 なら 0 に出来るということで、よくよく考えると論理演算と同じ。
したがって、以下のような実装になる。
if (X[i] == 'T') dp[i][j] = dp[i + 1][j] || dp[i + 1][(j + S[i] * pow(10, N-1-i) % 7];
else dp[i][j] = dp[i + 1][j] && dp[i + 1][(j + S[i] * pow(10, N-1-i) % 7];
pow 関数は繰り返し二乗法で高速化した上で mod を取ること。1を分配していくことから dp[N][0]=1 として何も数字を採用していない状態 dp[0][0]=1 かどうかで判定をする。
