AOJ 2894 - Aizu Competitive Programming Camp 2018 Day 3 F 01 文字列と窓 (Binary String with Slit
解法
サンプルの最後のケースで実験をすると、なんとなく見えてきます。
まず、移動の手段をすべて書くと、
01 → 10
10 → 01
10 → 11
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; }