Codeforces #222 Div1. C. Captains Mode

アプローチミスやらMLEやらしてもったいなかったけど、何とか本番に解ききった。
http://codeforces.com/contest/377/problem/C

問題

N人のプレイヤーがおり、その強さはS[i]である。
これらのプレイヤーをチーム１とチーム２の２チームで分けるが、その分け方は以下のとおりである。

• 両チームの取れる手順は事前に決められているが、その対象となるプレイヤーは選択可能である。
  • 手順pickでは、任意のプレイヤーを自分のチームに入れられる。
  • 手順banでは、任意のプレイヤーを利用不可能にできる。

一度pickまたはbanされたプレイヤーは以後選択できない。
両チームが最適手を取ったとき、チームの強さをプレイヤーの強さの総和としたとき、チーム１とチーム２の強さの差の最大値を答えよ。

なお、この問題は「チームキャプテンがmissするかも…」という文面が入っているが、解答にまったく関係ないようだ。

解法

手順をM手とすると、両チームともN人中上位M人しか選択しないので、S[i]をソートして以後上位M人だけ考える。
どのM人か選択済みかをbitmaskで持ち、チーム１は差を最大化、チーム２は差を最小化するよう各処理を後ろからバックトラックしていく。

int N,M;
ll S[1001];
string cm[100];
int ct[100];

ll dpdp[2][1<<21];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) cin>>S[i];
	cin>>M;
	
	sort(S,S+N);
	reverse(S,S+N);
	
	FOR(j,1<<M) dpdp[0][j]=-1LL<<60;
	dpdp[0][0]=0;
	FOR(i,M) cin>>cm[M-1-i]>>ct[M-1-i];
	FOR(i,M) {
		int cur=i%2,tar=cur^1;
		
		FOR(j,1<<M) dpdp[tar][j]=-1LL<<60;
		
		FOR(j,1<<M) {
			if(dpdp[cur][j]==-1LL<<60) continue;
			FOR(x,M) if((j&(1<<x))==0) {
				ll mm = dpdp[tar][j|(1<<x)];
				if(ct[i]==1) {
					if(cm[i][0]=='p') mm=max(mm,dpdp[cur][j] + S[x]);
					else mm=max(mm,dpdp[cur][j]);
				}
				else if(ct[i]==2) {
					if(mm==-1LL<<60) mm=1LL<<60;
					if(cm[i][0]=='p') mm=min(mm,dpdp[cur][j] - S[x]);
					else mm=min(mm,dpdp[cur][j]);
				}
				dpdp[tar][j|(1<<x)] = mm;
			}
		}
	}
	
	ll ret=-1LL<<60;
	FOR(i,1<<M) ret=max(ret,dpdp[M%2][i]);
	cout << ret << endl;
}

まとめ

後ろからやればよいってことに最初気づかず、前からやってpretest失敗していた。
オセロと同じで、先読みして最大化・最小化するのだから後ろからやるのは当然か。
本番中に気づけて良かった。