AtCoder Regular Contest 088 E - Papple Sort

今年の解き納め問題。

この回は都合で出られなかったけど、出てたらこれは解けていた気がする…

問題概要

文字列Sが与えられる。これを「隣り合った2つの文字を入れ替える」という操作を好きなだけ行い、回文に出来るか。可能なら、捜査の最小回数を求めよ。

E - Papple Sort

解説

そもそも回文に出来るかですが、
回文を作れる⇔奇数個ある文字の種類が1個未満
なので、普通にカウントしてあげてください。

最小回数ですが、AtCoder解説と異なる解法です。

外側から順に文字を確定していく方式。考え方にコツがあって、

• 各文字の種類ごとに見た時、同じ種類同士の文字を入れ替える必要性は全く無いので、一番外側の文字のみを考えればよい。

という点があります。で、一番外側に動かすのに最も操作回数の少ない文字を求めて、それを貪欲に外側に持っていけばいいです。

各文字の種類でdequeにその文字がある座標を埋め込むとこれが楽に実装・削除できます（通常の配列では工夫しないと、1操作でO(N)かかるので注意）。
しかし、「現在どこにその文字があるか」が分からないのでそれを毎回探す必要があり、これに1回O(|S|)かかります。そこで、バブルソートの反転数でお馴染みのBitIndexedTreeを利用します。

Bit Indexed Treeでは「i以下の要素で、利用された要素数」を見つけることが出来れば、「利用した文字列は消し去るor一番右へスライドし、後は利用しない」という考え方で、dequeに格納された最初の状態から現在あるべき座標が求められます。

移動後の座標がx - sum(x)で求まるので、一番外側に何を持ってくればいいのか、それに何回かかるかがO(log|S|)で分かります。あとは実際に文字列を操作せず、dequeのみで管理する点に注意して、文字がなくなるまで繰り返せば最小手数が求まります。

実際はBITでなくても、セグ木でも平方分割でも通りそうですが、これが一番実装楽だと思います。

Submission #1929672 - AtCoder Regular Contest 088

deque<int> pos[26];

int bit[200010];
int N = 1;

void init(int n) {
    N = n;
    REP(i, N)   bit[i] = 0;
}

void add(int k, int a) {
    while (k <= N) {
        bit[k] += a;
        k += k&-k;
    }
}

int sum(int k) {
    int ret = 0;
    while (k>0) {
        ret += bit[k];
        k &= k - 1;
    }
    return ret;
}

int main() {
    string s;   cin >> s;
    int n = s.size();
    rep(i, n)   pos[s[i] - 'a'].push_back(i + 1);
    int cntodd = 0;
    rep(i, 26) cntodd += pos[i].size() & 1;
    if (cntodd > 1) {
        cout << -1 << endl;
        return 0;
    }
    ll ret = 0;
    init(n);
    while (n > 2) {
        int del = -1;
        int mov = inf;
        rep(i, 26) {
            if (pos[i].size() > 1) {
                int l = pos[i].front(), r = pos[i].back();
                //適当に正しい位置へもっていき、
                l -= sum(l);    r -= sum(r);
                //両端への移動距離を計算する
                if (mov > (l - 1) + (n - r)) {
                    mov = l + n - r - 1;
                    del = i;
                }
            }
        }
        ret += mov;
        add(pos[del].front(), 1);
        add(pos[del].back(), 1);
        pos[del].pop_front();
        pos[del].pop_back();
        n -= 2;
    }
    cout << ret << endl;
    return 0;
}

感想

ライブラリ持ってないんですよね…BITでバグらせてWA連発したのは痛かった。