AOJ 1188: Hierarchical Democracy

問題

Hierarchical Democracy | Aizu Online Judge

• [[[99][59][63][85][51]][[1539][7995][467]][[51][57][79][99][3][91][59]]]という形で与えられる選挙区の区割りから、当選するために必要な最低得票数を求めよ
• [99]とある場合はその選挙区に99人の有権者がおり、過半数の得票を得ると1段階目の選挙区で勝利する。（有権者数が奇数であることは保証される）
• [[99][59][63][85][51]]とあるときは5つの選挙区があり、過半数の選挙区で勝利するとその2段階目の選挙区で勝利する（選挙区数が奇数であることが保証される）
• [[[99][59][63][85][51]][[1539][7995][467]][[51][57][79][99][3][91][59]]]とあるときは3つの2段階目の選挙区があり、過半数の2段階目の選挙区で勝利すると勝利する（奇数であることは保証される）
• このような階層構造がある中で、一番上の段階で勝利すると全体で当選することができる

方針

• [99]のように数字のみが入っている場合は過半数n/2+1票取るのが最小
• [[3][5][7]]のように2段階あるときは各選挙区の過半数をソートして少ないものからn/2+1選挙区分足すのが最小
• [[[1][3][5]][[3][5][7]][[5][7][9]]]のように3段階以上あるときは、まず内側の選挙区について最小を求め、[[3][5][7]]のように潰して2段階の場合に帰着させる
• 構文解析っぽいので構文解析 Howto · GitHubを参考にした

コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)

int getNumber(string& s, int* i) {
    int n = 0;
    while(s[(*i)] != ']') {
        n *= 10;
        n += s[*i]-'0';
        (*i)++;
    }
    return n;
}

int analyze(string& s, int* i) {
    if(s[(*i)] != '[') {
        cerr << "error!" << endl;
        return -1;
    }
    if(s[++(*i)] != '[') {
        return getNumber(s, i)/2 + 1;
    }
    vector<int> a;
    while(s[(*i)] == '[') {
        a.push_back(analyze(s, i));
        (*i)++;
    }
    sort(a.begin(), a.end());
    int ans = 0;
    rep(k, a.size()/2+1) ans += a[k];
    return ans;
}

int main(void){
    int n;
    string s;
    getline(cin, s);
    sscanf(s.c_str(), "%d", &n);
    rep(data, n) {
        getline(cin, s);
        int i = 0;
        cout << analyze(s, &i) << endl;
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1904350

反省

• カッコの内容を抜き出す方法とかがよく分からなかったので構文解析の方法をかなり見てしまった
• 最初のnの読み込みはcin.ignore()でOK
• エイヤでやったら一発ACして楽しかった