ICPC 国内予選2013C 階層民主主義 AOJ 1188

やるだけ。解法はICPC 国内予選2015C ICPC 計算機 AOJ1602 - intさわだんのBlack Historyと完全に同じ

#include <bits/stdc++.h>
#include <map>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};


char data[10010];
int poll[10010];
int sum[10010];

int main(){
    int z;
    cin >> z;
    for(int zz = 0;zz < z;zz++){
        cin >> data;
        int count = 0,k = 0;
        for(int i = 0;i < strlen(data);i++){
            if(data[i] == '['){
                k++;
                sum[count] = k;
                poll[count] = -1;
                count++;
            }else if(data[i] == ']'){
                k--;
            }else{ //数字の時
                int num = data[i] - '0';
                for(int j = i+1;j < strlen(data);j++){
                    if(data[j] != '[' && data[j] != ']'){
                        num = num * 10 + (int)(data[j] - '0');
                        i++;
                    }else{
                        break;
                    }
                }
                count--;
                poll[count] = num;
                count++;
            }
        }
        for(int i = 0;i < count;i++){
//            cout << sum[i] << " " << poll[i] << endl;
        }
        while(count > 1){
            int kmax = 0,o = 0;
            for(int i = 0;i < count;i++){
                if(sum[i] > kmax){
                    kmax = sum[i];
                    o = i;
                }
            }
            priority_queue<int, vector<int> , greater<int> >que;
            int len = 0;
            for(int i = o;i < count;i++){
                if(sum[i] == kmax && poll[i] != -1){
                    len++;
                    que.push(poll[i]);
                }else{
                    break;
                }
            }
            int ne = 0; // next
            for(int i = 0;i < (len+1)/2;i++){
                int q = que.top(); que.pop();
                ne += (q+1)/2;
            }
            poll[o-1] = ne*2 -1;
            for(int i = o+len;i < count;i++){
                poll[i-len] = poll[i];
                sum[i-len] = sum[i];
            }
            count -= len;
        }
        cout << (poll[0]+1)/2 << endl;
    }
}