Nearest Card Game [AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019 D]

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

解説

https://atcoder.jp/contests/aising2019/submissions/3994956

T:高橋くんとA:青木くんがどう取るかを考えると、
ATATATAAATTT
のようになる。
つまり、ATATAT部分とAAA部分とTTT部分である。
AAA部分とTTT部分は同じ個数になる。
各Xについて、
① ATATATとAAATTTの境界を見つける。つまり、AAAとTTTの個数を特定する
② ATATATのTの総和とTTTの総和を計算して答える
ができれば良い。
　
②の方は前処理することで、すぐ計算できる。
前処理は関数initで行っている。
get(L,R)でA[L]+...+A[R]を得られる。これでTTT部分は計算可能。
takasm[i]でATATAT...としたときのi番目までのTの総和が得られる。
Nが偶数の場合はATATAT, Nが奇数の場合はTATATとなるので、その辺を考慮して作る。
　
①が難しいのだが、これは二分探索で特定する。
他と違う二分探索なのだが、Xからの差分で二分探索する。
このためにf(x,len)を用意しよう。
[x-len,x+len]の範囲にあるAの要素の[L,R]を返す。
二分探索対象は、このlenである。
lenを大きくすれば、[L,R]の範囲が大きくなる。
この範囲をAAA部分とすれば、TTT部分は[R+1,N)の範囲になる。
この2つの範囲が重なるか、隣り合っていれば、その差分になるときにATATATの状態になっていることが分かる。
その境目の瞬間がちょうどその時である。
境目の瞬間は必ず隣り合っているように思えるかもしれないが、実際には重なる場合がある。
このときは、AAA部分が1つ多いので、右側を1つ減らそう。
　
これで①②を解決できたので、答えられる。

int N, Q, A[101010], X[101010];
//---------------------------------------------------------------------------------------------------
ll B[101010], takasm[101010];
void init() {
    B[0] = A[0];
    rep(i, 1, N) B[i] = B[i - 1] + A[i];
 
    rep(i, 0, N) {
        if (N % 2 == 1 and i % 2 == 0) takasm[i] = A[i];
        if (N % 2 == 0 and i % 2 == 1) takasm[i] = A[i];
    }
    rep(i, 1, N) takasm[i] += takasm[i - 1];
}
ll get(int L, int R) {
    ll res = B[R];
    if (L) res -= B[L - 1];
    return res;
}
//---------------------------------------------------------------------------------------------------
pair<int, int> f(int x, int len) {
    int lft = lower_bound(A, A + N, x - len) - A;
    int rht = upper_bound(A, A + N, x + len) - A - 1;
    return { lft, rht };
}
//---------------------------------------------------------------------------------------------------
ll solve(int x) {
    int ng = -1, ok = inf;
    while (ng + 1 != ok) {
        int md = (ng + ok) / 2;
        auto p = f(x, md);
        if (p.first > p.second) {
            ng = md;
            continue;
        }
 
        int len = p.second - p.first + 1;
        if (N - 1 <= p.second + len) ok = md;
        else ng = md;
    }
 
    int L, R;
    tie(L, R) = f(x, ok);
    int turn = R - L + 1;
 
    int taka = N - R - 1;
    int aoki = turn;
 
    if (taka != aoki) {
        R--;
        aoki--;
        turn--;
    }
    
    ll res = get(R + 1, N - 1);
    if (L) res += takasm[L - 1];
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, Q) cin >> X[i];
    init();
    rep(i, 0, Q) printf("%lld\n", solve(X[i]));
}