「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の
*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]]
||<
において最小得票数で勝利する問題に帰着する。このようにして上のアルゴリズムを再帰で繰り返し適用していけば良いことがわかる
