けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Codeforces Manthan Codefest 18 (Div. 1 + Div. 2) C. Equalize (R1300)

超苦手系。なんとか解けた。

問題へのリンク

問題概要

長さ 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;
    }
}