C-Green Bin

自分用備忘録として置いておきます。

c++の代表的なハッシュ法関連のSTLコンテナにunordered_mapというものがあります。ABC137のC問題ではこのハッシュコンテナを利用するのですが、unordered_mapの存在は知っていても使えないと意味がないということで実際にソースを書いてみました。

C-Green Bin
実行時間制限: 2 sec / メモリ制限: 1024 MB、配点:300点

問題文
文字列aに含まれる文字を何らかの順序で並べることで得られる文字列をaのアナグラムと呼びます。
例えば、"greenbin" は "beginner" のアナグラムです。このように、同じ文字が複数回現れるときはその文字をちょうどその回数だけ使わなければなりません。

　beginnerという文字列内の文字を何度か交換するとgreenbinというアナグラムを作ることが出来る。今回の問題は、いくつかの文字列が与えられた時に、同じアナグラムになる組み合わせは何個作れるかということを求めています。

入力例１
　N=3 (文字列が3つ)
　acornistnt
　peanutbomb
　constraint

　1つ目の文字列において、acornistntの文字を入れ替えるとconstraintを作ることができ、これは3つ目の文字列constraintに一致します。アナグラムが同じになるかどうかはc++のsort関数を使ってアルファベットの昇順に並べ替えれば良いでしょう。もちろん例えば、appleという単語はソートするとaelppなどのような意味不明なアナグラムに変換されますが、意味のある単語にするのが目的なのではなく、同じアナグラムでさえあれば同じ組としてカウントするというのが重要です。上記の例では1番目と3番目の文字列が同じアナグラムを作ることが出来るので回答としては1が正解になります。

　しかし制約条件の都合上、単純にすべての文字列をソートしてアナグラムを全探索で比較、カウントしている制限時間を超過してしまうので、同じアナグラムが出現したら、その出現回数を記録しておくことで計算時間を飛躍的に向上させることが出来ます。これにはunordered_mapというハッシュコンテナを利用して解くことが出来ます。unordered_mapではキー値としては文字列をソートした後のアナグラムを指定し、その値として出現回数をペアで保存しておけばよいでしょう。

aab, baa, abaという文字列があった場合
ソートするとすべてaabとなる為、aabをキー値としておけば、その出現回数は3回になります。
入力1回目：aab　→　["キー値" : 値] = ["aab" : 1]
入力2回目：baa　→　["キー値" : 値] = ["aab" : 2]
入力3回目：aba　→　["キー値" : 値] = ["aab" : 3]
というふうになります。

これをunordered_mapを利用して実装してみた結果が以下のようになります。

sample.cpp

#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)

using namespace std;

void solve() {
    int n; cin >> n; // 文字列の個数を入力
    vector<string> s(n); // 文字列の配列
    unordered_map<string, long long> um(n); // 既に出現した文字列を格納するハッシュコンテナ
    rep(i, n) cin >> s[i]; // 文字列入力

    long long res = 0; // 同じアナグラムの出現回数
    for (int i = 0; i < n; i++) {
        // 文字列をソートしてアナグラムを得る(cdbaとかならabcdと昇順(もしくは降順でも可)に並べ替える)
        sort(s[i].begin(), s[i].end());

        // 同じアナグラムの出現回数を記録、更新しておく
        um[s[i]] += 1;

        // 同じアナグラムが2回以上出た時に組数-1を足す
        res += um[s[i]] - 1;
    }
    cout << res << endl;
}

int main(void) {
    solve();
    return 0;
}

以上です。誤りや質問などございましたらコメント欄から知らせてください。

ABC137 C - Green Binをハッシュ法で解いてみた(備忘録)

C-Green Bin