Codeforces Round #323 (Div. 1) C. Superior Periodic Subarrays

これジャッジ解も(C++ で) 300ms くらいかかってるのに時間制限が 1000ms しか無いのはどうかと思うんですがどうなんですかね。

問題

codeforces.com

解法

長さ s を固定して考えてみます。で, が superior であるとすると, まず が比較されるすべての数字 について, が成り立っていなければなりません。ところで, この j はどのような数字なのかを考えると, これは g = gcd(n, s) として, を満たす数であるとわかります。
これと同様のことが i, i+1, ..., i+s-1 について成り立ちます。すなわち, i, i+1, ..., i+s-1 がsuperior であるためには, 各 j(i <= j <= i+s-1) が を満たすグループ k について, 最大値をとっていることが必要十分条件である, ということがわかります。これがメインアイデアです。

あとは, これを効率的に計算してくれるように実装するだけです。
n との gcd の候補というのは, 要するに n の約数です。各約数 g ごとに, 上で述べた最大値を求め, 各 が グループの中で最大値をとっているのかを調べ, 連続した部分列の中で長さ i となる部分列がいくつあるのかを求めます。
で, gcd(i, n) = g となるものについて部分列の数を答えに加算していけば答えを求められます。

const int MAXN = 200010;
int a[MAXN], gg[MAXN];
bool ok[MAXN];
int cnt[MAXN];
int n;

int inc(int x) {
    return (x+1 == n) ? 0 : x+1;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) gg[i] = __gcd(i, n);
    ll ans = 0;
    // g: GCD の候補(約数)
    for (int g = 1; g < n; g++) {
        if (n%g != 0) continue;
        memset(ok, false, sizeof(ok));
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < g; i++) {
            int maxi = -1;
            for (int j = i; j < n; j += g) maxi = max(maxi, a[j]);
            for (int j = i; j < n; j += g) if (maxi == a[j]) ok[j] = true;
        }
        int l = 0;
        bool all = true;
        for (; l < n; ) {
            if (ok[l]) {
                l++;
                continue;
            }
            all = false;
            int r = inc(l), len = 0;
            while (ok[r]) r = inc(r), len++;
            for (int i = 1; i <= len; i++) cnt[i] += len-i+1;
            if (r <= l) break;
            l = r;
        }
        if (all) {
            for (int i = 1; i < n; i++) cnt[i] += n;
        }
        for (int i = 1; i < n; i++) if (g == gg[i]) ans += cnt[i];
    }
    cout << ans << endl;
    return 0;
}