AtCoder ABC 206 F - Interval Game 2 (黄色, 600 点)

Grundy 数は Grundy 数でも、「山を分割していく」というタイプの Grundy 数ですね。

• 問題へのリンク

問題概要

個の区間が与えられる。 個目の区間は となっている。

Alice と Bob は次のようなゲームを行う。

まだ残っている区間のうち、「今までに選ばれたどの区間とも共有点をもたない」ものを交互に選んでいく。先に区間を選べなくなった方が負けである。

双方最善を尽くしたとき、どちらが勝つか？

(マルチテストケース： 回)

制約

• 
• 

考えたこと

という小さく見える制約に意味があるのかな...というのを最初思った。その後、 という制約もあるから座圧すれば実質意味ない制約なのかな... となった。でもコンテスト的には座圧しなくてもいいのは楽だね。

それはそうと、いわゆる区間スケジューリング問題のような設定でゲームをする！！！今までありそうでなかった面白い問題だね！！！

こういう「山とか盤面とかが分割されて行くようなゲーム」は、Grundy 数と相場は決まっている！！！

盤面が分割していくゲーム

初期状態だとゲームの盤面は、[0, 100) という状態になっている (区間の座標を 0-indexed にする)。

ここからたとえば 個の区間の中に [10, 20) があったと仮定して、これを選ぶと、盤面は

• [0, 10)
• [20, 100)

という具合に分割される。ここで、盤面を の範囲に制限したときの Grundy æ•°ã‚’ G[l][r] と書くことにしよう。このとき、このように「盤面全体が 2 つに分割された状態の局面」の Grundy 数は

G[0][10] ^ G[20][100]

になることが知られている。よって、 個の区間 それぞれに対して、

• G[0][l[0]] ^ G[r[0]][100]
• G[0][l[1]] ^ G[r[1]][100]
• ...
• G[0][l[N-1]] ^ G[r[N-1]][100]

の mex を求めれば OK。

メモ化再帰へ

以上のことを再帰的に行えば OK。区間 に関する Grundy 数をメモ化しながら、G[0][100] を求めよう。

計算量は として、 となる。

#include <bits/stdc++.h>
using namespace std;

int MAX = 110;
int N;
vector<int> L, R;
vector<vector<int>> dp;

int solve(int left = 0, int right = MAX) {
    if (right == left) return 0;
    if (dp[left][right] != -1) return dp[left][right];

    set<int> se;
    for (int i = 0; i < N; ++i) {
        if (left <= L[i] && R[i] <= right) {
            int tmp = solve(left, L[i]) ^ solve(R[i], right);
            se.insert(tmp);
        }
    }

    int grundy = 0;
    while (se.count(grundy)) ++grundy;
    return dp[left][right] = grundy;
}

int main() {
    int NUM_CASE;
    cin >> NUM_CASE;

    while (NUM_CASE--) {
        cin >> N;
        L.resize(N), R.resize(N);
        for (int i = 0; i < N; ++i) {
            cin >> L[i] >> R[i];
            --L[i], --R[i];
        }
        dp.assign(MAX, vector<int>(MAX+1, -1));
        cout << (solve() > 0 ? "Alice" : "Bob") << endl;
    }
}