【競プロ】1日1AC : ABC155 C問題 Poll

今日取り上げる問題はこちらです。

最近サボっていたのでC埋めを試みています。

その中でちょっとメモを残しておきたい問題をこうして記事にします。

提出コードと考え方

いくつか入力が与えられて、それぞれ何回出てきたかカウントするのは、mapが便利なのでそれを使いましょう。

keyとvalueが対応付けられていて、今欲しいのはvalueが最大のkeyです。

ループを回してこの最大値を求めるのが早いのですが、自分で解いた時はそうしなかったので、提出コードの解き方で説明します。

とりあえずvalueでソートしようと思ったので、mapの要素をpriority_queueに突っ込みました。

C++のpriority_queueは最大の要素を取り出します。

pair型の要素は、「firstの値」を比較、同じであれば「secondの値」を比較して順序を決めるので、キューには(value,key)で要素を入れています。
(順序は例えば、\((1,2)<(1,1),(1,\text{a})<(1,\text{b})\) のようになります。)

あとはvalueが最大のものを適当な配列に取り出して、ソートして出力します。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0;i < n;i++)

int main() {
    int n;
    cin >> n;
    map<string,int> mp;
    rep(i,n){
        string s;
        cin >> s;
        mp[s]++;
    }
    priority_queue<pair<int,string>> pq;
    for(pair<string,int> p : mp){
        pq.push(make_pair(p.second,p.first));
    }
    vector<string> ans;
    int vmax = pq.top().first;
    while(!pq.empty() && pq.top().first == vmax){
        ans.push_back(pq.top().second);
        pq.pop();
    }
    sort(ans.begin(),ans.end());
    for(string s : ans){
        cout << s << endl;
    }
    return 0;
}

先ほども言ったように、valueの最大をループで求めておくのが楽です
(editorialを読んで気づきました。)

というのも、mapのkeyは昇順にソートされているので、単に「要素を順番に取り出して、valueが最大のものであれば出力」を繰り返せばいいことになります。