Algoogle

Algorithm for Programming Contest

AOJ 1188 Hierarchical Democracy

Category: AOJ Tag: parsing

Hierarchical Democracy

問題概要


解法


一番下の階層から決定していけば良さそうなのでDFS的に潜っていく.
一番はじめの段階はn/2+1を返せばいい
あとの階層については, それより下の階層を決定したら
小さいのから順に勝てる数まで取っていって, その合計を返す.

”[” ”]”の扱いについては, “[“がその階層の始まり, “]”がその階層の終わりで
再帰すればあまり気にならない.

コード


(1188.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
#define rep(i,a) for(int i = 0;i < (a); i++)
#define all(u) (u).begin(),(u).end()
#define pb push_back
using namespace std;
typedef vector<int> vi;

int stoi(string num){
    int ret;
    stringstream s;
    s << num;
    s >> ret;
    return ret;
}

string str;
int cur;

int rec(){
    cur++;
    if(str[cur] != '[' && str[cur] != ']'){
        string t;
        while(str[cur] != '[' && str[cur] != ']')
            t += str[cur++];
        cur++;
        return stoi(t) / 2 + 1;
    }
    vi vote;
    while(str[cur] != ']'){
        vote.pb(rec());
    }
    sort(all(vote));
    int ret = 0;
    rep(i,vote.size()/2+1) ret += vote[i];
    cur++;
    return ret;
}

int main(){
    int n;
    cin >> n;
    while(n--){
        cin >> str;
        cur = 0;
        cout << rec() << endl;
    }
    return 0;
}

Comments