公式

F - Final Stage 解説 by physics0523

ヒント

Hint 1 ゲームの勝敗を分析する方法はいくつかありますが、今回の問題は何を選択すれば見通しがよいでしょうか?

Hint 2 ゲームに対して、後退解析をかけてみましょう。

Hint 3 ゲーム中のどの時点でも、山に残っている石の個数から「先手の勝ち」「後手の勝ち」「引き分け」が求められます。
また、 (当然と言えば当然ですが、) 各結果に辿り着く石の個数の集合は、いくつかの整数の区間 \([l,r]\) の和集合として表現できます。
「同じ結果になる石の個数がいくつかの区間を成す」ということを強めに意識しながら、改めて後退解析をかけてみましょう。

Hint 4 サンプルに対して後退解析をかけてみましょう。
  • 初期状態: \([0,\infty)\)=引き分け
  • 後手 \([1,2]\) : \([0,0]\) =先手勝ち、 \([1,\infty)\)=引き分け
  • 先手 \([3,4]\) : \([0,2]\) =後手勝ち、 \([3,4]\)=先手勝ち、 \([5,\infty)\)=引き分け
  • 後手 \([1,2]\) : \([0,0]\) =先手勝ち、 \([1,4]\)=後手勝ち、 \([5,5]\) =先手勝ち、 \([6,\infty)\)=引き分け
  • 先手 \([1,3]\) : \([0,0]\) =後手勝ち、 \([1,3]\) =先手勝ち、 \([4,5]\)=後手勝ち、 \([6,8]\) =先手勝ち、 \([9,\infty)\)=引き分け

この後退解析で何が起こっているかを考えてみましょう。


Hint 5 先手が \([L,R]\) 個石を取るべき手番であったとすると、その手番を後退解析すると起こることは次の通りです。
  • 山に残っている石の個数が \([0,L-1]\) 中なら後手勝ちとなる。
  • 一手前の先手勝ち \([A,B]\) は \([A+L,B+R]\) に移る。ただし、この区間は複数重なりうる。
  • 一手前の後手勝ち \([A,B]\) は \([A+R,B+L]\) に移る。ただし、この区間が潰れた場合は消滅する。

ここからはデータ構造の問題です。この後退解析を効率的に行うことを試みましょう。

Hint 6 いったん区間が潰れたり重なったりする事態から目を背けましょう。
そうすると、更新は常に、全ての先手勝ちの区間が長さ \(l\) だけ伸び、全ての後手勝ちの区間が長さ \(l\) だけ縮む (またはその逆) という形をしています。

Hint 7 どの時点でも、区間を並べていったとき勝敗は
  • …(先手勝ち)(後手勝ち)(先手勝ち)(引き分け)
  • …(後手勝ち)(先手勝ち)(後手勝ち)(引き分け)
のどちらかの形を成します。
とすると、「区間が潰れる」「区間が重なる」は表裏一体の現象であることが分かります。
「任意位置の区間をひとつ潰す」→「(必要なら)その両隣にあった区間をマージする」を実現するのに好都合なデータ構造を我々は知っているはずです。

Hint 8 Hint 6 にて、「全ての区間を同じ長さだけ伸縮させる」という操作が生まれていますが、これは「区間の長さに対応するオフセットを保持し、オフセットの基準値のみを加減する」というように取り扱うと軽く実行できます。
Hint 7 での好都合なデータ構造とは連結リストです。これも活用しましょう。

投稿日時:
最終更新: