読者です 読者をやめる 読者になる 読者になる

LoL/LJL好きのエンジニアのブログ

技術的な話やら、最近はLoLやLJLの話など。

AOJ 1305: Membership Management

はじめに

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

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

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

問題

射命丸文は文々丸新聞のマネージャーである。 従業員はみんな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);
        }
    }
}

*1:英語を理解するまでの時間です

*2:見てもらえればわかりますがコードは短い

*3:会社に所属しているメンバー全員を求める問題だと思っていた

*4:Time Limit Exceeded: 実行時間オーバー