B - Taking the middle

この記事は解説記事というより類題を解けるように問題の本質を自分用にメモしたものなのであまり参考にならないかも...

TLE解法（もしかするとWA)

  • 最小費用流
  • dp[何個取ったか][N-i-1からN+i以外の範囲から何個取ったか] = 最大値

AC解法

どうやら高度典型らしい。

1つ目の文章

中央を取られ続けるということは、V[n-i : n+i] の範囲から i 個までしか取れないことと等価です(高度典型)

これはカードを取るときの自由度が低い青木くんに注目することで、青木くんが常にV[n-i : n+i] の範囲から i 個以上取っている事がわかる。
十分条件がわかったのでこれが必要十分条権になることを証明すれば気がつけば典型を導けそう。
十分条件を見つける→必要十分で有ることを証明する
っていうのは典型ぽいので自力で導けるようにしたい。

2つ目の文章

外側 2 つを入れて任意の 1 要素を取り出すとするとこの条件を表現できます

番号が N−i+1以上 N+i以下のカードであってまだ選ばれていないもののうち、価値が最小のものを選べば良いことがわかる。
このような問題はpriority_queueで解ける(類題はあり本p73のexpedition)

今回の問題と類題の共通要素は
「決定するタイミングを後にずらして選択肢を全部みてから決める」
という部分にあると思う。