AGC019 D : Shift and Flip(1000)
作成日：2017.09.02
最終更新日：2017.09.02
問題概要
$0$と$1$からなる同じ長さの文字列$A,B$がある。
操作1「両端はつながっているものとみなして$A$を1文字左または右にシフトする」、
操作2「$B$の$i$文字目が$1$であるような$i$を1つ選び$A$の$i$文字目のビットを反転する」
を何度か行い$A$と$B$を一致させる。
この時に必要な操作の最小回数を求めよ。
但し、不可能である場合は$-1$と答えよ。
制約
$1 \leq |A| = |B| \leq 2000$
考え方
同じビットを2回以上反転させるのは無駄であるから、操作2の回数は$A$と$B$のビットの対応が定まれば決めることができる。
すなわち最終的な位置が元の位置から右(左)にいくつシフトしたのかが決まれば$O(|A|)$で求められる。
$|A|$回同じ方向にシフトさせると元に戻ることから、$|A|$通りだけ求めれば良い。
操作1の回数は元の位置から最も右及び左にシフトされた位置と最終的な位置が決まれば$O(1)$で求められる。
ただ位置を決めただけでは反転すべきビットを反転させられるかが分からない上、愚直にやると少なくとも$O(|A|^3)$になってしまうので工夫する。
反転すべきビットを決めるためには最終的な位置は先に決めておく必要がある。
それらのビットが反転できるためには$B$で$1$が立っている位置を通らなければならないが、これは左右それぞれ元の位置に最も近いもののいずれかを通ることが分かれば十分である。
但し$B$に$1$が含まれない場合は反転できないので、$A$に$1$を含んでいるか否かのみで答えが求められる。
後は最も右及び左にシフトされた位置を適切に定められれば良い。
これはどちらかを固定すればそちらの方ではビットを反転できないもののみを考えることでもう片方を求めることができるが、工夫なしで行うと全体で$O(|A|^3)$かかり間に合わない。
そこで固定した方を遠ざけたり近づけたりするともう片方はどうなるかを考える。
固定した方を遠ざけるともう片方の位置を定めるために考えるべきビットは減り、近づけると増える。
考えるべきビットが徐々に増えるだけならば、左右の位置を定めるための計算量は合わせて$O(|A|)$になり、全体で$O(|A|^2)$となるから間に合う。
ソースコード
マクロ等はこちら
const int MC = 2017;
char A[MC],B[MC];
int c[MC]; //右にiだけシフトした時に反転すべきビットの数
int l[MC],r[MC]; //元の位置から最も近い$B$で$1$が立っている位置との距離(左右別)
int sl[MC],sr[MC];
int main(){
scanf("%s %s" , A , B);
int n = 0;
bool zeroA = 1 , zeroB = 1;
while(B[n] != 0){
if(A[n] == '1') zeroA = 0;
if(B[n] == '1') zeroB = 0;
sl[n] = sr[n] = n;
++n;
}
if(zeroB){
printf("%d\n" , zeroA ? 0 : -1);
return 0;
}
repp(i,0,n) repp(j,0,n) if(A[j] != B[(i+j)%n]) ++c[i];
repp(i,0,n){
while(B[(i+n-l[i])%n] == '0') ++l[i];
while(B[(i+r[i])%n] == '0') ++r[i];
}
sort(sl,sl+n,[&](const int p , const int q){return l[p] < l[q];});
sort(sr,sr+n,[&](const int p , const int q){return r[p] < r[q];});
int ans = 123456789;
repp(i,0,n){
int m = 0;
int p = n-1;
ans = min(ans , 2*n-2-i+c[(n-i)%n]);
repm(j,n-1,i){
while(l[sl[p]] == j){
if(A[sl[p]] != B[(sl[p]+n-j+1)%n]) m = max(m , r[sl[p]]);
--p;
}
ans = min(ans , (j-1)*2-i+c[(n-i)%n]+m*2);
}
}
repp(i,0,n){
int m = 0;
int p = n-1;
ans = min(ans , 2*n-2-i+c[i]);
repm(j,n-1,i){
while(r[sr[p]] == j){
if(A[sr[p]] != B[(sr[p]+j-1)%n]) m = max(m , l[sr[p]]);
--p;
}
ans = min(ans , (j-1)*2-i+c[i]+m*2);
}
}
printf("%d\n" , ans);
return 0;
}解法まとめ
$B$がすべて$0$ならば、答えは$A$がすべて$0$の時$0$、そうでない時$-1$である。(11-20行)
それ以外の時、最終的な位置が元の位置から左右どちらにシフトして到達するかで場合分けする。
各場合において最終的な位置を固定した後、左右で最もシフトされた位置の一方を徐々に近づけていき、もう一方を最も近くなるように定める。
これらのうちで操作の最小となるものが解となる。(29-53行)