AISing Programming Contest 2019 : D - Nearest Card Game

全完は全完だけど色々手間取りすぎ。
https://atcoder.jp/contests/aising2019/tasks/aising2019_d

問題

N毎のカードがあり、それぞれ異なる数値A[i]がある。
２人でこれらを取り合うゲームを考える。
両者以下のアルゴリズムでカードを取る。

• 先手は常に残ったカードのうち最大の数値の物を取る。
• 後手は、ある定数Xに対し、もっとも近い数値のカードを取る(同着で2枚あるなら小さい方を取る)

Xが何通りか与えられる。
それぞれ先手が取るカードの数値の総和を答えよ。

解法

カードの取り方は以下のようになる。

• 先手が上位p枚を取る
• 後手が続きp枚を取る
• 残りは先手と後手が交互に取る。

よって、カードの数値の累積和と、1枚置きの累積和を事前に求めておけば、あとはpを求めれば解がわかることになる。
pは二分探索で求める。
先手はA[N-p]～A[N-1]までを取るとすると、A[N-2p]～A[N-p-1]が[X-(A[N-p]-X),X+(A[N-p]-X)]の範囲にあればよい。

int N,Q;
ll A[101010];
ll S[101010];
ll T[101010];
ll X;

int ok(int v) {
	if(v>N) return 0;
	
	int aa=(v+1)/2;
	int re=N-aa;
	int x=lower_bound(A,A+N,X-(A[re]-X))-A;
	return (x+v<=N);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) {
		cin>>A[i];
		S[i+1]=S[i]+A[i];
		T[i+1]=(i>=1?T[i-1]:0)+A[i];
	}
	
	while(Q--) {
		cin>>X;
		int turn=0;
		for(i=20;i>=0;i--) {
			if(ok(turn+(1<<i))) turn+=1<<i;
		}
		
		int a=(turn+1)/2;
		if(turn%2) turn++;
		
		ll ret=S[N]-S[N-turn/2];
		if(turn<N) ret+=T[N-turn];
		
		cout<<ret<<endl;
	}
}

まとめ

本番pを求めるのにlog^2(N)かけてしまいTLEした。