kmjp's blog

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

Codeforces #325 Div1 D. Lizard Era : Beginning

こちらはCよりシンプル。本番思い浮かばなかったことを反省したい。
http://codeforces.com/contest/585/problem/D

問題

N個のクエストがある。
3人のプレイヤーは各クエストを攻略するとそれぞれL[i],M[i],W[i]のスコアを得られる。
ただし各クエストはちょうど2人挑戦しなければならない。

各人の合計スコアが同じになるような挑戦の仕方の組み合わせは存在するか。
存在するならそのうち最高スコアのものを求めよ。

解法

O(3^N)では間に合わない。
そこで半分全列挙しよう。

L,M,Wの和が等しくなるようにしたいので、(M-L)、(W-L)の和をそれぞれ0にすることを考える。

まずN個のうち前半半分について、mapを用いてA[sum(M)-sum(L),sum(W)-sum(L)] := (sum(L)の最大値) をDPで求める。
同様に後半半分についてB[sum(L)-sum(M),sum(L)-sum(W)] := (sum(L)の最大値)
(当然「sum(L)の最大値」を達成する挑戦の仕方も覚えておく)

あとはAとBで同じkeyを持つものの和を取れば合計のLの最大値が求まる。

int N;
int A[3][30];
ll p3[30];
map<pair<int,int>,pair<int,ll> > M[2];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	p3[0]=1;
	FOR(i,N) p3[i+1]=p3[i]*3;
	FOR(i,N) cin>>A[0][i]>>A[1][i]>>A[2][i];
	
	for(ll mask=0;mask<p3[min(N,13)];mask++) {
		int t[3]={},tm=mask;
		FOR(i,min(N,13)) {
			x=tm%3, tm/=3;
			if(x==0) t[0]+=A[0][i],t[1]+=A[1][i];
			if(x==1) t[0]+=A[0][i],t[2]+=A[2][i];
			if(x==2) t[1]+=A[1][i],t[2]+=A[2][i];
		}
		M[0][{t[0]-t[1],t[0]-t[2]}]=max(M[0][{t[0]-t[1],t[0]-t[2]}], {t[0]+(1LL<<29),mask});
	}
	for(ll mask=0;mask<p3[max(0,N-13)];mask++) {
		int t[3]={},tm=mask;
		FOR(i,max(0,N-13)) {
			x=tm%3, tm/=3;
			if(x==0) t[0]+=A[0][13+i],t[1]+=A[1][13+i];
			if(x==1) t[0]+=A[0][13+i],t[2]+=A[2][13+i];
			if(x==2) t[1]+=A[1][13+i],t[2]+=A[2][13+i];
		}
		M[1][{t[1]-t[0],t[2]-t[0]}]=max(M[1][{t[1]-t[0],t[2]-t[0]}], {t[0]+(1LL<<29),mask*p3[13]});
	}
	
	ll co=-1LL<<40;
	ll best=-1;
	FORR(r,M[1]) if(M[0].count(r.first) && r.second.first+M[0][r.first].first>co) {
		co=r.second.first+M[0][r.first].first;
		best = r.second.second+M[0][r.first].second;
	}
	
	if(best==-1) _P("Impossible\n");
	else {
		FOR(i,N) {
			x=best%3;
			best/=3;
			if(x==0) _P("LM\n");
			if(x==1) _P("LW\n");
			if(x==2) _P("MW\n");
		}
	}
}

まとめ

半分全列挙は少し考えたものの、こういうkeyの摂り方を思いつけなかったのが反省。