第 4 回 PAST F - 構文解析 (4Q)

集計処理した上で、再度大きい順にソートする問題

• 問題へのリンク

問題概要

個の文字列 が与えられる。

この列に一回以上出現する単語を、その出現回数の多い順に並べたとき 番目の単語を出力せよ（一意に決まらない場合は "ambiguous" と出力せよ）。

制約

• 
• 

考えたこと

まずは集計処理しよう！　すなわち、次のような連想配列 (C++ ならば map<string, int> 型を求めよう。

---

• nums[str]： 個の文字列の中に、文字列 str が何個あるか

---

これを求めたあとは、各文字列ごとに再び (個数, 文字列) のペアを配列に格納していこう。これを大きい順にソートして 番目を求めれば良い。

ただし、タイがある場合は "AMBIGUOUS" と返す必要がある。ここでは、次のように判定した。

• 番目に大きい頻度と、 番目に大きい頻度が一致する ( の場合)
• 番目に大きい頻度と、 番目に大きい頻度が一致する ( の場合)

については、 "AMBIGUOUS" と返せばよい。

全体として、文字列の長さの最大値を として、計算量は と評価できる。

コード

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

int main() {
    int N, K;
    cin >> N >> K, K--;
    string S;
    map<string, int> nums;
    for (int i = 0; i < N; i++) {
        cin >> S;
        nums[S]++;
    }

    vector<pair<int, string>> v;
    for (auto [str, num] : nums) v.emplace_back(num, str);
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());

    if (K > 0 && v[K].first == v[K-1].first) 
        cout << "AMBIGUOUS" << endl;
    else if (K+1 < v.size() && v[K].first == v[K+1].first)
        cout << "AMBIGUOUS" << endl;
    else
        cout << v[K].second << endl;
}