けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

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

問題概要

 N 個の区間が与えられる。 i 個目の区間は  \lbrack L_{i}, R_{i}) となっている。

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

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

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

(マルチテストケース: T 回)

制約

  •  1 \le T \le 20
  •  1 \le N \le L_{i}, R_{i} \le 100

考えたこと

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

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

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

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

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

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

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

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

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

になることが知られている。よって、 N 個の区間  \lbrack l_{i}, r_{i}) それぞれに対して、

  • 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。区間  \lbrack a, b) に関する Grundy 数をメモ化しながら、G[0][100] を求めよう。

計算量は  A = 100 として、 O(A^{2}N) となる。

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