ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AOJ 2894 - Aizu Competitive Programming Camp 2018 Day 3 F 01 文字列と窓 (Binary String with Slit

問題

解法

サンプルの最後のケースで実験をすると、なんとなく見えてきます。
まず、移動の手段をすべて書くと、

  1. 01 → 10

  2. 10 → 01

  3. 10 → 11

  4. 11 → 10

の4通りしか存在しません。
そして、SとTが一致していない、一番左側の部分を一致させるには、それより右側にある1のビットを、全て消去する必要があります。
1を消去するには、4つめのパターンを使用する以外に方法がありません。
そして、4つめのパターンを使用するには、一番右側の1を、左にシフトする必要があり、これはパターン1を使用する以外に方法が存在しません。
ということで、まずはパターン1と4を駆使することで、SとTのズレの一番左側に移動する必要があります。

上の動作が終了すると、あとは右側に移動して、SとTのズレを修正していく必要があります。
今度は、パターン2とパターン3を使用して、1を右に移動させつつ、必要な数だけ1を増やすことになります。
これをサンプルケースの一番最後と照らし合わせると、ちょうど答えと一致します。
また、処理の前半部分は、

  • (Sの中で最も右側にある1の位置) - (SとTのズレの中で最も左側にあるもの)

が処理回数の最小値になり、後半部分は

  • (Tの中で最も右側にある1の位置) - (SとTのズレの中で最も左側にあるもの)

が処理回数の最小値になります。
SとTのズレの中で最も左側にあるものをa、
Sの中で最も右側にある1の位置をb、
Tの中で最も右側にある1の位置をcとしたとき、

  • b + c - 2×a

が答えになります。
が、このままではコーナーケースが2パターン存在します。
一つ目が、
S = 011000
T = 010001
という、右に1を移動させるだけで完了するパターン、
二つ目が、
S = 010001
T = 010000
という、左に1を移動させるだけで完了するパターンです。
先ほどの基本方針をそのままに、この2パターンも対処できるように式を書き直すと、

  • max(b-a,0) + |c-min(a,b)|

となります。
あとは、a、b、cをそれぞれ求めて、答えをクエリごとに出力していけば、無事にACすることができます。
提出コードはこちらになります。

#include <bits/stdc++.h>
#define inf 10000
using namespace std;

int a, b, c, q, x, y;
string s, t;

int main() {
  cin >> q;
  while(q--) {
    a = inf;
    cin >> s >> t;
    for(int i = 0; i < s.size(); ++i) {
      if(s[i] != t[i]) a = min(a, i);
      if(s[i] == '1') b = i;
      if(t[i] == '1') c = i;
    }
    if(a == inf)
      cout << 0 << endl;
    else {
      x = max(b - a, 0);
      y = c - min(a, b);
      if(y < 0) y *= -1;
      cout << x + y << endl;
    }
  }
  return 0;
}