AtCoder Grand Contest 019: D - Shift and Flip

,

https://beta.atcoder.jp/contests/agc019/tasks/agc019_d

ストレステストと嘘とテストケースの弱さを使ってAC。 つまりバグが残っている。 鯖側のテストだと$1000$ケースとかは用意してはいられないのでまあはい。

solution

最終状態の$A$の先頭が元々のAの何番目だったのかを総当たり。 $A_l$が先頭に移動するとして、それに加えて$0,1$の反転のために右に$d_r$移動して戻る/左に$d_l$移動して戻るという操作が必要。 この$l, d_l, d_r$について総当たりを愚直で書けば$O(N^4)$。 そこから$l$だけ決めて残りを二分探索とかでいい感じにするようにしたら$O(N^2 \log N)$。

まず$l$を固定する。 $A_l$を先頭にするのには左shiftを$l$回使うとしてよい。 $A_i$を$i$から$i - l$に動かす過程で$B$に$1$がなくかつ動かした後で不一致のときを考える。 そのような$i$のそれぞれについて、左に$l$動かす前に右にいくつ動かせば$1$に辿り着くかを$d_r(i)$、左へ$l$動かした後に左にいくつ動かせばを同様に$d_l(i)$とする。これは二分探索で決定できる。 $(d_l, d_r)$は$\forall i. d_l(i) \le d_l \lor d_r(i) \le d_r$を満たせばよく、これはsortしていい感じにすれば$O(N \log N)$で求まる。

implementation

嘘実装。$\mathrm{popcnt}(A) = N$で分岐してある場合を除いて$\mathrm{popcnt}(B) = 1$なケースで落ちる。

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_reverse(i, n) for (int i = (n)-1; (i) >= 0; --(i))
#define whole(x) begin(x), end(x)
using ll = long long;
using namespace std;
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }

template <typename UnaryPredicate>
ll binsearch(ll l, ll r, UnaryPredicate p) { // [l, r), p is monotone
    assert (l < r);
    -- l;
    while (r - l > 1) {
        ll m = (l + r) / 2;
        (p(m) ? r : l) = m;
    }
    return r; // = min { x in [l, r) | p(x) }, or r
}

constexpr int inf = 1e9+7;
int solve(string const & a, string const & b) {
    if (not count(whole(b), '1')) {
        return count(whole(a), '1') ? -1 : 0;
    }
    int n = a.size();
    if (count(whole(a), '1') == n and count(whole(b), '1') == 1) {
        return 2 * n - 2; // ???
    }
    vector<int> b_acc(n + 1);
    repeat (i, n) b_acc[i + 1] = b_acc[i] + (b[i] == '1');
    auto get_b_acc = [&](int l, int r) { return b_acc[r] - b_acc[l] + (l > r ? b_acc[n] : 0); };
    int result = inf;
    repeat (l, n) {
        vector<pair<int, int> > que;
        int cnt = 0;
        repeat (j, n) {
            int i = (l + j) % n;
            if (a[i] != b[j]) {
                cnt += 1;
                if (not get_b_acc(j, i + 1)) {
                    int dl = binsearch(0, n, [&](int d) {
                        return get_b_acc((j - d + n) % n, j);
                    });
                    int dr = binsearch(0, n, [&](int d) {
                        return get_b_acc(i + 1, (i + 1 + d) % n);
                    });
                    que.emplace_back(dl, dr);
                }
            }
        }
        int delta = n;
        if (que.empty()) {
            delta = 0;
        } else {
            sort(whole(que));
            int acc = 0;
            repeat_reverse (i, que.size()) {
                setmin(delta, 2 * que[i].first + 2 * acc);
                acc = max(acc, que[i].second);
            }
            setmin(delta, 2 * acc);
        }
        setmin(result, l + cnt + delta);
    }
    return result;
}

int main() {
    string a, b; cin >> a >> b;
    int result = inf;
    setmin(result, solve(a, b));
    reverse(whole(a));
    reverse(whole(b));
    setmin(result, solve(a, b));
    cout << result << endl;
    return 0;
}