Codeforces 673C - Bear and Colors - fooractalの競プロ日記

問題

Bearは $n$ 個の色付けされたボールを持っており、それらの色は $t_{1}, t_{2}, ..., t_{n}$ で表されます。
今このボールを一列に並べたとき、連続したボールの部分列によって区間が定義されます。このそれぞれの区間について最も数の多いボールの色を、その区間のdominant colorと定義します。またそのような色が複数存在する場合は最も番号付けの小さい色をdominant colorとすることにします。 $n$ 個のボールによって得られる互いに異なる区間のdominant colorを集計して、それぞれの色についての結果を出力してください。

解法

ベッドに入りながら考えてましたが解けなかったのでei1333さんの解法を見ました。
範囲の左端を決め、右端を徐々に伸ばしていくというイメージです。右端を伸ばしたとき、比較するのは今まで見てきたdominant colorと新しく範囲に入った色だけで十分であることがわかります。
あとは左端の位置を順次変更していけば全ての範囲について調べることができます。結局計算量は $O(n^2)$ となり十分間に合います。

ソースコード

#include <iostream>
#include <cstring>
using namespace std;

#define REP(i, x) for (int i = 0; i < (x); i++)
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a); i < (b); i++)

const int MAX_N = 5010;

int ti[MAX_N];
int answer[MAX_N];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    REP (i, n) {
        int t;
        cin >> t;
        ti[i] = t - 1;
    }

    REP (i, n) {
        int count[MAX_N], dominant = ti[i];
        memset(count, 0, sizeof(count));
        FOR (j, i, n) {
            count[ti[j]]++;
            if (count[dominant] < count[ti[j]] ||
                    (count[dominant] == count[ti[j]] && ti[j] < dominant)) {
                dominant = ti[j];
            }
            answer[dominant]++;
        }
    }

    REP (i, n) {
        cout << (i == 0 ? "" : " ") << answer[i];
    }
    cout << endl;

    return 0;
}

感想

わからなくて調べている途中にConvex Hull Trickという単語を幾度か聞いたので調べてみたいです。
この程度の問題はさらっと解けるようになりたいですね。