Mister雑記

競プロやります。

ARC088-E 「Papple Sort」 (800)

「Bubble Sort」と何が掛かっているんだろうと思ったが、「b」がひっくり返って「p」になってるのか。

概要

文字列 Sが与えられる。「隣同士の要素を入れ替える」という操作のみで Sを回文にできるかどうか判定し、できるなら操作の最小回数を求めよ。

制約

  •  |S| \lt 2 \times 10^5
  •  Sは英小文字からなる

解説

判定について

回文文字列を真ん中で分割すると、それぞれに含まれる文字の組み合わせは全く同じになる。このことから「 Sは回文にできる」ことと「 S奇数回現れる文字が1種以下である」ことは同値だと分かる。

具体的には配列を用意して、各文字の出現回数をカウントしていけばいい。

最適な操作

ここまでは言わばウォーミングアップで、具体的な操作を考える方が本番となる。

最適な操作として、私は以下のようなアルゴリズムを考えた。

  • 左端にある文字を見る。
    • その文字が1つしか入ってない場合はその文字を消して最初へ。
      • ただし以降の操作回数が1回増える。
    • そうでなければ次へ。
  • その文字のうち、一番右側にあるものの位置を求める。
  • それをスワップによって右端へ移動させる。
  • 左端と右端の文字を消す。
    • 長さが1以下になったら終了。
    • そうでなければ最初へ。

具体例を示すと以下の通り。

f:id:misteer:20180816220124p:plain

操作だけだと何しているか分かりにくいが、消した文字を残すと以下のようになっている。

f:id:misteer:20180816220143p:plain

左から順番に文字を固定しているわけである。なぜこれが最適なのかと言われると説明が難しい。

操作回数の計算

上図の一番下にあるように、元の文字列から結果の回文文字列を求めること自体は O(|S|)でできる。

しかし上の操作、愚直にやると O(|S|^2)かかってしまい間に合わない。 実はこういったスワップの回数を、BIT(Binary Indexed Tree)を使うことで O(|S| \log |S|)で求める方法がある。

文字列では面倒なので、数列 (1, 2, \dots, N)を並び替えたものについて考える。このとき、スワップの回数は転倒数という値と一致する。

数列 (a_1, a_2, \dots, a_N)の転倒数は、「 1 \leq i \lt j \leq Nかつ a_i \gt a_j」なる (i, j)の組の数である。 jを固定すれば、「 1 \leq i \lt jかつ a_i \gt a_j」なる iの個数を足し上げることで求められる。

これも愚直に求めると O(N^2)かかってしまうが、BITを使えば以下のようなアルゴリズム O(N \log N)で求まる。

  • BITで a_iより大きい要素の数を求め、答えに加算する。
  •  a_iの位置の値を1増やす( a_iを追加する)。
  •  iをインクリメントして最初に戻る。

これを繰り返せばOK。これは一種の典型なので覚えておくべきだろう。

解答例

#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

template <typename T>
using V = vector<T>;
using ll = long long;
#define FOR(i, a, b) for (ll i = (a); i <= (b); ++i)

class BIT {
public:
    // 要素数N、値vで初期化
    BIT(ll N, ll v) : V_NUM(N) {
        data.resize(N);
        fill(data.begin(), data.end(), v);
    }

    // [1, i]の総和を求める
    ll query(ll i) {
        ll ret = 0;
        while (i > 0) {
            ret += data[i];
            i -= (i & -i);
        }
        return ret;
    }

    // data[i]にv可算
    void update(ll i, ll v) {
        while (i < V_NUM) {
            data[i] += v;
            i += (i & -i);
        }
    }

    ll V_NUM;
    V<ll> data;
};

// swapでfrom->toに変えるのに必要な回数を求める
ll bubble(string from, string to) {
    ll N = from.size();
    
    // 1. 文字列から数列に変換する
    // fromでの各文字のindexを突っ込む
    queue<ll> cidx[26];
    FOR(i, 0, N - 1) {
        cidx[from[i] - 'a'].push(i);
    }

    // from[i] -> to[idx[i]]
    V<ll> idx(N);
    FOR(i, 0, N - 1) {
        idx[i] = cidx[to[i] - 'a'].front();
        cidx[to[i] - 'a'].pop();
    }
    
    // 2. 求めた数列の転倒数を求める
    // N要素のBITを構築
    BIT bit(N + 1, 0);

    ll ans = 0;
    FOR(i, 0, N - 1) {
        // N - idx[i]以下の要素数を加える
        ans += bit.query(N - idx[i]);
        
        // N - idx[i]を追加
        bit.update(N - idx[i], 1);
    }

    return ans;
}

int main() {
    string S;
    cin >> S;

    // S中の各文字の数を数える
    V<ll> cnt(26, 0);
    for (char c : S) {
        cnt[c - 'a']++;
    }

    ll oddcnt = 0;
    FOR(i, 0, 25) {
        oddcnt += cnt[i] % 2;
    }

    // 回文判定
    if (oddcnt > 1) {
        cout << -1 << endl;
        return 0;
    }

    // 回文の前半分を構築する
    // 各文字について、Sの頭から順に半分ずつ拾っていけばいい
    string pre;
    V<ll> appear(26, 0);
    for (char c : S) {
        if (appear[c - 'a'] < cnt[c - 'a'] / 2) {
            pre.push_back(c);
            appear[c - 'a']++;
        }
    }

    string to = pre;
    
    // |S|が奇数の場合、真ん中の文字を付ける
    FOR(i, 0, 25) {
        if (cnt[i] % 2 > 0) {
            to.push_back(i + 'a');
        }
    }

    // 前半をひっくり返してくっつける
    reverse(pre.begin(), pre.end());
    to += pre;

    cout << bubble(S, to) << endl;
    return 0;
}

私のBITでは [1, i]の総和しか求められないので、 N - idxにわざわざ変換している。なんか変換しなくて済む方法はあるのだろうか。

感想

  • スワップの回数をBITで求められるのは大きな知見だった。
  • 最適な操作手順までは自力で辿りついたが、その計算量を減らす方法がどうしても思いつかず無念。
  • 久々に解説を書いたが、想像以上に時間がかかるし説明もぎこちないものになってしまった。難しい......。