AGC033 B - LRUD Game
解法
まず気付くべき点は、縦と横は独立に考えられることです。これは今回のゲームのルールが
- 盤外に落ちる条件が「縦座標が
の範囲から外れること」または「横座標が
の範囲から外れること」であること
- 縦座標と横座標が互いに影響し合わないこと
- 高橋くんも青木くんもあるターンには決まった方向にしか動けず、「1ターンに縦に動くか横に動くか選べる」という状況がないこと
から、独立に考えてもよいことが分かります。
そのため、高橋くんが駒を縦方向に落とすことができるか・横方向に落とすことができるかをそれぞれ考えます。判定方法は同じなので、以降は横方向の場合だけを説明します。横方向だけを考える場合においては、文字が U D であるターンは「何もできないターン」だと見なして良いです。
ここでもしゲームの進行順と同じように前から考えると、高橋くん・青木くんともに「最適な戦略」を考えるのがとても難しいです。高橋くんは左右どっちに落としても勝てるので、高橋くんも青木くんも駒を左右どちら側に寄せたほうが得なのか分かりません。ターンごとにそれぞれが動ける向きが決まっているので、高橋くんは端に向かう/青木くんは真ん中に向かうような戦略も最適ではないです。全局面をシミュレートすればもちろん最適解は分かりますが、計算時間が足りません。
そこで使えるのが「逆から考える」テクニックです。逆から考えることの嬉しい点は、ゲーム中の全てのタイミングで、「今、駒がどこにあればどっちの勝ちなのか」がバッチリ決まる という点です。
このことを具体的に見ていきましょう。以下の入力例1を使います。
2 3 3 2 2 RRL LUD
まず、最終局面については簡単です。ゲームのルールから、横座標を として
の範囲にあれば青木くんの勝ち、そうでなければ高橋くんの勝ちです。
最終ターンである第3ターンの青木くんの行動には意味がないので、第3ターンの高橋くんの行動を考えましょう。高橋くんは自分のターンの行動によって、先ほどの範囲 から駒を出すことができれば勝ちです。第3ターンの高橋くんの文字は
L なので、もし であれば左に動かして範囲から出すことができます。
のときは範囲から出すことができません。
つまり第3ターンの直前時点では、「横座標がこの範囲にあれば青木くんの勝ち」という範囲は と変わります。
次は第2ターンの青木くんの行動ですが、文字は U なので青木くんは横方向に駒を動かせません。範囲はそのままです。
次は第2ターンの高橋くん、文字は R です。つまり「もしこのターンの前に だったら、
の範囲から出せる」ので、このターン直前時点での青木くんが勝てる範囲は
です。
次は第1ターンの青木くん、文字は L です。この場合、「もしこのターンの前に だったら、左に動かすことで
に入れることができる」ので、このターン直前時点での青木くんが勝てる範囲は
です。
最後に第1ターンの高橋くん。これは先ほどと全く同じで、このターン直前時点（つまりゲーム開始時点）での青木くんが勝てる範囲は となります。
この入力例1において初期座標は だったので、このゲームは（横方向に関しては）青木くんの勝ちとなります。
…と、このように逆から考えることで各ターンにおける「横座標がこの範囲にあれば青木くんの勝ち」という範囲を求めていくことができます。
各プレイヤーの文字が L または R であるターンにおいて、その方向に応じて高橋くんはこれを1マス分縮めることが、青木くんはこれを（盤外を含まない範囲で）1マス分広げることができます。そして途中で存在できる範囲が1マスもなくなってしまったり、最後の（つまりゲーム最初の）範囲に初期座標が入っていなければ高橋くんの勝ちです。
図を見ても分かるように青木くんの勝てる範囲は必ず1つの区間になるので、その最小値と最大値を持っておくことで範囲の伸び縮みを処理できます。縦横それぞれこのような判定をして、どちらかで高橋くんが勝てば駒は落ちるので結果は高橋くんの勝ち、両方で青木くんが勝てば駒は縦にも横にも落ちないので結果は青木くんの勝ちです。
実装コード
Submission #5259153 - AtCoder Grand Contest 033
実装テクですが、縦と横で別々にコードを書いて、ほとんど処理は同じなのに と初期座標と見る文字は違ってて…みたいな実装はあまり得策ではないです。コピペして1箇所変数を変え忘れた、などの悲劇が起こります。
できればリンク先の実装コードのように、共通化して2度同じコードを回るような実装にするのがオススメです。
