AISing Programming Contest 2019 D - Nearest Card Game

• 問題
• AC

シミュレーションしてみると（時系列を無視すれば）

1. 高橋君が上から何枚か取って
2. 残りを青木君が上から同じ枚数取って
3. さらに残りを二人で上から交互に取る

という仕組みになっていることがわかる。

高橋君が手順1で上から$l$枚、つまり区間$[N-l, N)$を取るとし、青木君が手順2で区間$[N-2l, N-l)$を取るとして、与えられたルールに従うための$l$の条件を考える。

まず、青木君が取るもっとも大きい数は$A_{N-l-1}$である。したがって、青木君が最初に決めた数を$x$とするとき、$x- \max(A_{N-l-1}-x, 0)$以上の数が書かれたカードはすべて青木君が取っていなければならないことになる。ここで、

$f(y) :=$ $y$以上の数が書かれたもっとも左のカードのインデックス

とする。（ $f(y)$は二分探索で求まる。） $f$を使って上の条件を表すと、青木君は少なくとも区間$[f(x- \max(A_{N-l-1}-x, 0)), N-l)$を取らなければならず、これは、青木君が手順2で取るカードの枚数が$(N-l)-f(x- \max(A_{N-l-1}-x, 0))$以上であることを意味する。この数を$g(l, x)$で表すとき、$g(l, x)$は$l$以下でなければならない。したがって、ルールに従った取り方では、$g(l, x) \le l$であるような最大の$l =: l_{\max}$が、手順1, 2で実際に取った枚数になる。$g(l, x)$は$l$について単調増加なので$l_{\max}$はやはり二分探索で求まる。

$l_{\max}$が求まったら、高橋君の点数は区間$[N-l_{\max}, N)$の総和と$[0, N-2l_{\max})$をひとつおきに取った和（$0$から始まるか$1$から始まるかは偶奇による）の合計になるため、どちらも累積和を計算しておけば${\mathcal O}(1)$で求まる。