2013国内予選 C. 階層民主主義

C. 階層民主主義

解法

• 第1段階では過半数ギリギリで勝つのが最適
• 第k段階(k>1)について考えると、
  • 過半数ギリギリの選挙区で勝てば良い
  • 勝つのに必要な票数が少ない方から半数の選挙区でだけ票を取る
  • 負けても良い選挙区では0票としてしまって良い

• という感じの計算を、inputを再帰下降で見ながらやってみたのが以下のコード

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

using namespace std;

int solve(const string& str, int& idx){
    int res = 0;
    ++idx;
    if(str[idx] != '['){
        while(isdigit(str[idx])){
            res = 10*res + str[idx]-'0';
            ++idx;
        }
        res = res/2+1;
    } else {
        vector<int> vi;
        while(str[idx] == '[')
            vi.push_back(solve(str, idx));
        sort(vi.begin(), vi.end());
        for(int i=0;i<vi.size()/2+1;i++)
            res += vi[i];
    }
    ++idx;
    return res;
}

int main(){
    int n; cin >> n;
    while(n--){
        string str; cin >> str;
        int idx = 0;
        cout << solve(str, idx) << endl;
    }
}