「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]]
||<
において最小得票数で勝1利する問題に帰着する。あとははじめに書いたアルゴリズムを再帰で繰り返し適用していけば答えが求まる
解答ソースコードは以下
>||
#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;
}
||<
*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;
}
||<
