Codeforces #180 Div1. A. Parity Game

CF180は不参加なので、後日練習。
http://codeforces.com/contest/297/problem/A

問題

01で構成された文字列に対し、以下の２種類の処理を行える。

• 最後にパリティとして0か1を加える。加える文字は、全体の1の数が偶数となるようにする。
• 先頭の文字を消す。

２つの文字列が与えられたとき、前者に上記２つの処理を繰り返して、後者を構築できるか答えよ。

解法

1の数が奇数の時、パリティとして1を１つだけ追加できる。
1の数が偶数のときはそれ以上追加できない。
また、1の数を偶数にした状態なら0はいくらでも追加できる。

よって、両者の文字の1の数を加え、前者の数が奇数なら1追加して、前者の方が1の数が大きければ構築可能となる。

char A[100002],B[100002];

void solve() {
	int f,r,i,j,k,l,x,y;
	
	GETs(A);
	GETs(B);
	j=k=0;
	FOR(i,strlen(A)) j+=A[i]-'0';
	FOR(i,strlen(B)) k+=B[i]-'0';
	j+=j%2;
	if(j>=k) _P("YES\n");
	else _P("NO\n");
	return;
}

まとめ

気づいてしまえばコード自体は単純だね。