問題概要
AtCoder のジャッジ結果を表すような文字列("AC", "WA", "TLE", "RE" の 4 種からなる) が $N$ 個与えられる.それぞれについて個数を出力せよ.
制約
- $1 \leq N \leq 10^5$
解法
カウントするべき文字列の種類ガ少ないので,それぞれについて一回ずつ配列を全走査したとしても間に合います.ただ,C++ であれば std::map< std::string, int > などを使ってまとめて数えてしまった方が楽に解けるでしょう.
以下の例では Haskell で辞書( [ ( String, Int ) ] なリスト)を作って lookup しています.
いずれにしても,文字列の種類が定数なので配列を走査する回数や std::map の $\log$ は定数倍の中に消えるので $\Theta( N )$ 時間で計算できます.
コード
readInt = readLn :: IO Int main = do n <- readInt ss <- group . sort <$> replicateM n getLine let kv = map ( head &&& length ) ss output kv "AC" output kv "WA" output kv "TLE" output kv "RE" output kv s = printf "%s x %d\n" s $ fromMaybe 0 $ lookup s kv