問題
即時決選投票では、投票者全員がすべての候補者に順位を付けます。開票はラウンドごとに進みます。
- 各投票用紙は、まだ残っている候補者のうち最も順位の高い人への1票として数えます。
- 全投票数の過半数を得た候補者がいれば、その人が当選です。
- そうでなく、残っている候補者全員の得票数が同じなら、全員が同点のまま選挙は終わります。
- それ以外の場合は、得票数が最も少ない候補者を落選させ(最少得票で並んだ人が複数いれば一度に全員)、新しいラウンドを始めます。
runoff_election(candidates, ballots) を実装してください。
入力
candidates: 候補者の名前。候補者 i は candidates[i] です。
ballots: 投票者1人につき1行で、候補者の番号(0始まり)を好きな順に並べたもの。各行にはすべての候補者がちょうど1回ずつ現れます。
出力
当選者の名前1つを含むリストを返してください。同点で終わった場合は、同点の候補者全員の名前を candidates に現れる順に返します。投票がなければ全候補者が同点です。
制約
1 ≤ candidates の長さ ≤ 9
0 ≤ 投票数 ≤ 200
例
入力:
candidates = ["Ana", "Bo", "Cy"]
ballots = [
[0, 1, 2],
[0, 2, 1],
[1, 2, 0],
[1, 0, 2],
[2, 0, 1]
]
期待される出力:
expected = ["Ana"]
入力:
std::vector<std::string> candidates = {"Ana", "Bo", "Cy"};
std::vector<std::vector<long long>> ballots = {
{0, 1, 2},
{0, 2, 1},
{1, 2, 0},
{1, 0, 2},
{2, 0, 1}
};
期待される出力:
std::vector<std::string> expected = {"Ana"};
入力:
string[] candidates = new string[] {"Ana", "Bo", "Cy"};
long[][] ballots = new long[][] {
new long[] {0, 1, 2},
new long[] {0, 2, 1},
new long[] {1, 2, 0},
new long[] {1, 0, 2},
new long[] {2, 0, 1}
};
期待される出力:
string[] expected = new string[] {"Ana"};
解説
ラウンド1は Ana 2票、Bo 2票、Cy 1票で、2.5票を超えた人はいないので Cy が落選します。Cy の票は Ana に移り、Ana が5票中3票で当選します。結果は ["Ana"] です。
入力:
candidates = ["Ana", "Bo", "Cy"]
ballots = [
[0, 1, 2],
[0, 1, 2],
[1, 2, 0],
[1, 2, 0],
[2, 1, 0],
[2, 1, 0]
]
期待される出力:
expected = ["Ana", "Bo", "Cy"]
入力:
std::vector<std::string> candidates = {"Ana", "Bo", "Cy"};
std::vector<std::vector<long long>> ballots = {
{0, 1, 2},
{0, 1, 2},
{1, 2, 0},
{1, 2, 0},
{2, 1, 0},
{2, 1, 0}
};
期待される出力:
std::vector<std::string> expected = {"Ana", "Bo", "Cy"};
入力:
string[] candidates = new string[] {"Ana", "Bo", "Cy"};
long[][] ballots = new long[][] {
new long[] {0, 1, 2},
new long[] {0, 1, 2},
new long[] {1, 2, 0},
new long[] {1, 2, 0},
new long[] {2, 1, 0},
new long[] {2, 1, 0}
};
期待される出力:
string[] expected = new string[] {"Ana", "Bo", "Cy"};
解説
6票のうち、どの候補者も1位票が2票ずつなので、3人とも同点です。結果は ["Ana", "Bo", "Cy"] です。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
誰がまだ残っているかを true/false のリストで管理し、毎ラウンド最初から数え直しましょう。
ヒント 2
過半数とは、票数 × 2 が投票総数より大きいことです。
ヒント 3
最少得票は残っている候補者の中だけで求めます。残っている全員がその票数なら、選挙は同点です。
目安の計算量
時間 O(c^2 × b)、追加メモリ O(c)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。