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; } };