AISing Programming Contest 2019：D - Nearest Card Game

結論

A の index は 0 始まりとします。また、以下で「左」や「右」と書いているのは、カードを $A_0$ から $A_{N-1}$ まで左から右へと並べた状況を想定しています。

N が偶数のとき

$B_p$ を以下で定義します
$B_p = \begin{cases} \text{inf} & (p=1) \\ A_{N-p} + A_{N-2p+1} &( 2 \leq p \leq N/2) \\ 0 &(p = N/2 + 1) \end{cases}$

このとき $B_{p+1} < 2x \leq B_p$ を満たす p が 1 つ存在し、高橋君が右から p 枚、青木君が続く p 枚を取り、残りは高橋君から始めて右から交互に取っていきます。

$B_p$ は減少列なので、このような p は二分探索で $O(\log N)$ で求められます。
また、高橋君が取ったカードの和は、累積和 $S_i = \sum_{k=0}^{i} A_k$ と、indexが偶数のみの和 $T_i = \sum_{k=0,\text{even}}^{i} A_k$ をあらかじめ計算しておくと、
$S_{N-1} - S_{N-p-1} + S_{N-2p-1} - T_{N-2p-1}$
で求められます。

クエリは $Q$ 個なので、累積和の計算もあわせて計算量は $O(N+Q\log N)$ となります。

N が奇数のとき

$B_p$ を以下で定義します
$B_p = \begin{cases} \text{inf} & (p=1) \\ A_{N-p} + A_{N-2p+1} &( 2 \leq p \leq (N+1)/2) \\ \end{cases}$

$B_{p+1} < 2x \leq B_p$ を満たす p が存在するとき、カードの取られ方は上記の N が偶数の場合と同様で、求める和は
$S_{N-1} - S_{N-p-1} + T_{N-2*p-1}$
です。

存在しないとき、高橋君が右の (N+1)/2 枚、青木君が左の (N-1)/2 枚を取ります。求める和は
$S_{N-1} - S_{(N-1)/2 - 1}$
となります。

ごちゃごちゃした説明

カードの取られ方

まずはカードがどのように取られていくかを把握したいです。
パターン(1)
高橋君は大きな値から順に、青木君は $x$ に近い値から順番に取っていくので、ゲーム開始からしばらくすると、高橋君がカードの右から p 枚を、青木君が続く p 枚を、それぞれ取った状況になります。その後は高橋君と青木君が交互に残ったカードの一番右を取っていきます。ここで、 p = 1 とすると下記のパターン(2)と一致してしまうので、ここでは p > 1 とします。
f:id:poporix:20190116233236p:plain
パターン(2)
$x$ が十分に大きな値のとき、高橋君と青木君は、右から順番に交互にカードを取っていくことになります。
パターン(3)
$x$ がもっと小さくなった場合、高橋君がカードの右から $N/2$ 枚を、青木君が左から $N/2$ 枚を取ります。 $N$ が偶数のときはこれで終了、 $N$ が奇数の場合は残ったカード $A_{N/2}$ を高橋君が取って終了となります。

パターン(1)の条件

パターン(1)となるのがどういう場合かを考察し、それが成り立たない場合として(2),(3)の場合を考えることにします。
まずは高橋君がカードの右から p 枚を、青木君が続く p 枚を、それぞれ取った状況(上図)です。 p > 1 に注意して下さい。

(i) 青木君が p 枚目に $A_{N-p-1}$ を取ったとき
このとき、青木君は x に最も近い p 枚のカードを取っており、その p 番目のカードとして $A_{N-p-1}$ を取っています。なぜなら、 $A_{N-p-1}$ より右や $A_{N-2p-1}$ より左にもっと x に近いカードがあれば、p - 1枚目までにそちらを先に取っているはずだからです。

・ $A_{N-2p}$ が $A_{N-p-1}$ よりも先に取られていることより、 $x - A_{N-2p} \leq A_{N-p-1}-x$ 。
・ p 枚目に $A_{N-2p-1}$ ではなく $A_{N-p-1}$ を取ったことから、 $A_{N-p-1} - x < x - A_{N-2p-1}$ 。

2つ合わせて、 $A_{N-p-1} +A_{N-2p-1} < 2x \leq A_{N-2p} + A_{N-p-1}$ となります。

ただし、N が偶数で p が N/2 の場合、上記の2つ目の条件は不要です。なぜなら、青木君が p 枚目のカードとして $A_{N-p-1}$ を取る時点で、残ったカードは $A_{N-p-1}$ しかないからです。よって、以下のように書けます。
$\begin{cases} &2x \leq A_{N-2p} + A_{N-p-1} & (N=\text{even},~p=N/2) \\ A_{N-p-1} +A_{N-2p-1} < &2x \leq A_{N-2p} + A_{N-p-1} & (\text{else}) \end{cases}$

