問題

https://atcoder.jp/contests/aising2019/tasks/aising2019_d

考え方

まず、ゲームがすすんだときにどのようにカードが選ばれているか確認する必要がある。高橋くんは上から大きい数を選んでいくので簡単である。青木さんは $x$ に近い数から順にとっていく。高橋くんの選んだカードを T 、青木さんが選んだカードを A とすると一般的には

ATATATAAAATTTT

のようにカードが選ばれることがわかる。ある境界値までは ATAT と高橋くんと青木さんは順番にカードを選ぶことがわかり、その後は青木さんが AAAA 、高橋くんが TTTT とカードを選ぶことが分かる。境界を | で表すことにすると以下のような選び方が存在する。

ATAT|AAATTT <- 青木さんと高橋くんはカードを競合することなく選ぶことができる。
ATATA|AATTT <- $A_6(0-indexed)$ のカードを青木さんと高橋くんで取り合う(高橋くんがとることになる)

さて、カードの選び方がわかったので実装を考える。「高橋くんがカードの大きいほうから $k$ 枚選ぶことができるかどうか？」という判定問題を考えよう。これは単調である。

上から $k$ 枚選ぶとき高橋くんは $A_{N-k}(0-indexed)$ 番目のカードを $k$ 番目に選ぶことになる。このとき青木さんがすで $A_{N-k}$ をとっていなければ、高橋くんは $A_{N-k}$ のカードを選ぶことができる。(なお同じ順番で選ぶ場合は高橋くんが優先なので選ぶことができる。)青木さんが $A_{N-k}$ のカードを何番目に選ぶか求めよう。青木さんが $A_{N-k}$ のカードを選ぶとき、 $d = A_{N-k} - x$ として $[x-d, x+d]$ の値に含まれるカードはすべて選ばれていることになる。 $x-d \le A_i$ を満たす最小の $i$ を $s$ とすると $A_{N-k}$ のカードは $(n - 1 - k + 1) - (s - 1)=n-k-s+1$ 番目に選ばれることになる。

よって「高橋くんがカードの大きいほうから $k$ 枚選ぶことができるかどうか？」の解は「 $n-k-s+1 \ge k$ であれば選ぶことができる。そうでない場合は選ぶことができない。」となる。

AAATTT のとり方が分かれば、あとは偶奇ごとに分けた累積和を足せば ATATAT の T のカードの合計は簡単に求めることができる。

Submission #4142667 - AISing Programming Contest 2019 / エイシングプログラミングコンテスト 2019

どこに着目して考察するべきだったか

まずはなによりもカードの選び方がどうなるか分かる必要がある。これは $N=10$ くらいのケースを考えればわかりそう。選び方の境界を求めるには「高橋くんが上から $k$ 枚選ぶことができるか？」という判定問題を考えればよいことがわかると実装がシンプルになりそう。計算量は $O(logN)$ だけ悪化するがほぼ無視できる。