Codeforces #380 Div1 D. Financiers Game

うーん…。
http://codeforces.com/contest/737/problem/D

問題

N個の整数列Aがある。
この整数列に対し２人で交互に数字を取り合うゲームを行う。

先手は初手、数列の先頭から1つか2つの要素をとる。
後手は数列の末尾から、先手のとった要素数またはそれに＋１した数の要素をとる。

以後、先手は数列の先頭、後手は末尾から、相手が直前とった要素数またはそれに＋１した要素をとることを繰り返す。
そのようなとり方ができなくなった場合ゲームは終了する。
それぞれ、とった要素の総和が自分のスコアとなる。
先手は（先手のスコア－後手のスコア）を最大化しようとし、後手は最小化しようとする場合、最終的なスコア差はいくつとなるか。

解法

状態として考えられるのは以下のとおりである。
f(先手がとった総要素数, 後手がとった総要素数, 手番, 相手が直前にとった要素数) := 以降のスコア差の最大値/最小値

この状態であるが、O(N^2.5)程度であり、Nが最大の4000でも600万程度しか状態がない。
よってうまくこれらの状態をメモリ上に格納すれば、単に総当たりするだけで解ける。
下手なメモリ配置をするとMLEするので注意。

以下のコードでは、先に両者のとった総要素数に対し、そのような状態に至る「相手が直前にとった要素数」の範囲を求め、状態をvectorに詰め込んでいる。

int N;
int A[4040];
ll S[4040];

int LL[4040][4040][2];
int RR[4040][4040][2];

vector<ll> memo;

void check(int L,int R,int K,int t) {
	if(R-L+1<K) return;
	if(LL[L][R][t]<=K && K<=RR[L][R][t]) return;
	LL[L][R][t]=min(LL[L][R][t],K);
	RR[L][R][t]=max(RR[L][R][t],K);
	if(t==0) {
		check(L+K,R,K,1);
		check(L+K+1,R,K+1,1);
	}
	else {
		check(L,R-K,K,0);
		check(L,R-(K+1),K+1,0);
	}
	
}

ll turn(int L,int R,int K,int t) {
	if(R-L+1<K) return 0;
	ll& ret=memo[(K-LL[L][R][t])+RR[L][R][t]];
	if(ret>-1LL<<60) return ret;
	
	if(t==0) {
		ret = turn(L+K,R,K,1) + S[L+K]-S[L];
		if(L+K+1<=R+1) ret = max(ret, turn(L+K+1,R,K+1,1) + S[L+K+1]-S[L]);
	}
	else {
		ret = turn(L,R-K,K,0) - (S[R+1]-S[R-K+1]);
		if(R-(K+1)>=L-1) ret = min(ret, turn(L,R-(K+1),K+1,0) - (S[R+1]-S[R-(K+1)+1]));
	}
	return ret;

}

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];
	}
	FOR(x,N) FOR(y,N) LL[x][y][0]=LL[x][y][1]=N+1;
	FOR(x,N) FOR(y,N) RR[x][y][0]=RR[x][y][1]=-1;
	check(0,N-1,1,0);
	
	int tot=0;
	FOR(x,N) FOR(y,N) FOR(i,2) {
		if(LL[x][y][i]<=RR[x][y][i]) {
			int num = RR[x][y][i]-LL[x][y][i]+1;
			RR[x][y][i]=tot;
			tot+=num;
		}
	}
	
	memo.resize(tot+5);
	FORR(r,memo) r=-1LL<<60;
	
	cout<<turn(0,N-1,1,0)<<endl;
}

まとめ

これはどういう問題なんだろう。状態を総当たりすればできてしまうので、いかにメモリに状態を乗せきるか？