【ABC195】E - Lucky 7 Battle - メモ帳がわり

ゲーム系の問題でDPをするときはメモ化再帰の方が書きやすい気がする。

解法

$ S_i $か0かの選択をする際に、その選択をした結果7の倍数を作れるor作れないことが分かれば、常に最適な行動を取れる。
ということで、前の桁から$ S_i $か0かの選択をした未来で7の倍数を作れるかどうかを再帰的に検証していくことにする。

メモ化再帰

ただ、愚直に全探索しようとするとO(2^N)になるため、間に合わない。
ここでDPの考え方を用いる。

再帰的に次の桁を呼び出すとき必要になる情報は、今何桁目で決定している合計値(mod 7)がいくつかという2つである。
この2つの情報を状態として持つDPテーブルを作成しメモ化すれば、何度も同じ計算をする事態を避けることができる。

どう検証するか

メモ化再帰の定義は次のようになる。
rec(i, cur) ← 前からi桁目までの選択が確定している場合に、確定している値を7で割った値がcurであるときに7の倍数を作れるか

rec(i, cur)は7の倍数を作れるときtrueを返し、作れないときfalseを返すようにする。

次の桁に遷移するときは次のように2つに分かれる。

rec(i+1, (cur + S[i]) mod 7) ← i桁目でS[i]を選択したとき
rec(i+1, cur) ← i桁目で0を選択したとき

i桁目の時点で青木くんのターンであった場合、7の倍数を作ることができない未来を2つの遷移先から選択すればよく、逆に高橋くんのターンであった場合、7の倍数を作ることができる未来を選べばよい。

実装

rec(i+1, (cur + S[i]) mod 7) と rec(i+1, cur)の戻り値を、それぞれflag1、flag2とする。

青木君のターンには、なるべくfalseを戻り値としたい。
7の倍数を作れない未来を選択できるのは、flag1 = true, flag2 = trueのパターン以外のときなので、flag1とflag2の論理積をとったとき、trueである場合のみ7の倍数を作らざるを得ないことになる。
よって、青木君のターンにはflag1 && flag2を戻り値とする。

逆に高橋君のターンでは、なるべくtrueを戻り値にしたい。
7の倍数を作れる未来を選択できるのは、flag1とflag2のどちらかがtrueの時なので、高橋君のターンにはflag1 || flag2を戻り値とする。

// mint: mod 7 のmodint構造体

int N;
string S, X;
bool rec(int i, int cur, vector<vector<int>> &memo) {
    if (i == 0) {
        if (cur) return 0; // curが0以外であるとき
        else return 1; // cur=0のとき
    }

    if (memo[i-1][cur] != -1) return memo[i-1][cur];

    mint nx = modpow((mint)10, i) * (S[N-i] - '0') + cur;
    // S[i]を選択する場合
    bool flag1 = rec(i-1, nx.val, memo);
    // 0を選択する場合
    bool flag2 = rec(i-1, cur, memo);

    // 青木君のターンのとき、7の倍数を作れない未来を選択する
    if (X[N-i] == 'A') return memo[i-1][cur] = flag1 && flag2;
    // 高橋君のターンのとき、7の倍数を作れる未来を選択する
    else return memo[i-1][cur] = flag1 || flag2;
}

void solve(){
    vector<vector<int>> memo(N+1, vector<int>(7, -1));

    if (rec(N, 0, memo)) c("Takahashi")
    else c("Aoki")
}

int main(){
    cin >> N >> S >> X;
    solve();
    return 0;
}```