Codeforces #180, Division 2, C : Parity Game

問題文

http://codeforces.com/contest/298/problem/C

概要

'0' と '1' からなる文字列に対し、以下のような変換ができる

• 文字列の末尾に対し、その文字列のパリティを付加する。パリティは、文字列中の 1 の数が奇数なら 1 、偶数なら 0
• 文字列の先頭の一文字を消去する

二つの文字列 a, b が与えられるので、任意回の変換の適用によって、a から b に変換できるかどうか判定せよ。

解法

各変換について考察します。
パリティが 1 のとき、一つの 1 を付加するとパリティが 0 になります。
パリティが 0 のとき、付加される文字は 0 なのでパリティは変化しません。
文字を削除するとき、1 を削除したときだけパリティが変わります。
1 を付加したあと、再び 1 を挿入するためには、1 を削除しなければなりません。
よって、a に含まれる 1 の数 + a のパリティ 個を超える 1 を含む文字列は生成できません。
それ以外のとき、0 を任意の場所に任意の数挿入することができるので、必ず変換可能となります。

コード

#define ALL( c ) (c).begin(), (c).end()

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	string a, b;
	cin >> a >> b;
	
	int c1 = count( ALL( a ), '1' ), c2 = count( ALL( b ), '1' );
	cout << ( c1 + c1 % 2 < c2 ? "NO" : "YES" ) << endl;

	return 0;
}