Lucky 7 Battle [パナソニックプログラミングコンテスト（AtCoder Beginner Contest 195） E]

https://atcoder.jp/contests/abc195/tasks/abc195_e

前提知識

• バックトラック

解説

https://atcoder.jp/contests/abc195/submissions/20908954 ゲーム問題には解法は多くないが、今回はその中でバックトラックを使った方法で解く。

状態の圧縮

ゲーム問題の解法でどれが使えるかなーというのを考えつつ、問題をよりコンパクトにできないか考える。
手順はどうあれ、勝つかどうかは数が7の倍数かどうかで決まる。
ということは過程はどうあれゲームの状態はその数を7で割った余りで表現できることになる。

iラウンドまで操作が確定しているときに、これまで確定している数を7で割った余りがmoである状態
この状態はこれまでの操作がどういった操作かどうかというのが今後の操作に影響しない。
つまりすべての状態は、(i,mo)の組、210⁵7通りに限定することができるということになる。
これは全部考慮できる状態である。

バックトラック

バックトラックというのは、とある状態の遷移先の勝敗がすべて確定していれば、
自分にとって有利な選択をすることで、とある状態の勝敗を確定させることができるというテク。
終端状態から逆向きに勝敗が確定していくので、バックトラックみたいな言い方だと思ってる。

今回の終端状態は(N,0)～(N,6)である。
ここから逆算して、考えていってもいいが、自分はメモ化再帰でやっていくのが好きなので、それでやってる。

メモ化再帰

メモ化再帰の詳細は説明しないが、プログラミングに慣れてる人向けにはキャッシュをすると言い換えることもできる。

f(i, mo) := i回目の操作が確定していて、確定している数を7で割った余りがmoの状態が「高橋君の勝ち」状態であるか

これを再帰で求めていく。
f(i, mo)を求めるときに、遷移先の状態である

• f(i+1, mo') …S[i]を加えたとき
• f(i+1, mo) …0を加えたとき

の選択肢があるが、青木君のターンであれば高橋君が負ける状態が1つでもあれば勝ちだし、
高橋君のターンであれば青木君が負ける状態が1つでもあれば勝ち。
これを遷移先の状態とどちらのターンかを元に判定する。

引数をkeyとしてメモ化を行っておくことで、状態数分の計算だけでよくなるので間に合う。

int N; string S, X;
//---------------------------------------------------------------------------------------------------
int p[201010];
bool cache[201010][7];
bool vis[201010][7];
bool f(int i, int mo) {
    if (i == N) return mo == 0;

    if (vis[i][mo]) return cache[i][mo];
    vis[i][mo] = true;


    if (X[i] == 'T') {
        // add S[i]
        if (f(i + 1, (mo + (S[i] - '0') * p[N - i]) % 7)) return cache[i][mo] = true;

        // add 0
        if (f(i + 1, mo)) return cache[i][mo] = true;

        return cache[i][mo] = false;
    }
    else {
        // add S[i]
        if (!f(i + 1, (mo + (S[i] - '0') * p[N - i]) % 7)) return cache[i][mo] = false;

        // add 0
        if (!f(i + 1, mo)) return cache[i][mo] = false;

        return cache[i][mo] = true;
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S >> X;

    p[0] = 1;
    rep(i, 1, 201010) p[i] = (p[i - 1] * 10) % 7;

    cout << (f(0, 0) ? "Takahashi" : "Aoki") << endl;
}