はまやんはまやんはまやん

hamayanhamayan's blog

Interval Game 2 [AtCoder Beginner Contest 206(Sponsored by Panasonic) F]

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