yukicoder No.79 過小評価ダメ・ゼッタイ 解説

問題文

解説

$L$の大きさごとに人数を求めたいとき、mapを使うとよい。
ここで、人数を管理するmapの名前を$P$と置く。
mapで都度人数を管理し、任意の$i$において$P_i<P_j$または$P_i=P_j$&$i<j$となる$j$を求めればよい。
さらに、$j$を小さい順にみていけば、$P_i\leqq P_j$が成り立つ$j$として随時更新していけば解ける。
実行時間は$O(N \hspace{2pt}log\hspace{2pt}max(L))$。今回の$N\leqq10^5,L\leqq6$という制約化なら十分高速。
また、今回は$L$が小さいので、vectorで管理するという方法でも$O(N+max(L))$で解ける。($L$が大きいとメモリ容量で死ぬので注意)。

#include <bits/stdc++.h>
using namespace std;

int main(){
  int N;cin>>N;
  map<int,int> P;
  for(int i=0;i<N;i++){
    int L;cin>>L;
    P[L]++;
  }
  int ans=0;
  for(auto i:P)
    if(P[ans]<=i.second)ans=i.first;
  cout<<ans<<endl;
}