丁寧に考えれば解ける感じ
問題概要
0 と 1 のみかならなる長さ N のビット列 S, T が与えられる。S に以下の操作を好きな回数だけ行って T にするのに必要な最小回数を求めよ。 (というクエリが Q 回投げられる)
- S の最も右にある 1 を含む連続 2 マスについて、
- それが 01 なら、10 に変形できる
- それが 10 なら、01 か 11 に変形できる
- それが 11 なら、10 に変形できる
制約
- 1 <= Q <= 105
- 2 <= |S| = |T| <= 50
考えたこと
こういうのは操作が何を意味しているのかを整理するのがよさそう。今回の操作は、
- S の最も右にある 1 を左に動かして、動かされた後のところはすべて 0 にする
- S の最も右にある 1 を右に動かして、動かされた後のところはすべて 0 にも 1 にもできる
という操作だと思うことができる。基本的には「最も右にある」1 にしか作用できないので、S と T がかなり左の方で異なっていたら、S の右側にある 1 を一端左に動かす必要がありそう。
自分が考えたのは、S と T を左から見て行って、最初に S[i] != T[i] となる index i をとってきたときに、
- j > i なる j があって S[j] = '1' のときは、S の最右の 1 を index i まで移動させて、その後それを T の最右の 1 まで移動させればいい (経路の 0 or 1 はよしなにできる)
- そうでないとき、S の最右の 1 (i より前) を、T の最右の 1 まで移動させればいい
という風に考えてコードを書いて、AC をもらえた。結局 S の最右の 1 を動かしていることには変わりないので、もう少し整理できるかもしれない。
#include <iostream> #include <string> using namespace std; int main() { int Q; cin >> Q; for (int _ = 0; _ < Q; ++_) { int res = 0; string S[2]; cin >> S[0] >> S[1]; if (S[0] == S[1]) { cout << 0 << endl; continue; } int n = S[0].size(); int ichi = 0; int zerogawa = 0; bool allzero = true; for (int i = 0; i < n; ++i) { if (S[0][i] != S[1][i]) { ichi = i; break; } } if (S[0][ichi] == '0') zerogawa = 0; else zerogawa = 1; for (int i = ichi; i < n; ++i) { if (S[zerogawa][i] == '1') allzero = false; } if (allzero) { int first = 0; for (int i = ichi; i >= 0; --i) { if (S[zerogawa][i] == '1') { first = i; break; } } ichi = first; } for (int iter = 0; iter < 2; ++iter) { int second = ichi; for (int i = ichi; i < n; ++i) { if (S[iter][i] == '1') { second = i; } } res += second - ichi; } cout << res << endl; } }
