Codeforces #378 Div2 C. Epidemic in Monstropolis

2:30はやめてほしいなぁ。
http://codeforces.com/contest/733/problem/C

問題

N要素の数列Aが与えられる。
２つの隣接する要素のうち、大小差があるなら大きい方が小さい方を併合し、和となる1要素に入れ替えることができる、とする。
別の数列Bが与えられるので、AをBに変形できるか、できるならその手段を答えよ。

解法

まずAの要素を何個ずつ合わせた部分列がBの各要素になるか求める。
後は各部分列について、変形で1要素に出来るか求めていく。
自分は愚直に部分列に対するメモ化再帰で、分割位置を総当たりして２つの部分列に分けられるかを判定した。
そのためO(N^3)解法。

O(N^2)でもできるかもしれないけど、色々コーナーケースが怖い。

int N;
int A[1010];
int K;
int B[1010];
int TA,TB;
int S[501];
int sum[501];
int can[501][501];

vector<pair<int,char>> R;


int dodo(int L,int R) {
	int i;
	
	if(can[L][R]!=-1) return can[L][R];
	if(L==R) return L;
	can[L][R]=-2;
	
	for(i=L;i<=R;i++) {
		if(dodo(L,i)>=0 && dodo(i+1,R)>=0 && sum[i+1]-sum[L]!=sum[R+1]-sum[i+1]) {
			can[L][R]=i;
			break;
		}
	}
	return can[L][R];
}

void gogo(int L,int R) {
	if(L==R) return;
	int X=can[L][R];
	gogo(X+1,R);
	gogo(L,X);
	if(sum[X+1]-sum[L]>sum[R+1]-sum[X+1]) {
		_P("%d R\n",L+1);
	}
	else {
		_P("%d L\n",L+2);
	}
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i], sum[i+1]=sum[i]+A[i];
	cin>>K;
	FOR(i,K) cin>>B[i], TB+=B[i];
	
	if(sum[N]!=TB) return _P("NO\n");
	x=0;
	FOR(i,K) {
		S[i+1]=S[i]+1;
		while(sum[S[i+1]]-sum[S[i]]<B[i]) S[i+1]++;
		if(sum[S[i+1]]-sum[S[i]]>B[i]) return _P("NO\n");
	}
	
	MINUS(can);
	for(i=K-1;i>=0;i--) if(dodo(S[i],S[i+1]-1)==-2) return _P("NO\n");
	
	_P("YES\n");
	for(i=K-1;i>=0;i--) gogo(S[i],S[i+1]-1);
	
}

まとめ

3問目で2000ptか…。