CODE THANKS FESTIVAL 2018 H - Median Game (500)

• 問題

解法

スコアは中央値なので,そのままやるとこれまで書いた和を全て持っておく必要がある(どれも中央値になり得る)
=> これは当然全探索に近いので不可能
=> 中央値は2ぶたんがやりやすい(X以上がY個の条件が判定しやすい) という典型もあり,判定関数を作って2ぶたんをしようという気持ちになる

すると判定をO(N²)ぐらいのDPでやろうというのが自然な流れになる.
注意としては,ゲームでDPをやるときは後ろから(そうしないと最終的にmax/minに持っていけない)
x以上のスコアを取れるか？という判定をすることを考える.
dp[ i ][ j ] := ( i ターン経過, a[j,N) でゲームをした時の x 以上の個数 ) とやると, O(N³) かかってしまう.
かといって遷移で x 以上でなるべく遠くをとったほうがいい みたいなのは成り立たない.(間違った)
ここで削れる要素は i ターンで, 先手/後手を持てば良さそうだが, x 以上が半分以上か?というのが判定できなくて困る.
こういうときは 値として #(x 以上) - #(x 未満) を持てば良い (半分以上か？を判定する典型)
( #(x以上)/ターン数 を最大化するようにこの2つの数を持ってもいいのか.. ? )

後は公式解説と同じ.
コードでは
dp1[ i ] := (先手番で,#(x以上) - #(x未満) の max )
dp2[ i ] := (後手番で #(x以上) - #(x未満) の min )
としている.

メモ

500ではない

コード