(ii) 青木君が p 枚目に $A_{N-2p}$ を取ったとき
2 つの場合が考えられます。

(ii - 1) x に p 番目に近いカードとして $A_{N-2p}$ を取った場合
・ $A_{N-p-1}$ が $A_{N-2p}$ よりも先に取られていることより、 $A_{N-p-1}-x < x - A_{N-2p}$ 。
・ $A_{N-2p}$ が $A_{N-p-1}$ よりも x に近いことより、 $A_{N-p} - x \geq x - A_{N-2p}$ 。

二つ合わせて、
　　　 $A_{N-p-1} +A_{N-2p} < 2x \leq A_{N-2p} + A_{N-p}$

(ii - 2) p 番目に x に近いカード $A_{N-p}$ を高橋君にとられ、 $A_{N-2p}$ を取った場合
・ $A_{N-p-1}$ が $A_{N-2p}$ よりも先に取られていることより、 $A_{N-p-1}-x < x - A_{N-2p}$ 。
・ $A_{N-p}$ が $A_{N-2p}$ よりも x に近いことより、 $A_{N-p} - x < x - A_{N-2p}$ 。
・ $A_{N-2p+1}$ を $A_{N-p}$ よりも先に取ったことより、 $x - A_{N-2p+1} \geq A_{N-p} - x$ 。

以上3つを合わせて、以下のように書けます：
　　　 $A_{N-p} +A_{N-2p} < 2x \leq A_{N-p} + A_{N-2p+1}$

よって、高橋君と青木君が合わせて 2p 枚取った時点で、それらがカードの右 2p 枚であるための条件は、上記の (i) または (ii-1) または (ii-2) より、
$B_p = \begin{cases} 0 & (N=\text{even},~p=N/2+1) \\ A_{N-p} + A_{N-2p+1} & (\text{else}) \end{cases}$
と定義して、
　　　 $B_{p+1} < 2x \leq B_{p}~(2 \leq p \leq \text{floor}(N/2))$
と書けます。

パターン(2)の条件

青木君が最初に取るカードが $A_{N-2}$ となる条件と同じなので、 $2x > A_{N-3} + A_{N-2} = B_1$ が得られます。
従って、 $B_1 = \text{inf}$ として $B_2 < 2x \leq B_1$ の場合、と言い換えられます。

パターン(3)の条件

N が偶数の場合、パターン(1)でp=N/2とした場合に一致します。
N が奇数の場合、 $A_{(N-1)/2}$ は x に p + 1 番目に近い値となるので、x は $A_0$ と $A_{(N-1)/2}$ の平均値以下です。よって、 $p = (N-1)/2$ としたとき $2x \leq B_{p+1}$ と書けます。これは「(1)の条件を満たす p が存在しない場合」と言い換えられます。

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    int N, Q;  cin >> N >> Q;
    vector<ll> A(N), X(Q);
    for(int i=0; i<N; i++) cin >> A[i];
    for(int i=0; i<Q; i++) cin >> X[i];

    vector<ll> S(N), T(N);
    S[0] = A[0];  T[0] = A[0];
    for(int i=1; i<N; i++){
        S[i] = S[i-1] + A[i];
        T[i] = T[i-1];
        if(i%2==0) T[i]+=A[i];
    }

    int P = N/2+1;
    vector<ll> B(P+1);
    // B の値をあらかじめ計算しておく
    B[1] = 1e18;
    if(N%2==1) B[P] = A[N-P] + A[N-2*P+1];
    else B[P] = 0;
    for(int p=2; p<P; p++){
        B[p] = A[N-p] + A[N-2*p+1];
    }

    for(int i=0; i<Q; i++){
        ll x = X[i];
        if(2*x <= B[P]){ //不等式を満たす p が存在しないとき
            cout << S[N-1] - S[P-2] << endl;
        }else{
            int l = 1, r = P-1;
            int p = l + (r-l)/2;
            while(!(B[p+1] < 2*x && 2*x <= B[p])){ // 不等式を満たす p を二分探索
                if(B[p+1] >= 2*x) l = p + 1;
                else r = p;
                p = l + (r-l)/2;
            }

            if(N%2==0){
                cout << S[N-1] - S[N-p-1] + S[N-2*p-1] - T[N-2*p-1] << endl;
            }else{
                cout << S[N-1] - S[N-p-1] + T[N-2*p-1] << endl;
            }
        }
    }
}

競プロやります。

競プロを頑張るブログです。