ABC 229 H — Advance or Eat

考察

前進も相手駒を食べる操作も一列だけを変えるため、盤面はN個の独立な列ゲームの和である。ただし白と黒で合法手が異なるので、通常の不偏ゲームのGrundy数とXORは適用できない。各列を白に有利なら正、黒に有利なら負の数として評価し、その和を使えないか考える。

一列には3^N状態があり、駒の前進・除去は後で定める順位を厳密に減らす。白の子評価の最大値Lより大きく、黒の子評価の最小値Rより小さい数を評価にする。この問題では操作を交換した共通状態、または食べる・進める二操作の直接の辺により常にL<Rを示せる。具体的な交換は正当性欄で証明する。子から順に数を付けられることが、単なる符号やGrundy数とは異なる核心である。

「最も単純な二進有理数」を計算する手順を決める。白の子評価の最大をL、黒の子評価の最小をRとし、対応する子がなければL=−∞、R=+∞。L<Rの開区間で、まず整数の存在を調べる。有限端について最小候補はfloor(L)+1、最大候補はceil(R)−1。整数があれば、その範囲内で0に最も近い整数を選ぶ。双方の手がない状態は0、白手だけなら正の整数、黒手だけなら負の整数へ接続する。

整数がなければt=1,2,…と増やし、floor(2^tL)+1≤ceil(2^tR)−1となる最初のtを探す。この整数範囲の要素mを取りeval=m/2^tとする。前の分母で候補がないため、この段の候補は一つでmは奇数。例えば1/2<eval<1では整数がなく、t=1でもなく、t=2で3/4となる。浮動小数のepsilonでstrict不等号を代用しない。

各列の駒の上からの位置を0,…,N−1とし、H(state)=Σ_{駒}(位置+1)をDAGの順位に使う。前進も除去もHを厳密に減らし、H≤N(N+1)/2=:H_max。子評価の分母が2^{h−1}を割るなら、非空の両端の間隔はその格子一つ以上あり、分母2^hまでで候補がある。帰納的に分母指数はH以下。Q=2^{H_max}を共通分母とし、全評価をQ倍した整数で保持すれば、探索のfloor/ceil・列和の符号を厳密に計算できる。N≤8ではH_max≤36で十分小さい。

数の加算を勝敗へ使える理由も確認する。非整数評価vの既約分母が2^tなら、v−2^{−t}とv+2^{−t}はより単純な候補である。両方が開区間外でなければvは最も単純ではないため、白にはvを高々2^{−t}減らす子が、黒には高々2^{−t}増やす子がある。正整数vなら白に高々1減らす子があり、負整数なら黒に高々1増やす子がある。

総和s>0が整数なら正の列を選んで高々1減らす。sが非整数で既約分母2^tなら、分母指数がt以上の列を選び、高々2^{−t}減らす。どちらも白は和を0以上へ移せる。和が0以下では全白手が和を厳密に負へする。黒も符号反転した同じ議論で、負の和から0以下へ応答できる。DAGなので無限に続かず、白番で正の和だけが勝ち、0以下は負けとなる。

典型の発動条件

独立ゲームの直和分解

発動条件: 一手が複数領域のうち一領域だけを変え、領域間で合法手が干渉しないとき。

各列を独立なゲーム成分として評価し、列評価を加算して盤面全体を扱う。

partisan game の数値評価

発動条件: 二人の合法手が異なるが、全ての左選択肢が全ての右選択肢より小さい数ゲームとして表せるとき。

白後継の上界と黒後継の下界の間にある最小絶対値の整数、なければ最小分母の二進有理数を選ぶ。

問題固有の要素

食べる操作は任意列の駒を消せるが、一手で変わるのはその駒の列だけなので、見かけに反して列分解を壊さない。

別の問題へ持ち帰る視点: 操作対象を全盤面から自由に選べても、状態変更が一成分内に閉じるならゲーム和への分解を検討する。

正当性

一手は一列だけを変えるため盤面は列ゲームの直和。手番で遷移が異なるのでGrundy XORは適用できない。白手v→aと黒手v→bが干渉しなければ双方を適用した状態cが存在し、a→cは黒手、b→cは白手なので帰納法でeval(a)<eval(c)<eval(b)。唯一の干渉は同じ駒を食べる・進める場合で、進めた後に食べる辺が存在するため直接eval(a)<eval(b)となる。ゆえに全左値<全右値を満たす数のゲームである。左右値間の最も単純な二進有理数を再帰的に割り当てるConway評価は直和で加算できる。総値が正なら白のTakahashiが先手勝ち、0以下ならSnukeが勝つ。駒減少または前進によるDAG順で全状態を評価し、浮動小数へ丸めない。 最も単純な二進有理数は開区間のfloor/ceil検査で厳密に求まり、分母指数は減少順位H以下。非整数評価の両隣のより単純な候補が区間外となる性質から、両者に一分母単位以内の応答手がある。これと整数評価の同じ性質により、正の総和から白は非負へ、負の総和から黒は非正へ移せ、0からの自手は相手に有利な符号を返す。有限性と帰納法で総和による勝敗判定が従う。

実装上の注意

  • 空・白・黒の三進数を列状態とし、駒の位置+1の総和が小さい状態から評価するかmemo再帰する。
  • 手がない側の端は∞。floor/ceilは負数でも数学的な丸めとし、両端の等号を除く。
  • 評価はQ倍した整数Vで保持する。指数tでのfloor(2^t eval)はfloor(V/(Q/2^t))として求め、Vを2^t倍して中間値を大きくしない。ceilも同じ正の除数で数学的に丸める。|eval|≤H_max、列和の絶対値もN H_max Q以下なので、N≤8では符号付き64bitで扱える。

復習の核

  • ゲームを見て即座に Grundy 数へ進まず、両プレイヤーが各状態から同じ遷移を選べる不偏性を先に確認する。
  • 数ゲームの評価可能性は、任意の白手後継が任意の黒手後継より小さいことを操作交換図で確認する。

計算量と制約

時間

O((N+H_max)3^N)、H_max=N(N+1)/2≤36。各列状態でO(N)の手を作り、子評価の両端を求め、分母指数0…H_maxを調べる。共通分母Q=2^{H_max}での整数演算を固定幅で行う。本問N≤8では高々6561状態。

空間

O(3^N)状態と評価値。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 8; N is an integer.; S_{i,j} is W, B, or ..

出典

分類・前提・執筆情報

掲載状態: 収録済み

Advance or Eat の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 独立な数ゲームの和

主題
  • 独立な数ゲームの和: 全ての後続局面が数で、左選択肢の全値が右選択肢の全値より小さいことを確認し、その間の最も単純な二進有理数を局面値とする。独立和は厳密な数の加算で評価する。一般のpartisan gameは数とは限らず、この規則を適用しない。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 独立な数ゲームの和

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

      学習の位置

      体系上の位置: 独立な数ゲームの和

      • 全ての後続局面が数で、左選択肢の全値が右選択肢の全値より小さいことを確認し、その間の最も単純な二進有理数を局面値とする。独立和は厳密な数の加算で評価する。一般のpartisan gameは数とは限らず、この規則を適用しない。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

      先に読む単元:

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題