Official

F - 構文解析 Editorial by QCFium


以下の2 つのステップに分けて考えます。

  • 同じ文字列をまとめて、「\(s_1\)\(n_1\) 個、\(s_2\)\(n_2\) 個、\(s_3\)\(n_3\) 個、\(\dots\)」 というデータ形式にする
  • 上のステップでできた列 \(s, n\) を、\(n_i\) の大きい順に並べ替える。

これが終われば

  • \(n_{K - 1}\) が存在し、\(n_{K - 1} = n_K\) なら ambiguous
  • \(n_{K + 1}\) が存在し、\(n_{K + 1} = n_K\) なら ambiguous
  • それ以外の場合は \(s_K\)

と答えを求めることができます

ステップ \(1\) :
C++ では std::map 、python では dict など、連想配列があれば \(O(N \log(N))\) でできます。連想配列のキーを文字列、値を整数 (出現回数を表す) とするとよいです。

ステップ \(2\) : C++ では std::sort 、python では sort など、\(O(N \log(N))\) のソート (並び替え) 関数を使うとよいです。

合計で時間計算量 \(O(N \log(N))\) でできます。

posted:
last update: