Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 231 B 問題 Election

AtCoder ABC ABC231 B問題 200 pts

問題

提出解答

問題の概要

$S_1, \dots, S_N$ のうち, 最も多く現れる文字列は何か? ただし, この問題ではこのような文字列が一意に定まるような入力のみ与えられる.

制約

$1 \leq N \leq 100$
$S_i$ は英小文字からなる長さ $1$ 以上, $10$ 以下の文字列
$N$ は整数
最も多く現れる文字列は一意に定まる.

解法

$i=1, \dots, N$ ごとに, $S_i$ が $S_1, \dots, S_N$ に何回登場するかみればよい. $S_i$ が $S_1, \dots, S_N$ に登場する回数を $M_i$ としたとき,

$\displaystyle M_I=\max_{i=1, \dots, N} M_i$

を満たすような $I$ を求め, $S_I$ を出力すれば良い.

ただし, $\displaystyle M_I=\max_{i=1, \dots, N} M_i$ となる $I$ は複数の候補が挙げられる場合があるが, 制約から, 条件を満たす $I$ について, $S_I$ は一致する.

そして, この解法の計算量は $O(N^2)$ であるが, 辞書を用いることにより, 計算量が $O(N)$ になる.