ABC 398 E — Tree Game

考察

木はconnected bipartiteで、その二部分彩色はswapを除き一意である。odd cycleを作らず追加できるのは異なる色間の未存在edgeだけである。

どの合法edgeを加えても部集合は変わらず、合法手数総数は|L||R|-(N-1)に固定される。

採用する候補: 二部分彩色して残り合法edge数のparityを求め、同じ色分割間の未edgeを応答用setに持つ

棄却する候補: 各局面で相手の手に応じたgame DPを行う

合法手同士に相互作用がなく、状態数だけを指数的に増やす過剰な方法である。

DFS/BFSでcolorとpart sizeを求め、未edgecross pairをsetへ列挙する。size parityでFirst/Secondを宣言し、自手番ではsetから一辺を出し、相手入力edgeをsetから削除する。

典型の発動条件

impartial gameの手数parity化

発動条件: 各手が独立な候補を一つ消し、他候補の可否を変えないとき。

残候補数の偶奇だけで勝者を決める。

bipartite graphの一意彩色

発動条件: connected graphでodd cycle禁止edgeを特徴付けるとき。

二部集合間だけを合法候補とする。

問題固有の要素

interactiveな戦略問題でも、全合法手が可換なら相手の選択内容を読む必要はなく、手数parityだけで先後を選べる。

別の問題へ持ち帰る視点: ゲームでは操作が残り選択肢集合へ及ぼす影響を確認し、単なるtoken取りゲームへ退化しないか調べる。

正当性

connected bipartite graphへcross-part edgeを追加しても同じ二部分彩色が有効なので、別候補の合法性は変化しない。 初期tree edgeN-1は全てcross-partに既に存在するため、残候補数は積からN-1を引く。 ゲームは固定された候補辺を交互に一つ消費するだけなので、残手数がoddなら先手、evenなら後手を選べば任意応答で必勝する。

実装上の注意

  • 各出力後にflushし、相手の(-1,-1)で即終了する。既存tree edgeを候補setへ入れず、pair indexを正規化する。

復習の核

  • path/starのpart sizeから候補を手列挙し、任意順で全候補を消費しても合法性が保たれることと手数parityを確認する。

計算量と制約

時間

O(N²)、二色塗りと全cross未辺の列挙。

空間

O(N²)、未辺set。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 100; 1 \leq U_i < V_i \leq N; The given graph is a tree.; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Tree Game の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 偶奇不変量からゲームの勝敗を決める

主題
  • 偶奇不変量からゲームの勝敗を決める: 合法手が独立な固定候補の消費に限られる場合や、成分分類から残手数の偶奇を求められる場合に、勝敗を決める偶奇量と応答戦略を証明し、局面ごとのDPなしで勝者を判定できる。
追加で学ぶ技能
既習技能
  • 対話protocolを守って情報を取得する: judgeとの問い合わせ応答または交互手番のprotocolを守り、許された形式で応答依存の探索・合法手の提示・終了処理を実行できる。query上限がある場合はその回数も満たす。

主タグ: 二部グラフの彩色と成分構造 偶奇不変量によるゲーム戦略

補助タグ: 対話protocolとquery設計

執筆: abc-explanation-author1.1.1 / revision 2

学習の位置

体系上の位置: 偶奇不変量からゲームの勝敗を決める

  • 合法手が独立な固定候補の消費に限られる場合や、成分分類から残手数の偶奇を求められる場合に、勝敗を決める偶奇量と応答戦略を証明し、局面ごとのDPなしで勝者を判定できる。
  • 各連結成分を二色に塗って矛盾を検出し、二つの部の大きさと色反転の自由度を成分ごとに集約できる。

先に読む単元:

  • 対話protocolを守って情報を取得する — 問い合わせ形式・回数上限・応答依存性・交互手番・合法な応答・flushを明示し、アルゴリズムをjudgeとの対話列として安全に実行する。

この解説で扱わないこと:

  • 後続状態の勝敗を再帰計算するGrundy DP、局面値を評価するminimax、およびグラフの二部彩色そのもの。

学習記録

状況更新: 更新記録なし

復習設定更新: 更新記録なし

端末内の保存状態を確認しています。

要復習一覧 / 学習記録のバックアップ / 解説に戻る

同じ単元の問題