kmjp's blog

競技プログラミング参加記です

Codeforces #330 Div1 A. Warrior and Archer

割と良問の気配だっただけにもったいない。
http://codeforces.com/contest/594/problem/A

問題

N個(偶数)の整数A[i]が与えられる。

2人プレイヤーは、これらの要素を交互に1個ずつ消していく。
最終的に数値が残り2個になるまで要素を消して行き、最終スコアは残った2要素の値の差の絶対値となる。
先手はスコアを最小化、後手は最大化したい場合、最終的なスコアはどうなるか答えよ。

解法

双方(N-2)/2個の要素を消すことができる。
後手は連続した(N-2)/2個の要素を消すことで、先手が残りをどう消してもその(N-2)/2個の要素の両隣に残る要素の差以上のスコアを得られる。
よって、Aをソートし、A[i+(N-2)/2+2]-A[i]が最大となるiを総当たりすると良い。

int N;
ll X[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>X[i];
	sort(X,X+N);
	
	int del=N-2;
	int A=(del+1)/2,B=del/2;
	ll ma=1LL<<61;
	FOR(i,N) if(i+B+1<N) ma=min(ma,X[i+B+1]-X[i]);
	cout<<ma<<endl;
	
}

まとめ

Nが奇数だと、最後に先手が処理できるので問題がややこしくなる、ってことでいいのかな?

広告を非表示にする