ゆらのふなびと

競プロ, Python, C++

AOJ-ICPC 400 インビジブル

問題

インビジブル | Aizu Online Judge

D: インビジブル - JAG Contest 2016 Domestic | AtCoder

解法

先手はスコアの最大化、後手は最小化を目指すのでミニマックス法で解ける。

先手, 後手のデッキでスタックにつまれている区間をそれぞれ[l0, r0), [l1, r1)とすると、状態として(l0, r0, l1, r1, 今どちらの手番か, スタックが空になってから何回パスが連続したか)を持つだけでよいというのがポイント。パスで得点が変化するときには相手が最後に置いた妨害カードより上にある自分の得点カードの和がわかればよいので、実装ではこれらも引数に入れると楽だった。

あとこれはインビジブルあるあるなんですけど、スタックが空になってないのにパスの回数を足して死んでいた。

http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2016%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9B%BD%E5%86%85%E4%BA%88%E9%81%B8A%2F%E8%AC%9B%E8%A9%95&openfile=D.pdf

gist.github.com