GCJ2017qual AをO(N)で解く

概要

長さNのbit列が与えられる。長さKの連続した列をflipして、全て1になるようにしたい。不可能ならIMPOSSIBLE、可能ならflipする最小数を答える。

略解

左から貪欲に0になっているところからflipする。背理法で証明できる。

largeケースですらなので普通にで解けてしまう。

高速化

flipを一様加算と見る。BITを使えばは自明。もう少し工夫する。

一様加算といえばBITの他にはimos法がある。今回はこれを使う。 imos法は微分した列を足した後に積分（累積和）するという手法である。一様加算の場合、微分した列は両端のみ足し込めば良く長さに依存しない。

しかし、足し合わせた後に逐一累積和を取れば意味がない。そこで、目標とする列も微分することを考える。 目標とする列は全て1である。これを微分すると、100….000となる。

また、最初に与えられた列も微分する必要があるが、足し合わせた後にmod 2を取ると考えると実は1も-1も等価であるためにとなる点を1とすれば良い。 後は、最初だけ1、他は0となるように（微分した）flipをする。

#include <bits/stdc++.h>
using namespace std;

string S;
int K;
vector<bool> vec;
int ans;

void flip(int x){
    vec[x] = vec[x]^1;
    vec[x+K] = vec[x+K]^1;
    ans++;
}

int solve(){
    cin >> S >> K;
    int L = S.size();
    
    ans = 0;
    vec.resize(L+1, false);
    
    vec[0] = S[0] == '+';
    for(int i=1; i<L; i++)
        vec[i] = S[i-1] != S[i];
    
    if(!vec[0]) flip(0);
    
    for(int i=1; i<L-K+1; i++) if(vec[i])
        flip(i);
    
    for(int i=L-K+1; i<L; i++) if(vec[i])
        return -1;
    return ans;
}

int main(){
    int T; cin >> T;
    for(int t=0; t<T; t++){
        cout << "Case #" << t+1 << ": ";
        
        int ans = solve();
        if(ans < 0)
            cout << "IMPOSSIBLE" << endl;
        else
            cout << ans << endl;
    }
    return 0;
}