ことさら−古都プログラマーの更級日記

京都でお寺を回りながら御朱印集めをしていたエンジニアのブログ。おもに技術的なはなしとか日常的なはなし。たまにカメラの話や競馬の話も書きます。

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、間違えた回答を提出すること。