概要
'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; }
