Croc Champ 2013 - Round 2 : A. Weird Game

今さらながらCROC Round2。本番は１問しか解けなかったけど妙にレートが上がった。
ではCまで復習。
http://codeforces.com/contest/293/problem/A

問題

2つの0・1が2N個ならなる文字列が与えられる。
この文字列を使って２人のプレイヤーがゲームをする。
各プレイヤーは交互に自分の文字列中の１文字を選択すると、その数字の分のスコアが得られる。
どちらかのプレイヤーが一度指定したのと同じ位置の文字は両文字列とも選択できない。

両者が最善手を取った場合、勝者が先手か後手か答えよ。

解法

互いに自分が最大限に得するように動くと、以下の基準で文字を選択する。

• 自分は点を稼いで相手には稼がせたくないので、まず自分も相手も１の場所を選ぶ。
• 次に自分が稼ぐために、自分が１で相手が０の場所を選ぶ。
• 次に、相手に稼がせないために自分が０で相手が１の場所を選ぶ。
• 最後に、余った両者０の場所を選ぶ。

上記処理をNターン繰り返せばよい。

int N;
char A[2000020];
char B[2000020];
int NN[2][2];


void solve() {
	int r,i,j,k,l,x,y;
	
	N=GETi();
	GETs(A);
	GETs(B);
	
	ZERO(NN);
	FOR(i,2*N) NN[A[i]-'0'][B[i]-'0']++;
	FOR(i,N) {
		// A
		int AP=0;
		if(NN[1][1]) { NN[1][1]--; AP=1;}
		else if(NN[1][0]) { NN[1][0]--; AP=1;}
		else if(NN[0][1]) { NN[0][1]--;}
		else NN[0][0]--;
		
		int BP=0;
		if(NN[1][1]) { NN[1][1]--; BP=1;}
		else if(NN[0][1]) { NN[0][1]--; BP=1;}
		else if(NN[1][0]) { NN[1][0]--;}
		else NN[0][0]--;
		
		if(AP>BP) {
			_P("First\n");
			return;
		}
		if(AP<BP) {
			_P("Second\n");
			return;
		}
	}
	_P("Draw\n");
	return;
}

まとめ

最善手に気が付けばコードは簡単。