Codeforces Round #683 (Div. 1) D2. Frequency Problem (R3000)

平方分割で解法を分岐する系の問題で、そのうちの片方の問題は Easy Version として D1 で出題されてた (Easy Version は R2600)

• 問題へのリンク

問題概要

正の整数 が与えられる。 以上 以下の整数のみからなる 要素の数列 が与えられる。

数列の連続する区間であって、それに含まれる最頻値が複数通りあるようなものを考える。そのような区間の長さの最大値を求めよ。

制約

• 

元の数列での最頻値のみ考えればよい

コンテスト中に考えていたのは

「求める区間の最頻値を としたとき、区間を挟む 2 つの整数はともに であるか、ともに であるかのいずれか」

というところだった。もしそうでなければ、条件を違反することなく区間を伸ばすことができるからだ。そしてこれ以上考察が進まなかった。

しかし、コンテスト後の TL を見て目から鱗だった。それは「もとの数列での最頻値が最頻となる区間のみ考えれば良い」ということだった。もし最頻値 ( とする) 以外の 2 つの数値 がともに最頻となるような区間が与えられたとしたとき、 の頻度は の頻度より小さくなっていることになる。しかしながら元々は の頻度は の頻度より大きくなっていたはずである。よって、元の数列から両端を削除して件の区間へと持っていく過程で、 の頻度と の頻度が一致する瞬間があるはずなのだ。この瞬間の区間長は、 がともに最頻となるときの区間長よりも大きい。

数列の種類数が小さい場合

これが Easy Version に相当する。最頻値を 1 個固定できるとなればやりようがある。

最頻値を としたとき、それ以外の各値 に対して、 の値で Zero-Sum Ranges をやれば OK。

ここで気になるのは、 と の頻度が一致する区間が得られたとして、その区間内部により頻度の高い値 が存在している可能性がある (この場合その区間は条件を満たさない)。しかしその場合、より長い区間が存在して、 と の頻度が一致する。ゆえに気にしなくてよい。

種類数が となるようにした場合、計算量は となる。

数列の種類数が大きい場合

まず、数列の数値の頻度が高い順に上位 をとって、それらについては Easy Version と同様の処理を行うことにする。そうすると、残りの整数については「頻度が 以下である」ということが言える (それより多いと全体の個数が を超えてしまうため)！！！

よってその場合については

「各 に対して、最頻値が でタイになるような区間の最長値を求める」

というふうにすれば OK。次のように考えればしゃくとり法が使える。

• 最頻値の頻度が 以下であるような極大の区間を列挙する (しゃくとり法が使える)
• そのうち最頻値がユニークでないものがあれば、答えを更新する

それぞれの作業は でできるので、このパートの計算量も となる。結局全体として計算量は となる。

コード

結構 TLE 厳しい...

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int MAX = 500;
int solve(int N, const deque<int> &A) {
    vector<int> hist(N, 0);
    for (int i = 0; i < N; ++i) hist[A[i]]++;
    vector<int> mean(N, 0);
    iota(mean.begin(), mean.end(), 0);
    sort(mean.begin(), mean.end(), [&](int i, int j) {return hist[i] > hist[j];});
    if (hist[mean[0]] == N) return 0;

    int res = 2;

    // 頻度の高いベスト √N
    for (int id = 1; id < min(MAX, N); ++id) {
        int v = mean[id];
        int GETA = A.size(), meannum = 0, vnum = 0;
        vector<int> vmin(GETA*2+1, GETA), vmax(GETA*2+1, -1);
        vmin[GETA] = vmax[GETA] = 0;
        for (int i = 0; i < N; ++i) {
            if (A[i] == mean[0]) ++meannum;
            else if (A[i] == v) ++vnum;
            chmin(vmin[meannum-vnum+GETA], i+1);
            chmax(vmax[meannum-vnum+GETA], i+1);
        }
        for (int i = 0; i < vmin.size(); ++i) chmax(res, vmax[i]-vmin[i]);
    }

    // 頻度が 1, 2, ..., √N になるもの: しゃくとり法
    for (int k = hist[min(MAX, N)-1]; k >= 1; --k) {
        int left = 0, vmax = 0, num = 0, num2 = 0;
        hist.assign(N, 0);
        auto push = [&](int id) -> void {
            hist[A[id]]++;
            chmax(vmax, hist[A[id]]);
            if (hist[A[id]] == k) ++num;
            else if (hist[A[id]] > k) --num, ++num2;
        };
        auto pop = [&](int id) -> void {
            hist[A[id]]--;
            if (hist[A[id]] == k) ++num, --num2;
            else if (hist[A[id]] == k-1) --num;
            if (num2 == 0 && num > 0) vmax = k;
            else if (num2 == 0 && num == 0) vmax = k-1;
        };
        for (int right = 1; right <= N; ++right) {
            push(right-1);
            while (left < right && vmax > k) pop(left++);
            if (num >= 2) chmax(res, right-left);
        }
    }
    return res;
}

int main() {
    int N;
    scanf("%d", &N);
    deque<int> A(N);
    for (int i = 0; i < N; ++i) scanf("%d", &A[i]), --A[i];
    printf("%d\n", solve(N, A));
}