全完は全完だけど色々手間取りすぎ。
https://atcoder.jp/contests/aising2019/tasks/aising2019_d
問題
N毎のカードがあり、それぞれ異なる数値A[i]がある。
2人でこれらを取り合うゲームを考える。
両者以下のアルゴリズムでカードを取る。
- 先手は常に残ったカードのうち最大の数値の物を取る。
- 後手は、ある定数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した。