Educational Codeforces Round 25: F. String Compression

http://codeforces.com/contest/825/problem/F

解法

文字列の最小周期はKMP法のテーブルを用いて計算できる。kmp[i]は文字列 S の先頭 i 文字を切り出した文字列の prefix と suffix の最大共通部分である。たとえば aabaabaab という文字列ならば 6 である。

aabaabaab
******
   ******

もし文字列に周期があるならば、i-kmp[i]が最小の周期になる。これはよく考えると分かるだろう。逆に文字列に周期がないならば、iはi-kmp[i]の倍数にはならない。

KMPテーブルの計算はO(n)でできるため、全体でO(n^2)で解くことができた。

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

int main() {
    std::string s;
    std::cin >> s;

    const int n = s.size();

    std::vector<int> len(n + 1);
    for (int i = 1; i <= n; i++) {
        len[i] = len[i / 10] + 1;
    }

    std::vector<int> dp(n + 1, 1e9);
    std::vector<int> kmp(n + 1);
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        kmp[i] = -1;
        int u = -1;
        for (int j = i + 1; j <= n; j++) {
            while (u != -1 && s[j - 1] != s[i + u]) u = kmp[i + u];
            if (u == -1) {
                kmp[j] = u = 0;
            } else {
                kmp[j] = ++u;
            }
            int period = (j - i) - kmp[j];
            if ((j - i) % period != 0) {
                period = j - i;
            }
            dp[j] = std::min(dp[j], dp[i] + len[(j - i) / period] + period);
        }
    }

    std::cout << dp[n] << std::endl;
}

最小周期が求められることの証明

周期が存在しないときは自明である。周期が存在するとき正しく求められるのかを考察する。

周期が存在するとき、たとえば以下のような対が考えられる。

f:id:pekempey:20170718002559p:plain:w500

文字列の長さを \(N\)、最小周期を \(T\)、kmpの値を \(K\) としたとき \(K>=N-T\) は自明に成り立つ。しかし \(K \gt N - T\) となってしまうと周期が正しく取れなくなってしまう。実はそうはならないことを示せば良い。

f:id:pekempey:20170718002928p:plain:w500

もし \(N-T\)よりも \(K\) が大きくなったとする。等しいノード同士を結ぶと以下のようになる。よく見るとすべてのノードが連結である。何故連結になるのかを示す。

f:id:pekempey:20170718003011p:plain:w500

重要な考察として、最小周期は素数である。\(N-K \lt T\) なので \(N-K\) は \(T\) の倍数ではありえない。つまり \(N-K\) と \(T\) は互いに素である。

f:id:pekempey:20170718003143p:plain:w500

互いに素なので、整数論のよくある定理(拡張ユークリッド互除法とかで見るやつ)により任意の地点に到達できる。よってすべての値が等しいということになる。しかしこれは矛盾、つまり仮定が誤っている。