中級 0件解決済み 正答率0%

即時決選投票

順位付き投票で即時決選投票を行い、ラウンドごとに最も弱い候補者を落としていきます。

このチャレンジで学べること

  • 各投票用紙を、残っている中で最上位の候補者の票として数える
  • 過半数による当選と全員同点を判定する
  • 最少得票の候補者をすべて落とす

問題

原文(英語)を表示

即時決選投票では、投票者全員がすべての候補者に順位を付けます。開票はラウンドごとに進みます。

  1. 各投票用紙は、まだ残っている候補者のうち最も順位の高い人への1票として数えます。
  2. 全投票数の過半数を得た候補者がいれば、その人が当選です。
  3. そうでなく、残っている候補者全員の得票数が同じなら、全員が同点のまま選挙は終わります。
  4. それ以外の場合は、得票数が最も少ない候補者を落選させ(最少得票で並んだ人が複数いれば一度に全員)、新しいラウンドを始めます。

runoff_election(candidates, ballots) を実装してください。

入力

candidates: 候補者の名前。候補者 i は candidates[i] です。

ballots: 投票者1人につき1行で、候補者の番号(0始まり)を好きな順に並べたもの。各行にはすべての候補者がちょうど1回ずつ現れます。

出力

当選者の名前1つを含むリストを返してください。同点で終わった場合は、同点の候補者全員の名前を candidates に現れる順に返します。投票がなければ全候補者が同点です。

制約

1 ≤ candidates の長さ ≤ 9

0 ≤ 投票数 ≤ 200

例

例 1
入力:
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"] です。

例 2
入力:
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用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。