AtCoder AGC #019 : D - Shift and Flip

割とすんなり方針が立った。
http://agc019.contest.atcoder.jp/tasks/agc019_d

問題

同じ長さNの2つのビット列A,Bがある。
Aに対し以下の処理を繰り返し、A=Bとなるようにするには、最少何回処理を行う必要があるか。

• Aを左右いずれかに1bitローテートする
• B[i]=1である場合、A[i]を0/1反転する。

解法

BがゼロでA!=BのときはAのビットを変えられないので解なし。
それ以外の場合を考える。

AとBが一致した時点で、初期状態からのローテート量が合計左側にL回だったとする。
このLを総当たりしつつ最少回数を求めよう。(右側も同様に行う)

この時、A[i]はL回ローテート後(i-L)番目の位置に来る(mod Nは省略)。
よってA[i]=B[i-L]ならA[i]は反転不要。
A[i]!=B[i-L]ならどこかで反転しなければならない。
B[i-L]～B[i]の間のどこかに1があるなら、途中で反転すればよいが、それができるとは限らない。

そうでない場合、以下の2つの選択肢がある。

• 最初B[i+R]=1となる最小のR回まで右ローテートし、ビット反転させて(L+R)回左ローテートする。
• L回を超えB[i-L-L']=1となる最小のL'余分に左ローテートし、ビット反転させてL'回右ローテートする。

各ビットについて(L',R)を求めよう。
最初の余分な右ローテート回数rと、最後の余分な左ローテート回数lのうち、反転を要する全ビット反転に対しビットできるような最小の(l+r)を求めればよい。
これはソートしてスライド最小値や尺取り法の要領で求められる。

string S,T;
int A[10060];
int B[10060];
int L[10060],R[10060];
int N;
int n1,n0;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S>>T;
	N=S.size();
	
	n1=count(ALL(S),'1');
	n0=count(ALL(T),'0');
	if(n1 && n0==N) return _P("-1\n");
	if(S==T) return _P("0\n");
	
	int mi=1<<30;
	for(int loop=0;loop<2;loop++) {
		int pre=-1;
		FOR(i,5*N) {
			A[i]=S[i%N]=='1';
			B[i]=T[i%N]=='1';
			if(B[i]) pre=i;
			L[i]=pre;
		}
		pre=5*N;
		for(i=5*N-1;i>=0;i--) {
			if(B[i]) pre=i;
			R[i]=pre;
		}
		
		//left
		FOR(i,N) {
			int tar=0,shiftmi=101010;
			vector<pair<int,int>> V;
			FOR(j,N) {
				x=2*N+j;
				y=2*N+j-i;
				if(A[x]!=B[y]) {
					tar++;
					if(L[x]<y) V.push_back({y-L[x],R[x]-x});
				}
			}
			if(V.empty()) {
				shiftmi=0;
			}
			else {
				int RR[2020]={};
				int lma=0,rma=0;
				sort(ALL(V));
				FORR(v,V) lma=max(lma,v.first),rma=max(rma,v.second);
				shiftmi=min(lma,rma);
				for(r=V.size()-1;r>=0;r--) {
					RR[r]=max(RR[r+1],V[r].second);
					shiftmi=min(shiftmi,V[r].first+RR[r+1]);
				}
			}
			mi=min(mi,tar+i+2*shiftmi);
		}
		reverse(ALL(S));
		reverse(ALL(T));
	}
	
	
	cout<<mi<<endl;
	
}

まとめ

意外とコードが長くなってしまった。