AOJ 1188 Hierarchical Democracy (改善版)

前回 :

TLEにはなりませんでしたが，頻繁にstringをやりとりしている点など無駄が多いのでそのうちやりなおします．

ということでやり直した．

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cctype>

using namespace std;

string str;
int p;

bool isopen(int p){
    return str[p] == '[';
}

bool isclose(int p){
    return str[p] == ']';
}

int dig(){
    return str[p++] - '0';
}

int num(){
    int n = 0; 
    while(isdigit(str[p])){
        n*=10;
        n+=dig();
    }
    return n;
}

int first(){
    vector<int> fir;
    p++; // jump [
    while(isopen(p)){
        p++; // jump [
        fir.push_back(num());
        p++; // jump ]
    }
    p++; // jump ]
    int ans = 0;
    sort(fir.begin() , fir.end());
    for(int i=0; i<fir.size()/2+1; i++){
        ans += fir[i]/2+1;
    }
    return ans;
}

int second(){
    if(isopen(p) && isopen(p+1) && isopen(p+2)){
        // some firsts
        p++; // jump [
        vector<int> sec;
        while(isopen(p)){
            sec.push_back(second());
        }
        p++; // jump ]
        int n = 0;
        sort(sec.begin() , sec.end());
        for(int i=0; i<sec.size()/2+1; i++){
            n+=sec[i];
        }
        return n;
    } else {
        // first
        return first();
    }
}

int main(){
    int n;
    cin >> n;
    while(n--){
        p = 0;
        cin >> str;
        cout << second() << endl;
    }
}