yukicoder : No.1925 悪鬼三七次元

こういう問題、なかなか本番中に詰め切れないんだよな…。
https://yukicoder.me/problems/no/1925

問題

1次元の数直線上に(N+1)個の壁があり、それぞれの座標X[i]が与えられる。
この壁を、先手後手交互に1つずつ破壊していくゲームを考える。
最後、壁が2個になった時点で、その距離がこのゲームのスコアとなる。

先手はスコアを最大化、後手は最小化しようとしたとき、最終的なスコアを求めよ。

解法

後手は内側の壁を残すために外側から壁を壊そうとする。

• Nが偶数の場合
  • (1+i+N/2)番目とi番目の壁を残すことで、(X[1+i+N/2]-X[i])の最小値が解となる。
  • 先手は両壁の内側の壁、後手は外側の壁を壊すのが最適。
  • もし先手がその他を壁を壊すと、(1+i+N/2)番目とi番目より内側の壁が残り、スコアが減ってしまうので、そんなことはしない。
  • もし後手がその他を壁を壊すと、(1+i+N/2)番目とi番目より外側の壁が残り、スコアが増えてしまうので、そんなことはしない。
• Nが奇数の場合
  • 後手が(N-1)/2回壁を壊し、残された(N+1)/2個の区間ができると、先手はそのうち最大区間を残すことができる。
  • 後手はその最大区間を最小化しようとしてくる。
  • よって、長さL以上の区間が(N+1)/2個以上取れるような最大のLが解となる。

int N;
ll X[101010];

int hoge(ll v) {
	ll pre=0;
	int num=0;
	int i;
	for(i=1;i<=N;i++) {
		if(X[i]-pre>=v) {
			num++;
			pre=X[i];
		}
	}
	return num;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		X[i+1]=X[i]+x;
	}
	
	if(N%2==0) {
		ll mi=1LL<<60;
		for(i=0;i+N/2+1<=N;i++) mi=min(mi,X[i+N/2+1]-X[i]);
		cout<<mi<<endl;
	}
	else {
		ll ret=0;
		for(i=50;i>=0;i--) if(hoge(ret+(1LL<<i))>=(N+1)/2) ret+=1LL<<i;
		cout<<ret<<endl;
	}
}

まとめ

偶奇でここまで戦略が変わるゲームのも珍しいかも。