558B - Amr and The Large Array

Problem - B - Codeforces

• 本番は下のコードの cnt のかわりに map を使った O(n*log(n)) の解法で通した。ソッチのほうがバグも少なくてすむと思うけど、勉強のため O(n) のコードを書いてみた。
• 要は beauty となる a[i] の値の先頭と末尾を見つけておいて距離を比較するだけ。

class Div2B {
public:
    // O(N)
    void solve(void) {
            int N;
            cin>>N;
            vector<int> A(N);
            int maxA = 0;
            REP(i,N)
            {
                cin>>A[i];
                maxA = max(A[i], maxA);
            }
            vector<int> cnt(maxA+1,0);
            REP(i,N)
                ++cnt[A[i]];
            int beauty = 0;
            REP(i, N)
                beauty = max(beauty, cnt[A[i]]);
            vector<pair<int,int>> xs;
            // 重複度が beauty と一致する A[i] の先頭と末尾を見つける
            // O(N)
            vector<int> head(maxA+1,-1);
            REP(i, N)
            {
                if (cnt[A[i]] == beauty && head[A[i]] < 0)
                    head[A[i]] = i;
            }
            vector<int> tail(maxA+1,-1);
            for (int i = N-1; i >= 0; --i)
            {
                if (cnt[A[i]] == beauty && tail[A[i]] < 0)
                    tail[A[i]] = i;
            }
            int L = N;
            int minL = 0;
            int minR = N-1;
            REP(i, N)
            {
                if (cnt[A[i]] != beauty)
                    continue;
                int len = tail[A[i]]-head[A[i]]+1;
                if (len < L)
                {
                    L = len;
                    minL = head[A[i]];
                    minR = tail[A[i]];
                }
            }
            cout<<(minL+1)<<" "<<(minR+1)<<endl;
    }
};