超苦手系。なんとか解けた。
問題概要
長さ N のバイナリ列 a, b が与えられる。a に対して
- 隣接二項を swap する
- 0 と 1 を反転する
の操作を最小回数行って b にせよ。(10 -> 01 なら 1、1000 -> 0001 なら 2)
制約
- 1 <= N ,= 106
考えたこと
a の 1 と b の 1 をマッチングさせるような問題である。数が合わないところや、離れている 1 のところは反転したりする。
- 1 を 2 マス分以上移動させる意味はない
- a[i] = b[i] = 1 となっている i については、両方 0 であると思って差し支えない。
ということが言えるので、後者の作業後に、距離 1 の 1 同士は結び付けて、それ以外の 1 は反転で対処する。
#include <iostream> #include <string> using namespace std; int main() { int n; string a, b; while (cin >> n >> a >> b) { int res = 0; for (int i = 0; i < n; ++i) { if (a[i] == '1' && b[i] == '1') { a[i] = '0'; b[i] = '0'; } } for (int i = 0; i < n; ++i) { if (a[i] == '1') { if (b[i] == '1') continue; else if (i+1 < n && b[i+1] == '1') { ++res; a[i] = '0'; b[i+1] = '0'; } else { ++res; a[i] = '0'; } } if (b[i] == '1') { if (a[i] == '1') continue; else if (i+1 < n && a[i+1] == '1') { ++res; b[i] = '0'; a[i+1] = '0'; } else { ++res; b[i] = '0'; } } } cout << res << endl; } }