https://atcoder.jp/contests/abc206/tasks/abc206_f
前提知識
解説
https://atcoder.jp/contests/abc206/submissions/23623437
今回の問題はgrundy数を知らないとまず解けない。
解説範囲がとても広くなってしまうので、grundy数についてはどこかで勉強してきてほしい。
だが、一応簡単に以下に説明する。
grundy数
エッセンスだけ記載するが、理由も含めて他で学習してくるべきなので、調べて勉強してくるのがオススメ。
grundy数というのを各状態に対して計算を行う。
計算ルールとしては、
- 状態xに対するgrundy(x)は状態xから遷移可能な状態yに対するgrundy(y)のいずれにも含まれない0以上の最小の整数値
- 状態xと状態yが完全に独立した状態である場合に状態xと状態yをまとめたgrundy(x∧y)はgrundy(x) xor grundy(y)になる
な感じ。最終的にgrundy数が0の状態が負け状態になり、それ以外は勝ち状態である。
今回は、この「状態」を適切に決定することでgrundy数の計算に持ち込むことができ、勝敗を判定できる。
状態
端的には以下のようにする。
grundy(l,r) := 区間[l,r)がまだ選択可能な時のgrundy数
区間の範囲は[1,100)なので、grundy(1, 100)が0なら負け状態なのでBobの勝ち、それ以外ならAliceの勝ちとなる。
遷移
grundy数の計算では、遷移を意識する必要がある。
例えば、grundy(1,100)からの遷移を考えてみよう。
この場合は何も選択されてないということなので、N個の選択可能な区間がある。
例えば[4,6)を選択したとしよう。すると、選択後には区間は2つに分割される。
具体的には[1,4)と[6,100)に分割される。
この2つの区間は今後は独立に操作されることになる。
なので、grundy([1,4)∧[6,100))はgrundy([1,4)) xor grundy([6,100))として考えることができる。
ちょっと複雑な感じになったのでまとめると、
grundy(1,100)から区間[4,6)を選択した後のgrundy数はgrundy([1,4)) xor grundy([6,100))となる。
このようにあるgrundy(x,y)を計算するときは、さらに小さい区間のgrundy(x',y')の結果のみが必要となるので、
再帰的に、もしくは、区間DPのように計算を進めていくことでgrundy(1,100)を計算することができる。
後は0かそうでないかを判定するだけ。
int N, L[101], R[101]; //--------------------------------------------------------------------------------------------------- bool vis[101][101]; int memo[101][101]; int grundy(int l, int r) { if (vis[l][r]) return memo[l][r]; vis[l][r] = true; set<int> gs; rep(i, 0, N) if (l <= L[i] && R[i] <= r) gs.insert(grundy(l, L[i]) ^ grundy(R[i], r)); int g = 0; while (gs.count(g)) g++; return memo[l][r] = g; } //--------------------------------------------------------------------------------------------------- void solve() { cin >> N; rep(i, 0, N) cin >> L[i] >> R[i]; rep(l, 0, 101) rep(r, 0, 101) vis[l][r] = false; if (grundy(1, 100) == 0) cout << "Bob" << endl; else cout << "Alice" << endl; } //--------------------------------------------------------------------------------------------------- void _main() { int T; cin >> T; rep(t, 0, T) solve(); }