はまやんはまやんはまやん

hamayanhamayan's blog

Tagの勢い [yukicoder No.628]

https://yukicoder.me/problems/no/628

解法

https://yukicoder.me/submissions/228007

今回は計算量が問題にならないので、高速化は考えなくてもいい。
色んな実装法があると思う。
 
mapを使ってタグ毎のポイントの総和をまず計算する。
これでタグとポイントのペアが取れたので、これをvector>に入れ替えて、ポイント降順タグ昇順でソートする。
pairのベクタのソートはfirst昇順second昇順なので、普通に使うとダメなのだが、firstにマイナスで入れておくと昇順ソートが絶対値的には降順ソートになり、比較関数を書かなくて済むのでオススメ。
あとは、そのベクタの先頭10個を取り出して答える。

int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    map<string, int> cnt;
    rep(i, 0, N) {
        int no, M, S;
        cin >> no >> M >> S;
        rep(j, 0, M) {
            string tag; cin >> tag;
            cnt[tag] += S;
        }
    }

    vector<pair<int, string>> v;
    fore(p, cnt) v.push_back({ -p.second, p.first });
    sort(v.begin(), v.end());

    int n = min(10, (int)v.size());
    rep(i, 0, n) printf("%s %d\n", v[i].second.c_str(), -v[i].first);
}