競技プログラミングの上記の問題がTLEになって原因を調べた．TLEになったコードは以下の通りである．
// 繰り返し部分のみ
vector<ll> c(200010, 0);
ll max = 0;
ll t;
REP(i, M) {
c[A[i]]++;
auto max = max_element(c.begin(), c.end());
cout << *max << endl;
}
結論としては計算量がO(MN)になるためである．(N=200010とする)制約として1≤N,M≤200000であるため，MNは最大4*1010となる．一見ループを見ると計算量がO(M)に見えるが，std::max_elementは要素の数だけ比較するので計算量はO(N)となる．以下はリファレンスより抜粋．
max((last - first) - 1, 0)回の比較を行う
max_element - cpprefjp C++日本語リファレンス
以上より，std::max_elementを使用しない実装を考える必要がある．以下のようにコードを変更した．
vector<ll> c(200010, 0);
ll max = 0;
ll t;
REP(i, M) {
c[A[i]]++;
if (max < c[A[i]]) {
max = c[A[i]];
t = A[i];
} else if (max == c[A[i]]) {
if (t > A[i]) {
max = c[A[i]];
t = A[i];
}
}
cout << t << endl;
}
以下のようにmax値を変数に持つことでstd::max_elementを使用しないようにした．計算量はO(MN)からO(M)に減った．
