AOJ 1188: Hierarchical Democracy（階層民主主義）

はじめに

あやややや！射命丸文です！今回は AOJ 1188 Hierarchical Democracy (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1188) という問題を解きました！最高最速の名にふさわしくC++なる言語を使おうとしたのですが、今回はまだJavaを使うことにしました。そのうちC++に切り替えようと思います！その暁には他にJava担当の幻想郷競技プログラマー部の部員を読んでこなくては行けませんね！

昨日 yoshikyoto さんが topcoder に参加する様子を見ていて、問題を解く時間を計ることと、WA*1 を出さないことが重要だと思ったので、時間とWAを出した回数を記録することにしました！

• 解くのにかかった時間: 20分
• WAの回数: 0

解法

選挙区を木構造にして、solve()を呼ぶと、子のsolve()を読んで、過半数を返すといった、再帰的関数で簡単に解くことができました！ [...] みたいな文字列の分解は、AOJではよく見る気がするので覚えておきたいですね！

ソースコード

class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            Zone zone = new Zone(br.readLine());
            System.out.println(zone.solve());
        }
    }
}

class Zone{
    ArrayList<Zone> children;
    int value = 0;
    
    Zone(String str){
        str = str.substring(1, str.length() - 1);
        
        try{
            // 値だったらparseInt
            value = Integer.parseInt(str);
        }catch(NumberFormatException e){
            // 値じゃなかったら木構造的にparse
            children = new ArrayList<Zone>();
            int depth = 0;
            int start = 0;
            for (int i = 0; i < str.length(); i++) {
                switch(str.charAt(i)){
                case '[':
                    if(depth == 0) start = i;
                    depth++;
                    break;
                case ']':
                    depth--;
                    if(depth == 0){
                        children.add(new Zone(str.substring(start, i+1)));
                    }
                    break;
                }
            }
        }
    }
    
    int solve(){
        // valueは必ず奇数なのでこれでいい
        if(value != 0) return (value + 1) / 2;
        
        // 再帰的！
        ArrayList<Integer> arr = new ArrayList<Integer>();
        for(Zone child : children){
            arr.add(child.solve());
        }
        
        // 過半数を返す
        Collections.sort(arr);
        int sum = 0;
        int maj = (arr.size() + 1) / 2; // arrのsizeはかならず奇数なので
        for (int i = 0; i < maj; i++) {
            sum += arr.get(i);
        }
        return sum;
    }
}

*1:Wrong Answer、間違えた回答を提出すること。