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