Google Code Jam 2021 Round 1C : C. Double or NOTing

色々問題考えるなぁ。
https://codingcompetitions.withgoogle.com/codejam/round/00000000004362d7/00000000007c1139

問題

2進数表記された2つの整数S,Eがある。
Sに対し、以下の処理を繰り返しEにしたい。最小何回の処理で行えるか。

• Sを2倍にする
• Sの各桁を0/1反転させる。ただし、Sが正の時は反転前後でleading zeroは適宜削除する

解法

コーナーケースとして、S=Eの時は解0、S=0の時は初手反転としておく。
S,Eをそれぞれランレングス圧縮しよう。以後、0/1の区別は無視して、長さの配列(以下V,Wと表現する)とみなして考える。

そうすると、2つの処理は以下のように言い換えられる。

• Sを2倍にするのは、Vが奇数長なら[1]を末尾に追加、偶数長なら末尾の要素をインクリメント
• 反転は、Vの先頭要素の削除

Vのうち先頭k要素を、反転の繰り返しで切り飛ばし、その分後ろに(Sの倍加により)要素を付け加えることでWにすることを考える。
反転回数kを総当たりしよう。そうすると反転以外ではV末尾しかいじくれないので、対応するVとWの要素が一致しない場合は、条件を満たす処理手順がないことを意味する。

V

=

W

かつ

V

が奇数の時、

V

の末尾をインクリメントできないので注意。

string S,E;

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>S>>E;
	
	if(S==E) {
		_P("Case #%d: 0\n",_loop);
		return;
	}
	int ret=0;
	if(S=="0") S="1", ret++;
	vector<int> V={1},W={1};
	FOR(i,S.size()) if(i) {
		if(S[i]==S[i-1]) V.back()++;
		else V.push_back(1);
	}
	
	FOR(i,E.size()) if(i) {
		if(E[i]==E[i-1]) W.back()++;
		else W.push_back(1);
	}
	if(E=="0") {
		_P("Case #%d: %d\n",_loop,(int)V.size());
		return;
	}
	int mi=1<<20;
	for(i=0;i<=V.size();i++) {
		int over=i+W.size()-V.size();
		int can=i;
		if(V.size()%2==1) can++;
		if(over<0) continue;
		if(can<over) continue;
		int count=i+ret;
		FOR(j,W.size()) {
			if(i+j<V.size()) {
				if(V[i+j]!=W[j]) {
					if(i+j==V.size()-1&&(V.size()%2==0||V.size()>W.size())&&W[j]>=V[i+j]) count+=W[j]-V[i+j];
					else count+=1<<20;
				}
			}
			else {
				count+=W[j];
			}
		}
		mi=min(mi,count);
	}
	
	
	
	if(mi==1<<20) {
		_P("Case #%d: IMPOSSIBLE\n",_loop);
	}
	else {
		_P("Case #%d: %d\n",_loop,mi);
	}
}

まとめ

コーナーケースがややこしくてしんどい。