Codeforces Round #658 (Div. 2) 参加記

B - Sequential Nim

最初にに到達した方が、常に先に山に手をつけることができる。これは、次がなら、その山をだけ残して相手に渡し、次がの場合は山を全て取ることで実現できる。よって、到達するまでの回数を数えればよい。注意点として、最後の山は数えない。

void solve(){
    int N;
    cin >> N;
    vector<int> a(N);
    rep(i,N)cin >> a[i];
    int cnt = 0;
    rep(i,N-1){
        if(a[i] == 1)cnt++;
        else break;
    }
    cout << ((cnt%2 == 0)? "First": "Second") << endl;
}

C - Prefix Flip

Easy Version

右から揃えていく。が揃っていない場合、反転させるためには、であることが条件である。この条件を満たしていない場合は、先頭だけの処理を挟めばよい。

である。

void solve(){
    int N;
    cin >> N;
    string a, b;
    cin >> a >> b;
    auto f = [&](int x){
        //cerr << x << ":" << endl << a << endl;
        rep(i,x+1){
            a[i] = char(((a[i] - '0') ^ 1) + '0');
        }
        reverse(a.begin(), a.begin()+x+1);
        //cerr << a << endl;
    };
    vector<int> ans;
    for(int i = N-1; i >= 0; i--){
        if(a[i] == b[i])continue;
        if(a[0] == a[i]){
            f(i);
            ans.push_back(i+1);
        }
        else{
            f(0);
            ans.push_back(1);
            f(i);
            ans.push_back(i+1);
        }
        //dump(a);
    }
    cout << ans.size() << " ";
    for(auto v: ans){
        cout << v << " ";
    }
    cout << endl;
}

Hard Version

右から揃えていくのは変わらないが、reverseを実装するとTLEになる。 ここで、reverseする代わりに、左右端のindex を持ち、reverseされることをswap(l,r)に言い換える。また、間が何回反転されたかも持つ。間がどこにあるかを持つ必要はない。先頭だけの処理もあるので、個別の反転回数も持って、合計何回反転されたかをもてば偶奇でわかるようになる。

。

void solve(){
    int N;
    cin >> N;
    string a, b;
    cin >> a >> b;
    vector<int> x(N), y(N);
    rep(i,N){
        x[i] = a[i] - '0';
        y[i] = b[i] - '0';
    }
    int l = 0;
    int r = N-1;
    int cnt_all = 0;
    vector<int> cnt(N,0);
    vector<int> ans;
    for(int i = N-1; i >= 0; i--){
        int xr = x[r] + cnt_all + cnt[r];
        int xl = x[l] + cnt_all + cnt[l];
        xr %= 2;
        xl %= 2;
        if(xr == y[i]){
            if(l < r)r--;
            else r++;
            continue;
        }
        if(xl != xr){
            xl ^= 1;
            cnt[l]++;
            ans.push_back(1);
        }
        swap(l,r);
        ans.push_back(i+1);
        cnt_all++;
        if(l < r)r--;
        else r++;
    }
    cout << ans.size() << " ";
    for(auto v: ans){
        cout << v << " ";
    }
    cout << endl;
}