問題
ランクドペア方式は、すべての一対一の対戦を調べて勝者を決める方法です。投票者全員がすべての候補者に順位を付けます。a を b より上位にした投票者が、b を a より上位にした投票者より多ければ、候補者 a は候補者 b に勝ちます。この勝利の差は(a を好む投票者数)−(b を好む投票者数)です。両者の人数が同じ対戦は除外します。
- 勝利を差の大きい順に並べます。差が同じなら勝者の番号が小さい順、それも同じなら敗者の番号が小さい順にします。
- その順に勝利を見ていき、それぞれを勝者から敗者への矢印として確定させます。ただし、その矢印が確定済みの矢印と循環(閉路)を作る場合、つまり確定済みの矢印をたどって敗者から勝者にすでに到達できる場合は確定させず、その勝利は飛ばします。
- 確定した矢印が1本も向いていない候補者が勝者です。
ranked_pairs_winner(candidates, ballots) を実装してください。
入力
candidates: 候補者の名前。候補者 i は candidates[i] です。
ballots: 投票者1人につき1行で、候補者の番号(0始まり)を好きな順に並べたもの。各行にはすべての候補者がちょうど1回ずつ現れます。
出力
確定した矢印が向いていない候補者全員の名前を、candidates に現れる順に返してください。ふつうは1人ですが、同数の対戦があると複数になることがあり、投票がなければ全候補者になります。
制約
1 ≤ candidates の長さ ≤ 9
0 ≤ 投票数 ≤ 200
例
入力:
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"] です。
入力:
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用に調整されています。上記の説明と制約に従ってください。