AOJ 1188 Hierarchical Democracy

解き直しました → http://tubo028.hatenablog.jp/entry/2013/09/09/182151

問題

ACM-ICPC 2013 国内予選のC問題です.
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1188

本番中にこの問題を見た時 貪欲法で解けるということには気づいたのですが,時間内に構文解析をしてデータ構造を作るというところまでできる自信がなかたため無視しました.
今解いてみるとデータ構造とか考えなくてもstd::stringのやり取りで十分だったので少し後悔しています.

どうやった

第1段階で勝つために必要な票数の最小値は,有権者数が小さい順に過半数個の選挙区を選び,それら全てで過半数の票を獲得する場合の合計です.
つまり,[[a1][a2][a3]...[an]]というn個(nは奇数)の選挙区で第1段階の選挙を行うとすると,
まず有権者数で昇順にソートし,
[[a1][a2][a3]...[an]] → [[a'1][a'2][a'3]...[a'n]]
前から floor(n/2)+1 個の選挙区で floor(ak/2)+1 票,全部で Σ[k=1,floor(n/2)+1]floor(a'k/2)+1 票を得ればよいということになります.

第p段階(1<p)でも同様に,Σ[k=1,floor(n/2)+1]floor(a'k)+1 票となります.(1<pの時は票数は全て必要なので2で割らない)

以上の貪欲法で,複数個の選挙区からなる選挙区 [[%d][%d]...[%d]] での最小の票数がわかるので,それ自体を1つの選挙区 [%d] とみなします.
これを第1段階から順に階層が1層だけになるまで繰り返します.

実装

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

using namespace std;

#define ALL(c) c.begin() , (c).end()

string to_s(const int & n){
    stringstream ss;
    ss << n; return ss.str();
}

int min_vote(vector<int> & a, bool half){
    sort(ALL(a));
    int rtn = 0;
    for(int i=0; i<a.size()/2+1; i++){
        rtn += half ? a[i]/2+1 : a[i];
    }
    return rtn;
}

string resize_tree(string in, bool half){
    for(int i=0; i<in.size()-2; i++){
        if(in[i] == '[' && in[i+1] == '[' && isdigit(in[i+2])){
            int j=i;
            while(!(isdigit(in[j]) && in[j+1] == ']' && in[j+2] == ']')) j++;
            string leafs(in.begin()+i+1 , in.begin()+j+2);
            vector<int> reg;
            int a = 0;
            for(int p=0; p<leafs.size(); p++){
                if(isdigit(leafs[p])){
                    a*=10;
                    a+=leafs[p]-'0';
                } else if(leafs[p] == ']'){
                    reg.push_back(a);
                    a=0;
                }
            }
            string resized = to_s(min_vote(reg,half));
            in.replace(i+1, leafs.size(), resized);
        }
    }
    return in;
}

void solve(string in){
    int d = 0;
    while(in[d] == '[') d++;
    for(int i=0; i<d-1; i++){
        in = resize_tree(in, i==0);
    }
    cout << in.substr(1, in.size()-2) << endl;
}

int main(){
    int n; cin >> n;
    while(n--){
        string in; cin >> in;
        solve(in);
    }
}

入力された文字列の中で
"[[[a11][a12]...[a1n]][[a21][a22]...[a2n]]...[[am1][am2]...[amn]]]"
の形をした部分を見つけ,そのなかの各 [[ak1][ak2]...[akn]] (1<=m<=k) での最小値 min_k で "[[ak1][ak2]...[akn]]" を置換するということをm回繰り返すと,最終的に
[[min_1][min_2]...[min_m]]
の形になります.
これを,文字列全体が "[%d]" の形になるまで,つまりカッコの深さ分だけ繰り返しています.

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