AtCoder Beginner Contest 155 C – Poll を解いた記録
問題の概要
文字列が\(N\)個ある.出現回数が最大の文字列を,辞書順で小さい順に出力せよ.
制約
- \(1 \leq N \leq 2 \times 10^5 \)
- 文字列は英小文字のみからなる
- 文字列の長さは10以下
解法
次の2ステップで答えを出します.
- 出現回数が最大の文字列を探し出す
- 探しだした文字列を,辞書順で小さい順に出力する
出現回数が最大の文字列を探し出すためには,同じ文字列がそれぞれ何回出現するかを数えないといけません.連想配列(文字列などを添字にできる配列)を使って同じ文字列の出現回数を数えます.
入力される文字列をキー(添字),文字列の出現回数を値とする連想配列を用意すれば,文字列の出現回数を数えられます.
文字列の出現回数を数え終わったら,連想配列の要素をすべて確認して文字列の出現回数の最大値を求めます.
文字列の出現回数の最大値が求まったら,出現回数が最大値となる文字列だけを取り出し,それを辞書順で小さい順に出力すればOKです.
C++のmapでは,キーの値が小さい順(文字列の場合は辞書順で小さい順)に要素を参照できます.これを使えば,文字列の出現回数の最大値が求まったあとで文字列を出力する処理が簡単に書けます.
実装例
感想など
この問題は,私がAtCoderで初めてコンテスト中にC++を使ってACしたものです.以前はC言語でコンテストに出場していましたが,2020年2月頃に競プロを再開するときにC++へ移行しました.
ABC155の頃はまだC++に不慣れだったこともあり,実装に時間がかかっていました.(ABC155のA問題とB問題はC言語でACした)