Writer 解説: https://img.atcoder.jp/aising2019/editorial.pdf

問題概要

$ N (\leq 10^5)$枚の数字が書かれたカード $ A_1 \lt A_2 \lt \cdots \lt A_N$ を高橋くんと青木くんが交互に，カードがなくなるまで取っていく．先攻は高橋くんである．高橋くんは数字の大きいカードから順に，青木くんはあらかじめある数字 $ x$ を決めておき，その数字に近い数字のカードから順に取っていく．

いま， $ x$ の値の候補が$ Q (\leq 10^5)$ 個与えられる．それぞれについて，高橋くんが取るカードの数字の合計を求めよ．

解法概要

A が

青木くんと高橋くんが交互に取るエリア
青木くんが必ず取るエリア
高橋くんが必ず取るエリア

の順に 3 つに分けられることがわかった．このエリアの境界を $ O(log N)$とかで求めることができれば良さそう． (エリアの境界がわかれば，あとは事前にインデックスの偶奇ごとの累積和を取っておけば計算できるため)

エリア 3 の開始インデックスがわかればエリア 3 の長さがわかり，エリア 3 の長さがわかればエリア 2 の開始インデックスもわかる (方法は後述) ので，エリア 3 の開始インデックスについて考察する．

ルールより，青木くんが最初に取るカードは $ x$ に最も近い数字のカードである．これは二分探索で求められる．このカードのインデックスを $ i_\mathit{nearest}$ とすると，$ A_{i_\mathit{nearest}}$は $ A_n$でない限り必ずエリア 2 に含まれる．

$ A_{i_\mathit{nearest}} = A_n$ のときは高橋くんも青木くんも数字の大きなカードから順に取るという同じ戦略を取ることになるので，高橋くんが $ A_{i_\mathit{nearest}}$ を先に取ってしまう．この場合の高橋くんのカードの数字の合計は，カードを 1-indexed で管理しているとすると$ N$が奇数なら奇数インデックス，偶数なら偶数インデックスのカードの数字の合計になる．以下， $ A_{i_\mathit{nearest}} \neq A_n$ を仮定して考察を進める．

この仮定を付け加えると$ A_{i_\mathit{nearest}}$必ずエリア 2 に含まれるから，エリア 3 の開始インデックスは$ i_\mathit{takahashi}$について $ i_\mathit{nearest} \lt i_\mathit{takahashi} \leq n$が成り立つ．これを二分探索で求めることを考える．$ i_\mathit{nearest} \lt j \leq n$ であるカード $ A_j$ を高橋くんが取るために必要な条件は，高橋くんから見た$ A_j$ を取る優先順位 $ r_\mathit{takahashi}$と青木くんから見た$ A_j$ を取る優先順位$ r_\mathit{aoki}$ について　$ r_\mathit{takahashi} \leq r_\mathit{aoki}$ が成り立つことである．$ r_\mathit{takahashi}$ はそのカードの数字が何番目に大きいかを数えれば求まる．$ r_\mathit{aoki}$ はそのカードよりも $ x$との差が小さいカードの枚数を二分探索などで調べれば求まる．これらを利用するとエリア 3 の開始インデックスを二分探索で求めることができる．

エリア 3 の開始インデックスが求められたら，エリア 2 とエリア 3 が同じ長さになるようにエリア 2 の開始インデックスを求める．ただし例外として，カードの枚数が奇数でエリア 3 の長さが$ \lceil \frac{N}{2} \rceil$の場合のみエリア 2 よりエリア 3 が 1 短い．

エリア 2 とエリア 3 の開始インデックスが求められたので，あらかじめ計算しておいた累積和を使って高橋くんのカードの数字の合計を求めることができる．エリア 3 の開始インデックスを求める二分探索の中で，青木くんから見たカードの優先順位を調べるためにまた二分探索をしているので空間計算量は $ O(N (\log N)^2)$ といったところか．

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

int main() {
    int n,m;
    cin >> n >> m;
    vector<int> a(n+1, -(1 << 30));
    for(int i=1;i<=n;++i) cin >> a[i];

    vector<vector<ll>> total(2, vector<ll>(n+1, 0)); // インデックスが偶数の累積和，インデックスが奇数の累積和
    total[1][1] = a[1];
    for(int j=2;j<=n;++j) {
        total[j%2][j] = total[j%2][j-2] + a[j];
        total[1-j%2][j] = total[1-j%2][j-1];
    }


    int q;
    for(int i=0;i<m;++i) {
        cin >> q;

        // 青木くんが最初に取るカードのインデックス
        int nearest_i = distance(a.begin(), lower_bound(all(a), q));
        if(abs(a[nearest_i-1]-q ) <= abs(a[nearest_i]-q)) {
            --nearest_i;
        }

        // 青木くんと高橋くんの戦略が一致
        if(nearest_i >= n) {
            cout << total[n%2][n] << endl;
            continue;
        }

        // 高橋くん区間の開始インデックスを探索
        int ng = nearest_i, ok = n;
        int mid = n;
        while(ok-ng > 1) {
            mid = (ng+ok)/2;
            // 青木くんと高橋くんそれぞれから見た a[mid] の優先順位
            int aoki_rank = mid - distance(a.begin(), lower_bound(all(a), q - (a[mid]-q))) + 1;
            int takahashi_rank = n - mid + 1;
            if(aoki_rank < takahashi_rank) {
                ng = mid;
            } else {
                ok = mid;
            }
        }
        int aoki_left = n - (n-ok+1)*2 + 1;

        cout << (aoki_left?total[1-aoki_left%2][aoki_left-1]:0) + total[0][n]+total[1][n]-total[0][ok-1]-total[1][ok-1] << endl;
    }
}

所感

水曜日からずっと悩んでいた問題だが，考察でわかったことを素直に実装すれば案外素直な問題だった．

NoiminのNoise

エイシングプログラミングコンテスト 2019 D - Nearest Card Game

問題概要

解法概要

ソースコード

所感