🦔

AGC 049 | B - Flip Digits

2020/12/17に公開

競プロ

tech

問題

解法

以下のパターンのみ変更できる。右のパターンに注目すると、1を左に移動できる。

1を右には移動できないので左から順に条件を満たすようにしていけばよい。

$S_i$ と $T_i$ が異なるとき以下のようにすると $S_i = T_i$ とすることができる。

どちらの場合も $i$ より右から1をもってきてその後変更すればいい。このとき $i$ の右に1がない場合は $S = T$ にすることは不可能である。

コード

実装時のTips

$j$ で $i$ より右側の1の位置を記憶している。これをしないとTLEしてしまう。

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

// 1は増やせない
// 01 => 10, 11 => 00
//
// 左から揃えていく.
// 以下は何もしない
// 0 or 1
// 0    1
// 以下は右に1をもってくる
// 1 or 0
// 0    1
int main() {
  ll n;
  string s, t;
  cin >> n >> s >> t;
  ll ans = 0;
  ll i = 0;
  ll j = 0;  // 一番左の1
  while (i < n) {
    if (s[i] == t[i]) {
      i++;
      continue;
    }
    // 右から1をもってくる
    j = max(j, i + 1);
    while (true) {
      if (j == n) {
        cout << -1 << endl;  // もう何もできない
        return 0;
      }
      if (s[j] == '1') break;
      j++;
    }
    if (j != i + 1) {
      swap(s[j], s[i + 1]);
      ans += j - (i + 1);
    }
    if (s[i] == '1') {
      s[i] = s[i + 1] = '0';
    } else {
      s[i] = '1';
      s[i + 1] = '0';
    }
    ans++;
    i++;
  }

  cout << ans << endl;
}

AGC 049 | B - Flip Digits

問題

解法

コード

参考

Discussion