CODE THANKS FESTIVAL 2018 : H - Median Game

ほんとAtCoderは中央値の問題が多いなぁ。
https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/tasks/code_thanks_festival_2018_h

問題

N枚のカードが並んでおり、各カードの値A[i]が与えられる。
このカードを使い2人でゲームを行う。

2人は交互にカードの端からカードを1枚以上何枚か選び抜き出す、ということを行う。
そして、抜き出したカード群それぞれの総和を求め、カード群におけるその中央値がゲームのスコアとなるものとする。

先手はスコアを最大化、後手は最小化しようとするとき、最終スコアはいくつになるか。

解法

中央値に関する問題の定番テクとして、スコアを二分探索しよう。
先手はスコアをX以上にしようとし、後手はX未満にするとする。

その場合、総和のX以上のカード群が半数以上となるXの最大値を求めよう。
dp(n,0) := 先手がカード残りn枚の状態で(X以上のカード群)-(X未満のカード群)を最大いくつにできるか
dp(n,1) := 後手がカード残りn枚の状態で(X未満のカード群)-(X以上のカード群)を最大いくつにできるか

dp(0,0)=dp(0,1)=0から、順にテーブルを埋めていくと、dp(N,0)が0以上かどうか判定することで条件を満たせるか判断できる。

int N;
int A[1010];
ll S[1010];
int dp[2][5050];

int ok(ll v) {
	int i,j;
	FOR(i,N) dp[0][i]=dp[1][i]=-5050;
	dp[0][N]=dp[1][N]=0;
	for(i=N-1;i>=0;i--) {
		for(j=i+1;j<=N;j++) {
			dp[0][i]=max(dp[0][i],-dp[1][j]+((S[j]-S[i]>=v)?1:-1));
			dp[1][i]=max(dp[1][i],-dp[0][j]+((S[j]-S[i]>=v)?-1:1));
		}
	}
	return dp[0][0]>=0;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		S[i+1]=S[i]+A[i];
	}
	
	ll X=-1LL<<59;
	for(i=59;i>=0;i--) if(ok(X+(1LL<<i))) X+=1LL<<i;
	cout<<X<<endl;
}

まとめ

Gより難しくない？