文字列のソートはどれだけかかる？

こんばんは、らんこむです。

先週末はABC287とARC155に参加していました。

ABC287はそれなりに解けたんですが、ARC155に関しては1問も解けず・・・

2時間問題とにらめっこしているのは中々辛かったですね。

さて、ABC287のE問題では公式解説とは別解としてソートをして解いている人が多かった印象です。

C問題のテストケースが少なかったことで話題になっていましたが、E問題もそれなりに盛り上がっていましたね。

さて、本題のE問題です。

atcoder.jp

与えられた文字列を辞書順にソートすると、LCPの計算は前後の確認だけで済むようになるので、

時間は「ソートの時間」+「前後比較の時間」です。

「前後比較の時間」については総文字数の 5 × 10⁵ で抑えられます。

問題となるのはソートの時間です。

一般的に長さ N の配列のソートは の計算量になります。

ただし、これは の "比較回数" です。長さ L の文字列の比較には最大で L回の文字比較が必要です。

実際には発生しませんが、簡単に考えられる最悪の状態としては長さ 2.5 × 10⁵ の二つの文字列に対して の比較を行うことです。

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main() {

    // 文字列長
    const int L = 250000;
    // 試行回数
    const long long N = 10000000;

    string S(L, 'a');
    string T(L, 'a');
    T[L - 1] = 'b';

    bool ans;
    time_t start = time(nullptr);

    for (long long i = 0; i < N; ++i) {
        ans = (S < T);
    }

    time_t end = time(nullptr);

    cout << difftime(end, start);

    return 0;

}

上記のコードで簡単に比較してみると1分程度かかりました。

まだまだ調べなければ分からないことは多いですが、1/60 程度に時間が抑えられれば良いので 嘘解法というわけではないような気がします。

また何か思いついたら続報を書こうと思いますが、今日はこのあたりで。