はじめに

今回は Membership Management | Aizu Online Judge という問題を解きました。

問題読解: 17分 *1
解釈実装: 25分
WA: 2回

実装にそんなに時間はかからなかったのですが *2 、問題を勘違いしており*3 、無駄に時間をかけてしまいました。また、この問題は実行時間が見積もりにくかったです。大雑把な見積もりで提出したらTLE *4 を2回出してしまいました。この2点が反省点です。TLEの詳細につきましては後に述べます。

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1305

射命丸文は文々丸新聞のマネージャーである。従業員はみんな1つ以上のグループに所属している。しかし、グループのメンバーの入れ替えが頻繁に起こる。射命丸は、グループのメンバー管理に頭を悩ませていた。

射命丸は何か変更があるたびにメンバー情報の更新をする。例えば、myonとpadがplayerグループのメンバーであるということは、以下のように表される。

player:myon,pad.

: の前がグループの名前で、その後がメンバーの名前である。メンバーの部分にグループの名前が出てくることもある。

yoyomu:nine,myon,player,yuyuko.

これはplayerグループがyoyomuグループに含まれていることを示す。これは以下と同じである。

yoyomu:nine,myon,myon,pad,yuyuko.

しかし、これではmyonが重複することになるので、実際は以下のようになる。

yoyomu,nine,myon,pad,yuyuko.

あなたの仕事は、このようなグループの管理を行うことである。グループはすごく深くネストすることもあるので注意してほしい。

入力

入力は複数のデータセットからなる。
nは100以下の整数で、入力の数である。
続くn行はグループの情報が与えられる。
- 形式は、<グループ名>:<メンバー1>,<メンバー2>,...,<メンバーm>. といった感じである。
- グループの名前はすべて異なり、メンバーは1人以上10人以下である。
- グループに含まれているグループが循環することはない。
- グループに含まれるメンバーの名前は1文字以上の英語小文字からなる。
入力の終わりは0で表される。

出力

それぞれのデータセットに対して、一番最初のグループに含まれるメンバーの数を求めよ

方針

グループ名 -> グループメンバー配列 となるHashMapを作る
- ここのkeyに含まれていない名前はメンバーの名前なので人数カウント
人数を重複してカウントしないように、HashSetに人間を突っ込んでいく
1度調べたグループや名前はcheckedというHashSetに突っ込んでいき、二度調べないようにした
- 最初はデータの大きさが大したこと無いからと甘く見ていたが、これをしないとTLEする
- グループが100あるため、グループ1にグループ2が含まれていて、グループ2にグループ3が含まれていて… となっていた場合、O(100!) かかってしまうので当然間に合わない

実装

Java
変数名がわかりづらいのが反省点

class Main {
    static HashMap<String, String[]> groups;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true) {
            int n = Integer.parseInt(br.readLine());
            if(n == 0) break;
            
            String group = "";
            groups = new HashMap<String, String[]>();
            for (int i = 0; i < n; i++) {
                String[] team = br.readLine().split(":");
                String[] members = team[1].split("[,\\.]");
                groups.put(team[0], members);
                if(i == 0) group = team[0];
            }
            
            HashSet<String> ans = new HashSet<String>();
            HashSet<String> checked = new HashSet<String>();
            getMember(group, ans, checked);
            System.out.println(ans.size());
        }
    }
    
    /**
    * ansに再帰的にメンバーを突っ込んでいく
    */
    static void getMember(String name, HashSet<String> set, HashSet<String> checked){
        if(checked.contains(name)) return;
        checked.add(name);
        if(!groups.containsKey(name)) {
            set.add(name);
            return;
        }
        String[] members = groups.get(name);
        int len = members.length;
        for (int i = 0; i < len; i++) {
            getMember(members[i], set, checked);
        }
    }
}