構文解析 [第四回 アルゴリズム実技検定 F]

https://atcoder.jp/contests/past202010-open/tasks/past202010_f

解説

https://atcoder.jp/contests/past202010-open/submissions/21472068

実装問題。問題で要求されていることを頑張って実装しよう。
以下に示すのは実装例であり、各々が好き好きに実装すればいい。

入力の抽象化

まずは、入力を抽象化しよう。
入力例でもやっていることだが、XXXが何個、YYYが何個のように集計をする。

cnt[s] := 文字列sが何個あるか

C++ではmapを使えば簡単に集計ができる。

個数が大きい順に文字列を見ていく

rev[t] := cnt[s]=tとなる文字列集合

これを集計用に作っていく。
C++のmapではvalue部分に配列も乗せることができるので、そこに文字列を入れていく。
最後にmapのイテレータを逆から使って、K番目の文字列を抽出していく。
mapのイテレータはkeyを昇順で取ってきてくれるので逆から使うことで大きいものから順に取り出すことができる。
今何個目を見ているかを変数xで保持しながら、K番目を探していく。
複数個ある場合はAMBIGUOUSを答えてそうでない場合は、その文字列を答えればいい。

int N, K;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    map<string, int> cnt;
    rep(i, 0, N) {
        string s; cin >> s;
        cnt[s]++;
    }

    map<int, vector<string>> rev;
    fore(p, cnt) rev[p.second].push_back(p.first);
    int x = 1;
    for (auto ite = rev.rbegin(); ite != rev.rend(); ite++) {
        vector<string> strs = ite->second;
        int tot = strs.size();

        if (x <= K && K < x + tot) {
            if (strs.size() == 1) cout << strs[0] << endl;
            else cout << "AMBIGUOUS" << endl;
            return;
        }
        x += tot;
    }
}