AOJ 1188 階層民主主義

ICPCに参加することになりました。よろしくお願いします。ということで少し練習しようかな,と。

2013年 会津大会 の問題を解いてみましたが,問題Cと問題Dは無事正解できました。多分AとBはできると思うのでこの年だと(自分だけなら)4完ですかね。

問題

階層民主主義 | Aizu Online Judge

解法

この階層選挙は木の構造になるのでそれぞれの木の頂点に対して「その選挙区を取るには最低何票必要か」を示す木DPを解く。

第一段階では(有権者+1)/2が最低必要な人数である。第k段階では,その頂点の下の(k-1)段階目で必要な人数をソートして過半数選挙区を取るのに必要な人数を小さい順に求めていく。

一番難しいのはこのようなデータ構造にするために入力をどう整理するか,ということだが,"["を見たら木の深さを一つ深くしたノードを見に行って,"]"を見たら木の深さを一段浅くしたノードを見に行く,というようにすれば自然に木構造が出来上がる。

結構面白い問題でした。

struct node {
    ll cost;
    vector<node*> next;
    node* before;
    node(ll c) : cost(c) {}
    node() : cost(0) {}
};

ll dfs(node* now) {
    if (now->cost != 0) return now->cost;
    int n = (now->next).size();
    vector<ll> score;
    for (int i = 0; i < n; i++) {
        score.push_back(dfs(now->next[i]));
    }
    sort(score.begin(), score.end());
    ll ret = 0;
    for (int i = 0; i < (n+1)/2; i++) {
        ret += score[i];
    }
    return ret;
}

void solve(const string& s) {
    // 木を作る
    node* root = new node();
    node* now = root;
    int cur = 0;
    int n = s.size();
    while (1) {
        if (cur >= n) break;
        if (s[cur] == '[') {
            node* tmp = new node();
            tmp->before = now;
            now->next.push_back(tmp);
            now = tmp;
            cur++;
        } else if (s[cur] == ']') {
            now = now->before;
            cur++;
        } else {
            int i = cur;
            int tmp = 0;
            while (1) {
                if (!isdigit(s[i])) break;
                else tmp = tmp*10 + (s[i]-'0');
                i++;
            }
            cur = i;
            now->cost = (tmp+1) / 2;
        }
    }
    // 解く
    cout << dfs(root) << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        string s;
        cin >> s;
        solve(s);
    }
    return 0;
}