CODE THANKS FESTIVAL 2018-H:Median Game

これはわかればシンプルで楽に解けるので好き。

問題

解法

このゲームでは，ある列の中央値がゲームのスコアになり，それを求めよと言われている(偶数のときは2つ候補があるが，大きいほうをとる)。中央値を求める問題では二分探索が有効である。中央値が $x$ 以上となるか？という質問に答えるには，数列の中に $x$ より以上の数が半分以上含まれるかを調べるだけでよく，これは比較的容易にできるためである。

それでは，「ゲームのスコアは $x$ 以上になるか？」という問題に答えよう(この問題は $x$ について答えが単調なので，二分探索が使える)。このとき，Aliceはスコアを大きくしたいので， $x$ 以上の数を増やしたいはずである。一方Bobは，スコアを小さくしたいので， $x$ より小さい数を増やしたいはずである。この2人の戦いをdpによって見守ろう。

$dpAlice[i]$ :上から $i$ 枚目以降のカードが残っているときにAliceの手番で， $(x以上の個数)-(x未満の個数)$ の最大値
$dpBob[i]$ :上から $i$ 枚目以降のカードが残っているときにBobの手番で， $(x以上の個数)-(x未満の個数)$ の最小値

dpの遷移であるが，とりあえずAliceの手番のときを考えよう。今回はこのdpに $O(N^2)$ かけてよいので。 $i\lt j \leq N+1$ について，区間 $[i,j-1]$ のカードをとり， $j$ 枚目以降のカードを残してBobに手番を渡すとしよう( $j=N+1$ のときはゲーム終了という意味)。これらのカードの総和を $S$ とすると， $S$ と $x$ の大小によって $dpBob[j]$ に $1$ を足すか $-1$ を足すかすればよい。この結果の $j$ についての最大値が $dpAlice[i]$ である。Bobの手番のときも同様である。
dpの遷移は後ろから，つまり $i=N$ から行うことに注意。ゲームでdpをするときの定番だろう。「ゲームのスコアは $x$ 以上になるか？」という問題の答えは， $dpAlice[1]\geq 0$ のときYes，そうでないときNoである。