LeftToRightGame [2018 TCO Algorithm Round 3A Div1 Easy]

http://community.topcoder.com/stat?c=problem_statement&pm=14950

length桁の数を2人で作る。
Aさんが上位1桁目を決めて、Bさんが上位2桁目を決めて…と順番に数を決めていく。
上位1桁目だけ1～9の数である必要がある。
両者が最適に数を決めてAさんはdivisorの倍数でない、Bさんはdivisorの倍数であるように目指す。
どちらが勝つか。

前提知識

• 後退解析

解法

後退解析をメモ化再帰で解く。
f(cu,mo) := 上位cu桁が確定していて、これまでの数%divisor=moである場合の勝敗
後退解析をするので、遷移先に負け状態が含まれるなら勝ち状態にする。

int N, D;
int memo[1010][1210];
int f(int cu, int mo) {
    if (0 <= memo[cu][mo]) return memo[cu][mo];

    int p = cu % 2;

    if (cu == N) {
        if (p == 0 and mo != 0) return memo[cu][mo] = 1;
        if (p == 1 and mo == 0) return memo[cu][mo] = 1;
        return memo[cu][mo] = 0;
    }

    int lose = 0;
    rep(d, 0, 10) {
        if (cu == 0 and d == 0) continue;
        if (!f(cu + 1, (mo * 10 + d) % D)) lose = 1;
    }
    if (lose) return memo[cu][mo] = 1;
    return memo[cu][mo] = 0;
}
struct LeftToRightGame {
    string bob = "Bob";
    string alice = "Alice";
    string whoWins(int length, int divisor) {
        N = length;
        D = divisor;

        rep(cu, 0, N + 1) rep(mo, 0, D) memo[cu][mo] = -1;
        if (f(0, 0)) return alice;
        return bob;
    }
};