競プロ備忘録

競プロerの備忘録

ABC201D - Game in Momotetsu World

結構シンプルなコードが書けて、説明としてもわかりやすいものになったと思うので残します。
本質的には公式解説などと何も変わりないので、新規性はないかも。

解法

手番の偶奇を考えるのは面倒なので、以下のようなDPを考える。

 dp_{i, j} := マス (i, j)から先攻でゲームを開始したとき、後攻より最大何点上回れるか

自明に、右下のマスからゲームを開始した場合はそれ以上動けないので、 dp _ {H, W} = 0である。
このDP配列を後ろから更新することを考えると、見ているマスの右、下のマスについてDP配列の値が埋まっているので、これを用いて以下のように更新する。

 dp _ {i, j} = max(score _ {i+1, j} - dp _ {i+1, j},  score _ {i, j+1} - dp _ {i, j+1})

ただし、 score _ {i, j}は、マス (i, j)が'+'であるときは 1、'-'であるときは -1となる値(すなわち、そのマスに進んだときに自分のスコアに加算される値)である。
隣接するマスのDP配列の値はすなわち「相手がそのマスからスタートしたときに自分より最大何点上回れるか」を示しており、マス neighborに進んだときに獲得できる score _ {neighbor}から dp _ {neighbor}の値を引いてやれば、自分がマス neighborに進んだ場合、相手より最大何点上回れるかが求まる。
よってこの式の意味としては、マス (i+1, j)とマス (i, j+1)に進んだ場合の相手とのスコア差の最大値を計算しているということになる。

この通りにDP配列の更新を行っていけば、 dp _ {1, 1}がゲーム全体として先攻が後攻をどの程度スコアで上回れるかを示しているので、 dp _ {1, 1} \lt 0なら"Aoki"、 dp _ {1, 1} = 0なら"Draw"、 dp _ {1, 1} \gt 0なら"Takahashi"と答えればよい。

実装は以下の通り。

Submission #36863786 - Mynavi Programming Contest 2021(AtCoder Beginner Contest 201)

マスによって先攻後攻の場合分けをして最大最小どちらを取るか考えなくて良いので、実装としてはかなりシンプルで楽だと思う。