AOJ 1188 Hierarchical Democracy (ICPC国内予選2013問題C)

• 問題文

括弧の始まり('[')が来たときに再帰呼び出しをしてその括弧の始まりに対応する括弧の終わり(']')が来た時にその選挙区で必要な最小の得票数を計算してその結果を返せばよいです。
第 1 段階の有権者数で必要な最小の得票数は有権者の過半数の票なので、有権者の数を c とすると必要な最小の得票数は (c + 1)/2 です。 なので数字が来たときは適切にパースして最小の得票数 (c + 1)/2 を vector にでも入れます。

第 k 段階で必要な最小の得票数は、この選挙区に含まれる第 k − 1 段階の選挙区のうち過半数で勝った候補者の最小の得票数となります。つまり第 k 段階の選挙区に含まれる第 k − 1 段階のそれぞれの候補者の必要な最小の得票数を
{c1 ,c2 , ... ,cn} (n が必ず奇数)
とするとこれらをソートして小さい方から (n + 1)/2 個の合計が第 k 段階の必要な最小の得票数となります。

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

string s;
int p = 0;

bool is_digit(char c){
    return '0' <= c && c <= '9';
}

int dfs(){
    vector<int> v;
    while( p < s.size() ){
        if( is_digit(s[p]) ){
            int res = 0;
            while( is_digit(s[p]) ){
                res *= 10;
                res += s[p] - '0';
                p++;
            }
            v.push_back((res + 1) / 2);
        }else if( s[p] == '[' ){
            p++;
            v.push_back( dfs() );
        }else if( s[p] == ']' ){
            p++;
            int n = v.size();
            vector<int> a = v;
            sort(a.begin(), a.end());
            int res = 0;
            for(int i = 0; i <= n/2; i++){
                res += a[i];
            }
            return res;
        }
    }
}

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> s;
        p = 1;
        cout << dfs() << endl;
    }
}