torus711 のアレ

主に競技プログラミングの問題について書きます

Codeforces #173, C : XOR and OR

概要

'0' と '1' からなる文字列について、次のような変換ができる。

  • 隣り合う二文字について、その xor と or の結果でその二文字を置き換える(順番は問わない)

二つの文字列 a, b が与えられる。
この操作を任意の回数行うことで a から b に変換できるかを判定せよ。

解法

まず、xor と or について、その入出力表を考えます。

in1 in2 xor or
0 0 0 0
0 1 1 1
1 0 1 1
1 1 0 1

表より、1 が一つでもあれば 00 を除き任意の形に相互変換が可能であることがわかります。
また、1 を一つずつ動かしていくことで任意の場所に 1 を作れます。

この事実より、次のいずれかの条件に当てはまらない場合は a から b に変換可能であると言えます。

  • a と b の長さが違う
  • a の長さが 1 であるか、a に '1' が含まれない場合で、a と b が異なる
  • a に '1' が含まれ b には含まれない

コード

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

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

	string a, b;
	cin >> a >> b;

	cout << ( a.size() != b.size() ||
			  ( a.size() == 1 || !count( ALL( a ), '1' ) ) && a != b ||
			  count( ALL( a ), '1' ) && !count( ALL( b ), '1' )
			  ? "NO" : "YES" ) << endl;

	return 0;
}