ICPC 国内予選C(サンプルは通った,ジャッジデータは試せてない)

ICPC2013_C.cpp

// start: 0:34
// end: 2:00
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

#define REP(i, n) for ( int i = 0; i < n; i++ )

using namespace std;

string line;
int p, MAX_DEPTH;

// 0~9のcharならtrue
bool isNum(char c) {
    int n = c - '0';
    return 0 <= n && n <= 9;
}

// 数字のみをパース
int number() {
    int n = 0;
    while(isNum(line[p])) n = n * 10 + line[p++] - '0';
    return n;
}

// []をパース、数字はパースしない
int dfs(int depth) {
    int bkt = 0, sum = 0;
    vector<int> ret;

    while(1) {
        if ( line[p] == '[' ) {
            p++;
            bkt++;
            ret.push_back( dfs(depth+1) );
        } else if ( line[p] == ']' ) {
            bkt--;
            if ( bkt == -1 || depth == 0 ) {
                break;
            } else {
                p++;
            }
        } else {
            return number();
        }
    }

    // ソートして過半数を取り出し、過半数を計算して合計値を返す
    sort(ret.begin(), ret.end());

    // 最初の選挙区だけ得票数が過半数になる
    REP(i, ret.size()/2+1) {
        if ( depth == MAX_DEPTH ) sum += ret[i] / 2 + 1;
        else sum += ret[i];
    }
    return sum;
}

int main() {
    int n;
 
    cin >> n;

    while(n--) {
        MAX_DEPTH = 0;
        p = 0;
        cin >> line;

        // 最初の括弧の連続から最大の深さを計る（深さは一様）
        // 最初（最深）の計算のみ住民の投票なので過半数にする
        int i = 0;
        while(line[++i] == '[') ++MAX_DEPTH;

        cout << dfs(0) << endl;
    }   
    
    return 0;
}

sample

6
[[123][4567][89]]
[[5][3][7][3][9]]
[[[99][59][63][85][51]][[1539][7995][467]][[51][57][79][99][3][91][59]]]
[[[37][95][31][77][15]][[43][5][5][5][85]][[71][3][51][89][29]][[57][95][5][69][31]][[99][59][65][73][31]]]
[[[[9][7][3]][[3][5][7]][[7][9][5]]][[[9][9][3]][[5][9][9]][[7][7][3]]][[[5][9][7]][[3][9][3]][[9][5][5]]]]
[[8231][3721][203][3271][8843]]

sample.out

107
7
175
95
21
3599