問題文

\(T\) 個のテストケースについて、以下の問題を解いてください。

\(N\) 個の半開区間 \([ L_i,R_i)\ (1 \leq i\leq N)\) があり、 Alice と Bob がこの区間を使って次のようなゲームをします。

• Alice から始めて、以下の操作を交互に行う。
  • \(N\) 個の区間の中から、既に選ばれているどの区間とも共有点をもたない区間を \(1\) つ選ぶ。

先に操作を行えなくなった方が負けで、もう片方のプレイヤーが勝ちます。

双方のプレイヤーが勝利に対して最善を尽くした場合、どちらが勝つことになりますか？

制約

• \(1 \leq T \leq 20\)
• \(1 \leq N \leq 100\)
• \(1 \leq L_i <R_i \leq 100\)

STEP1　ゲームの勝者を求める問題

ゲームの勝者を求める問題では次のような解法をよく用います。

• ゲームの展開を状態と遷移に落とし、後ろからDPする。
• ad-hocな必勝条件を求める
  • 貪欲法
  • 相手の真似をする　など
• grundy数を用いる

今回の問題では状態数が多くDPは使えそうにありません。 また問題設定が単純すぎて、貪欲などad-hocな解もなさそうです。 grundy数が使えないか考えましょう。

STEP2　grundy数について

grundy数は、ゲームをいくつかの小さなゲームに分割できるときによく利用されます。(例: Nimを1つずつの山に分割する、区間を小さな区間に分割する)

grundy数の情報はネット上に充実しているので、重要事項のみまとめます。

定義1

有向非巡回グラフ(DAG) \(G = (V,E)\) について、\(G\) の各頂点 \(v\) のgrundy数 grundy\(_G(v)\) を次で定義する。

• \(\mathrm{grundy}_G(v) = \mathrm{mex}\{\ \mathrm{grundy}_G(w) : (v,w) \in E\ \}\)

ただし非負整数の集合 \(S\) に対し、\(\mathrm{mex} \ S\) で \(S\) に含まれない最小の非負整数を表す。

( \(G\) はDAGなので、grundy数はトポロジカルソートの逆順により帰納的に求められる。)

定義2

グラフ \(G_1 = (V_1, E_1)\), \(G_2 = (V_2, E_2)\) に対し、\(G_1\) と \(G_2\) の積グラフ \(G_1 \times G_2 = (V_{1\times 2}, E_{1\times 2})\)を次で定義する。

• \(V_{1 \times 2} = V_1 \times V_2\)
• \(E_{1\times 2} = V_1 \times E_2 \cup V_2 \times E_1\)

定理1

DAG \(G\) と 頂点 \(v\) が与えられている。

Alice と Bob が次のようなゲームをする。

• はじめコマが \(v\) に置かれている
• Aliceから初めて、以下の操作を交互に行う。
  • コマを有向辺により隣接する頂点のどれかに移す。
• 先に操作を行えなくなったプレーヤーの負け、そうでないプレーヤーの勝ちである。

このゲームで双方が最善を尽くすとき、

• Alice がゲームに勝つ \(\iff\ \mathrm{grundy}_G(v) > 0\)

(多くのゲームは、ゲームの状態と遷移をグラフの頂点と辺におきかえることによりDAG上のゲームに帰着できる。以下では、ゲームのgrundy数と呼んだ時、対応するグラフのgrundy数を表す。)

定理2

DAG \(G_1,G_2\) と各々の頂点 \(v_1,v_2 \)に対し、

• \(\mathrm{grundy}_{G_1 \times G_2} ((v_1, v_2)) = \mathrm{grundy}_{G_1}(v_1)\ \mathrm{xor}\ \mathrm{grundy}_{G_2}(v_2)\)

が成り立つ。

(つまり、互いに無干渉な複数のゲームを同時に行う場合、各ゲームのgrundy数のxorを取ることにより全体のゲームでどちらが必勝かを判定できる。)

STEP3　grundy数の利用

今回のゲームでは、1つの区間を選んだ時残った領域が2つの区間に分割されます。それぞれの区間を「互いに無干渉な小ゲーム」だとみなし、区間dpの要領で必勝法を求めます。

整数からなる集合\(S\)に対し、次のゲームを考えます。

• Alice から始めて、以下の操作を交互に行う。
  
  • \(N\) 個の区間の中から、\(S\)の部分集合であり、かつ既に選ばれているどの区間とも共有点をもたない区間を \(1\) つ選ぶ。
• 先に操作を行えなくなったプレーヤーの負け、そうでないプレーヤーの勝ちである。

このゲームのgrundy数を \(gr(S)\) とおきます。 主に\(S\) が区間 \([l,r) (1 \leq l \leq r \leq 100)\) の時、grundy数 \(gr(l,r) := gr([l,r))\) の値がどうなるか考えます。 最終的に \(gr(0,100)\) を求めることが目標です。

さて、\(gr(l,r)\)を求めましょう。 区間 \([l,r)\) が与えられたときにAliceは次の手を打つことができます。

• \([l,r)\) に含まれる区間 \([A_i,B_i)\) を選ぶ。

さて、ある \(i\) に対しAliceが \([A_i,B_i)\) を選んだとすると、残った領域は区間 \([l,A_i)\) と区間 \([B_i,r)\) に分割されます。 以降、2つの区間はお互いに無干渉のままゲームが進んでいきます。

\([l,A_i)\) のgrundy数は \(gr(l,A_i)\) 、 \([B_i,r)\) のgrundy数は \(gr(B_i,r)\) なので、Aliceが 区間 \([A_i,B_i)\) を選んだあとの状態のgrundy数 \(gr([l,A_i) \cup [B_i,r)) \) は、

• \(gr([l,A_i) \cup [B_i,r)) = gr(l,A_i) \ \mathrm{xor} \ gr(B_i,r)\)

です。

よって、Aliceが区間を選ぶ前の状態でのgrundy数 \(gr[l,r)\) は、

• \(gr(l,r) = \mathrm{mex} \left\{ gr(l,A_i) \ \mathrm{xor} \ gr(B_i) : [A_i,B_i) \subseteq [l,r) \right\}\ \ldots (*)\)

となります。

STEP4　区間DP

区間DPにより \(gr[0,100]\)の値を求めましょう。

\(l=r\)のときは、\([l,r)\)は空集合ですからAliceの負け、つまり\(gr(l,r) = 0\)です。 遷移式(*)を用い、長さの短い \((l,r)\) から順番に、\(gr(l,r)\) の値を求めます。 \(gr(0,100) > 0\) であればAliceの勝ち、そうでなければBobの勝ちです。

1つのテストケースについて計算量は \(O(N^3)\) なので、全体で実行時間制限に間に合います。