AUPC 2018 day3 F: Binary String with Slit

問題

01からなる文字列が与えられる。
文字列に対して次の操作を好きなだけ行える。
文字列の一番右の'1'を含む連続する二文字の部分文字列を

• 11は10に
• 10は11か01に
• 01は10に

することができる。
文字列S, Tが与えられたとき、SをTに最低何回の操作で変えられるか。

制約

S, Tの長さは50以下で、それが10^5個以下与えられる。
S, Tは0,1からなり、ともに少なくとも一つの1を含む。

方針

一番右の1とその両隣しか操作できないので、
S, Tのうち異なる場所のうち一番左まで0にして100....0000のようにしないといけない。
その後は1を右に動かしていく。
前半は一回の操作で1文字消えて、後半は一回の操作で1文字確定するので明らかにこれが最適。
なので愚直に頭の中か紙の上でシミュレーションする。

ソースコード

int solve(){
	string s, t; cin >> s >> t;
	int n = s.size();
	int p = 0, s1 = n - 1, t1 = n - 1;
	for(; p < n && s[p] == t[p]; p++);
	if(p == n) return 0;
	for(; s1 >= 0 && s[s1] == '0'; s1--);
	for(; t1 >= 0 && t[t1] == '0'; t1--);
	
	if(s1 < p) return t1 - s1;
	if(t1 < p) return s1 - t1;
	if(s1 == p) return t1 - s1;
	int ans = s1 - p - 1;
	if(t1 == p) return ans + 1;

	ans += 2;
	ans += t1 - p - 1;
	return ans;
}
int main() {
	cin.tie(0); cin.sync_with_stdio(0);
	int q; cin >> q;
	while(q--){
		cout << solve() << endl;
	}
	return 0;
}