すべてのチャレンジ
難しい 0件解決済み 正答率0%

ランクドペア方式の勝者

一対一の勝利のうち循環を作らないものだけを確定させ、ランクドペア方式で選挙の勝者を求めます。

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

  • 順位付き投票から一対一の選好表を作る
  • 同点時のルールどおりに勝利を差で並べ替える
  • グラフに閉路ができない場合だけ辺を確定させる

問題

原文(英語)を表示

ランクドペア方式は、すべての一対一の対戦を調べて勝者を決める方法です。投票者全員がすべての候補者に順位を付けます。a を b より上位にした投票者が、b を a より上位にした投票者より多ければ、候補者 a は候補者 b に勝ちます。この勝利の差は(a を好む投票者数)−(b を好む投票者数)です。両者の人数が同じ対戦は除外します。

  1. 勝利を差の大きい順に並べます。差が同じなら勝者の番号が小さい順、それも同じなら敗者の番号が小さい順にします。
  2. その順に勝利を見ていき、それぞれを勝者から敗者への矢印として確定させます。ただし、その矢印が確定済みの矢印と循環(閉路)を作る場合、つまり確定済みの矢印をたどって敗者から勝者にすでに到達できる場合は確定させず、その勝利は飛ばします。
  3. 確定した矢印が1本も向いていない候補者が勝者です。

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

入力

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

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

出力

確定した矢印が向いていない候補者全員の名前を、candidates に現れる順に返してください。ふつうは1人ですが、同数の対戦があると複数になることがあり、投票がなければ全候補者になります。

制約

1 ≤ candidates の長さ ≤ 9

0 ≤ 投票数 ≤ 200

例

例 1
入力:
candidates = ["Ann", "Bob", "Cal"]
ballots = [
    [0, 1, 2],
    [0, 1, 2],
    [0, 1, 2],
    [1, 2, 0],
    [1, 2, 0],
    [2, 0, 1],
    [2, 0, 1],
    [2, 0, 1],
    [2, 0, 1]
]

期待される出力:
expected = ["Cal"]
入力:
std::vector<std::string> candidates = {"Ann", "Bob", "Cal"};
std::vector<std::vector<long long>> ballots = {
    {0, 1, 2},
    {0, 1, 2},
    {0, 1, 2},
    {1, 2, 0},
    {1, 2, 0},
    {2, 0, 1},
    {2, 0, 1},
    {2, 0, 1},
    {2, 0, 1}
};

期待される出力:
std::vector<std::string> expected = {"Cal"};
入力:
string[] candidates = new string[] {"Ann", "Bob", "Cal"};
long[][] ballots = new long[][] {
    new long[] {0, 1, 2},
    new long[] {0, 1, 2},
    new long[] {0, 1, 2},
    new long[] {1, 2, 0},
    new long[] {1, 2, 0},
    new long[] {2, 0, 1},
    new long[] {2, 0, 1},
    new long[] {2, 0, 1},
    new long[] {2, 0, 1}
};

期待される出力:
string[] expected = new string[] {"Cal"};

解説

Cal は Ann に6対3で勝ち(差3)、Ann は Bob に7対2で勝ち(差5)、Bob は Cal に5対4で勝ちます(差1)。まず Ann→Bob を確定し、次に Cal→Ann を確定します。Bob→Cal は循環を作るので飛ばします。Cal に向かう矢印はないので ["Cal"] です。

例 2
入力:
candidates = ["Ann", "Bob"]
ballots = [
    [0, 1],
    [1, 0]
]

期待される出力:
expected = ["Ann", "Bob"]
入力:
std::vector<std::string> candidates = {"Ann", "Bob"};
std::vector<std::vector<long long>> ballots = {
    {0, 1},
    {1, 0}
};

期待される出力:
std::vector<std::string> expected = {"Ann", "Bob"};
入力:
string[] candidates = new string[] {"Ann", "Bob"};
long[][] ballots = new long[][] {
    new long[] {0, 1},
    new long[] {1, 0}
};

期待される出力:
string[] expected = new string[] {"Ann", "Bob"};

解説

Ann と Bob は1対1の同数なので矢印は確定せず、2人とも返します。結果は ["Ann", "Bob"] です。

解き方のヒント

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

各投票用紙では、どの候補者もそれより下位の全員より好まれています。

ヒント 2

勝者から敗者への矢印を確定する前に、確定済みの矢印をたどって敗者から探索しましょう。勝者に到達したら飛ばします。

ヒント 3

最後に、確定した矢印が1本も入ってこない候補者が勝者です。

目安の計算量

時間 O(b × c^2 + c^4)、追加メモリ O(c^2)

参考資料

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

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

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

他の人の解答から学ぶ

コミュニティの解答

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