mayoko’s diary

プロコンとかいろいろ。

AtCoder Regular Contest 060 F - 最良表現 / Best Representation

AtCoder
問題

arc060.contest.atcoder.jp

解法

n = |w| とします。

全て同じ文字で構成されている場合答えが n 1 となること, および w が良い文字列である場合答えが 1 1 になることは明らかです。

その他の場合は最良表現が 2 になることが分かるようです。

よって, 以下のようなアルゴリズムが考えられます：

  • 答えが n 1 になる場合は自明なので先に処理する。
  • 答えが 1 1 になるかどうかを判定する。
  • そうでない場合, [0, i) と [i, n) に分けてそれぞれが良い文字列かどうかを判定し, その数を求める。

ここで問題になるのは「良い文字列になるかの判定をどうやるか」ということです。文字列の長さが m であるとすると, 周期的になる文字の長さ d は, m の約数しかありません。

よって, 各 d に対してその周期の繰り返しでないことが分かれば良いわけですが, これは [0, n-d) の範囲の文字列と [d, n) の文字列が一致しているかどうかで判定することができます(最初の d 文字が一致していると 最初の 2 周期が同じであることがわかって, 次の d 文字が一致していると 3 周期一致していることがわかって, … というような感じ)。
文字が同じかどうかはローリングハッシュを使えば簡単に判定できます。ローリングハッシュって神。

また, [1, n] の約数の数を数えようとするアルゴリズムを考えると, 以下のプログラムより 約数の数の総和は O(N log N) であることがわかります。

for (i = 1; i <= n; i++) {
    for (j = i; j <= n; j += i) {
        cnt++;
    }
}

よって, 最良表現が 2 の場合でも, 全体で O(N log N) で判定できます。

std::random_device rnd;
const ull mul[2] = {10000 + (rnd()%10000), 10000 + (rnd()%10000)};
const ull mod[2] = {1000000007, 1000000009};

class RollingHash {
public:
    RollingHash() {}
    template<class T>
    RollingHash(const T& s) {
        init(s);
    }
    template<class T>
    void init(const T& s) {
        n = s.size();
        for (int i = 0; i < 2; i++) {
            pow[i].resize(n+1);
            h[i].resize(n+1);
            pow[i][0] = 1; h[i][0] = 0;
        }
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < n; j++) {
                pow[i][j+1] = (mul[i]*pow[i][j]) % mod[i];
                h[i][j+1] = (s[j] + h[i][j]*mul[i]) % mod[i];
            }
        }
    }
    inline pair<ull, ull> hash(int i) const {return make_pair(h[0][i], h[1][i]);}
    // [l, r)
    inline pair<ull, ull> hash(int l, int r) const {
        ull p0 = (h[0][r] - (h[0][l]*pow[0][r-l]%mod[0]) + mod[0]) % mod[0];
        ull p1 = (h[1][r] - (h[1][l]*pow[1][r-l]%mod[1]) + mod[1]) % mod[1];
        return make_pair(p0, p1);
    }
private:
    int n;
    vector<ull> pow[2], h[2];
};

const int MAXN = 500100;
vector<int> divs[MAXN];

// [l, r)
bool isGood(const RollingHash& rh, int l, int r) {
    int n = r-l;
    for (int d : divs[n]) {
        if (rh.hash(l, r-d) == rh.hash(l+d, r)) return false;
    }
    return true;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int n = s.size();
    {
        vector<int> cnt(26);
        for (char c : s)
            cnt[c-'a']++;
        for (int i = 0; i < 26; i++) {
            if (cnt[i] == n) {
                cout << n << endl;
                cout << 1 << endl;
                return 0;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 2*i; j <= n; j += i) {
            divs[j].push_back(i);
        }
    }
    RollingHash rh(s);
    if (isGood(rh, 0, n)) {
        cout << 1 << endl;
        cout << 1 << endl;
        return 0;
    }
    int ans = 0;
    for (int i = 1; i < n; i++) {
        if (isGood(rh, 0, i) && isGood(rh, i, n)) ans++;
    }
    cout << 2 << endl;
    cout << ans << endl;
    return 0;
}

良い文字列の判定の仕方が思いつかなくて死んでいた。言われてみれば当たり前なので悔しい。