ABC155 C問題をC++で解く

タイトルの通りABC155 C問題をC++で解いた話です。
問題のリンク


今回は筆者が最近よくやるsetとmultisetを組み合わせた探索を説明していこうと思います。

問題

N枚の投票用紙があり、i(1 <= i <= N)枚目には文字列Siが書かれている。

書かれた回数が最も多い文字列を全て辞書順で小さい順に出力してください。

方針

Sの中で最も書かれた文字列が何回書かれたかを求める部分、
最も書かれた回数が多い文字列を列挙する部分の2回全探索をする。

制約

1 <= N <= 2 * 10^5

1 <= Siの長さ <= 10

問題点

どうやら通常のfor文だとTLEするらしい。

解決策

探索部分の計算量を削減する。
削減方法として先程述べたsetとmultisetを組み合わせた探索を紹介します。

int main()
{
    ll N;
    cin >> N;
    
    multiset S;
    set roop_itr;

    for( ll i = 0; i < N; i++)
    {
        ll tmp;
        cin >> tmp;
        S.insert(tmp);
        roop_itr.insert(tmp);
    }
 
    # Sの中で最も書かれた文字列が何回書かれたかを保持する
    ll most = 0;
 
    # 一番多く書かれている文字の回数を探索
    for(set::iterator itr = roop_itr.begin(); itr != roop_itr.end(); ++itr)
    {
        if( S.count( *itr ) > most ) most = S.count( *itr );
    }
 
    vector ans;
    # 一番多く書かれている文字列を列挙する
    for(set::iterator itr = roop_itr.begin(); itr != roop_itr.end(); ++itr)
    {
        if( S.count( *itr ) == most ) ans.push_back( *itr );
    }

    # 辞書順で表示するのでソートしておく
    sort(all(ans));
    rep(i,ans.size()) cout << ans[i] << endl;

注目する部分は、以下である。
Sの先頭から最後まで見ていくのと違い、setの要素を全探索しているので探索量を抑えることが出来る。
また要素数をmultisetのcount関数を用いて求めているところもポイント。

# 一番多く書かれている文字の回数を探索
    for(set::iterator itr = roop_itr.begin(); itr != roop_itr.end(); ++itr)
    {
        if( S.count( *itr ) > most ) most = S.count( *itr );
    }

これでSの中身が全て異なる文字列でない限りは計算量削減を見込むことが出来る。
Sの中身が全て異なる文字列の場合TLEするかもしれない...
実際に提出したコード