AOJ1188 Hierarchical Democracy

AOJ1188 Hierarchical Democracy

サイト

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1188&lang=jp

解説

[[123][4567][89]]

という得票のデータが与えられたとき、最少得票数で過半数の選挙区を治めたい

それぞれの選挙区の得票は必ず奇数票あるので、上のデータの、それぞれの値の半分+1の値 に変換してソートすると考えやすくなる。つまり

123, 4567, 89
↓半分
62,  2284, 45
↓ソート
45, 62, 4567

選挙区もまた奇数個あるので、このように処理すると45と62だけの票数を獲得すればこの選挙区において最小で過半数を獲得できる

換言すると上の昇順ソート列から、得票数の数の半分+1 の値の和を獲得すればよい。すなわち、45+62=107票が答えとなる

では以下のように括弧のネストが深くなった場合どうすればよいか

[[[123][4567][89]][[5][3][7][3][9]][[8231][3721][203][3271][8843]]]

これは次のようにイメージして問題を分割して考えると上の解き方と同じことすればよいとわかる

[  [[123][4567][89]]  [[5][3][7][3][9]]  [[8231][3721][203][3271][8843]]  ]

かたまりそれぞれに対し最少得票数は上のアルゴリズムに沿って

107, 7, 3599

と求められる。こうすると

[[107][7][3599]]

において最小得票数で勝利する問題に帰着する。あとははじめに書いたアルゴリズムを再帰で繰り返し適用していけば答えが求まる

解答ソースコードは以下

#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;
 
const char *p;
 
int solve() {
  int ret = 0;
   
  ++p;
  if(*p == '[') {
    vector<int> v;
    while(*p == '[') v.push_back(solve());
    sort(v.begin(), v.end());
    for(int i = v.size()/2; i>=0; i--) ret += v[i];
  } else {
    char *e;
    ret = strtol(p, &e, 10)/2 + 1;
    p = e;
  }
  ++p;
  return ret;
}
 
int main() {
  int n;
  string s;
  cin >> n;
  for(int i = 0; i < n; i++) {
    cin>>s;
    p = s.c_str();
    cout << solve() << endl;
  }
  return 0;
}
最終更新:2013年11月01日 22:10