Runoff

次のように、決選投票を実行するプログラムを実装します。

./runoff Alice Bob Charlie
Number of voters: 5
Rank 1: Alice
Rank 2: Bob
Rank 3: Charlie

Rank 1: Alice
Rank 2: Charlie
Rank 3: Bob

Rank 1: Bob
Rank 2: Charlie
Rank 3: Alice

Rank 1: Bob
Rank 2: Alice
Rank 3: Charlie

Rank 1: Charlie
Rank 2: Alice
Rank 3: Bob

Alice

背景

選挙の勝者を決定するための非常に単純なアルゴリズムである多数決選挙については、すでにご存知でしょう。すべての投票者が1票を獲得し、最も多くの票を持つ候補者が勝利します。

しかし、多数決にはいくつかの欠点があります。例えば、3人の候補者がいて下の投票が行われる選挙ではどうなるでしょうか?

多数決では、AliceとBobはそれぞれ2つの票を持っているので引き分けとなります。しかし、それは正しい結果なのでしょうか？

別の種類の投票システムとして、順位選択制があります。順位選択制では、有権者は複数の候補者に投票することができます。トップの候補者に投票するだけでなく、優先順位に従って候補者をランク付けできます。したがって、投票結果は次のようになります。

Three ballots, with ranked preferences

ここでは、各投票者は、第1候補を特定することに加え、第2および第3の候補も示しています。すると、以前は引分けだったのが、今では勝者が出る可能性があります。もともとAliceとBobが引き分けたので、Charlieは落選します。ですが、Charlieを選んだ有権者は、BobよりもAliceを選びました。ですので、ここではAliceが勝者と言えるでしょう。

順位選択制はまた、多数決のさらに別の潜在的な欠点を解決することができます。次の投票用紙を見てください。

誰がこの選挙に勝つべきでしょうか。各投票者が第一候補のみを選択する多数決では、Charlieは4票でこの選挙に勝ち、Bobは3票、Aliceは2票です。しかし、有権者の大半 (9人のうち5人) は、CharlieではなくAliceかBobの方が喜ぶでしょう。順位の選好を考慮することで、順位選択制は有権者の選好をよりよく反映する勝者を選ぶことができるでしょう。

そのような順位投票制度の一つが、即時決選投票制度 (Runoff) です。即時決選投票では、有権者は希望する数の候補者を順位づけすることができます。いずれかの候補者が最初の優先投票の過半数 (50%以上) を得れば、その候補者が選挙の勝者と宣言されます。

50%以上の得票率の候補者がいなければ、 「決選投票」 が行わます。得票数が最も少なかった候補者は選挙から除外され、最初にその候補者を第一希望として選んだ投票者は、第二希望を考慮することになります。なぜこのようなことをするのでしょうか？これは事実上、最も人気のない候補者が最初から選挙に参加していなかったとしたら何が起こっていたかをシミュレーションしています。

このプロセスは繰り返されます。どの候補も投票の過半数を持っていない場合、最後の候補者は削除され、彼らに投票した人は代わりに (まだ削除されていない) 次点の候補者に投票します。候補者が過半数を獲得すると、その候補者が勝者と宣言されます。

上の9票を見て、決選投票がどのように行われるかを見てみましょう。

Aliceは2票、Bobは3票、Charlieは4票です。9人の中で選挙に勝つには過半数 (5票) が必要です。誰も過半数を持っていないので、さらに決選投票が必要です。Aliceが一番少ない (2票しかない) ので、Aliceは落選します。最初にAliceに投票した有権者はBobを2番目に選んだので、Bobはさらに2票を獲得します。Bobは今5票を持っていて、Charlieは4票を持っているままです。Bobが過半数を獲得し、Bobが勝者と宣言されました。

どのようなコーナーケースを検討する必要があるでしょうか？

1つの可能性は、候補者を削除するときにタイとなる場合です。最下位の候補者は全員落選として、そのようなシナリオに対処することができます。ですが、残っているすべての候補者の投票数が同じであれば、同点の最下位候補を排除することは、全員を排除することを意味します。その場合は、全員を排除しないように注意し、残りのすべての候補者の間で同点を宣言するだけです。

即時決選投票の中には、投票者がすべての候補者をすべて順位づけする必要がないものもあります。そのため、1回の選挙で5人の候補者がいる場合でも、投票者は2人しか選ばない場合があります。しかし、この問題では、私たちはそのようなコーナーケースは無視し、すべての有権者がすべての候補者を好きに順位づけすると仮定しましょう。

これは多数決よりは少し複雑に見えます。しかし、選挙の勝者が有権者の選好をより正確に反映する選挙制度であるという利点はほぼ間違いないでしょう。

始め方

ここでは、この問題の配布コード (スターターコード) をCS50 IDEにダウンロードする方法を説明します。CS50 IDEにログインし、ターミナルウィンドウで次の各コマンドを実行します。

  • すでに存在しているpset3 ディレクトリに移動します。
  • mkdir runoffを実行して、pset3 ディレクトリにrunoff というディレクトリを作成 (新規作成) します。
  • cd runoffを実行して、そのディレクトリに移動 (ディレクトリを開く) します。
  • wget https://cdn.cs50.net/2020/fall/psets/3/runoff/runoff.cを実行して、この問題の配布コードをダウンロードします。
  • lsを実行します。この問題の配布コードは、runoff.cというファイルにあります。

理解を深める

runoff.cを開いて、すでに書かれているコードを見てみましょう。ここでは、2つの定数MAX_CANDIDATES (選挙の候補者の最大数) とMAX_VOTERS (選挙の有権者の最大数) を定義しています。

次は2次元配列preferencesの設定です。配列preferences[i]は、投票者番号iのすべての選好を表し、整数preferences[i][j]は、投票者iのj番目の選好である候補者のインデックスを格納します。

次はcandidateと呼ばれる構造体　(struct) です。すべての候補者には、名前の文字列フィールドと、現在所有している投票数votesを表すint、および候補者が選挙から除外されたかどうかを示すeliminatedというbool値があります。配列candidatesで、選挙のすべての候補者を追跡します。

このプログラムには、voter_countとcandidate_countという2つのグローバル変数もあります。

mainに移りましょう。候補者の数と投票者の数を決定した後、main関数の投票ループが開始され、すべての投票者に投票の機会が与えられます。投票者が選好を入力すると、vote関数が呼び出され、すべての選好を追跡します。いずれかの時点で、投票が無効と見なされた場合、プログラムは終了します。

すべての投票が終わると、次のループが始まります。このループは、勝者をチェックし、勝者が見つかるまで最後の順位の候補者を削除する決選投票のプロセスを繰り返します。

最初に呼び出すのはtabulateと呼ばれる関数で、これは有権者の選好をすべて調べ、まだ落選していない各有権者のトップ候補を見て、現在の投票総数を計算します。次に、print_winner関数は勝者が1人いる場合それを出力します。その場合、プログラムは終了します。しかし、そうでなければ、プログラムは、選挙に残っている候補者の中で最も少ない得票数を決定する必要があります (find_minの呼び出しによって)。選挙に参加しているすべての候補者が (is_tie関数によって決定される) 同数の票を持っていることが判明した場合、その選挙は引き分けと宣言されます。そうでなければ、最も少ない得票数の候補者 (複数可) は、eliminate関数の呼び出しを介して選挙から削除されます。

このファイルをさらに詳しく見ると、これらの関数 (vote、tabulate、print_winner、find_min、is_tie、およびeliminate) はすべて、あなたが完了しなければならないことがわかります！

仕様

決選投票をシミュレートするようにrunoff.cの実装を完了します。vote、tabulate、print_winner、find_min、is_tie、およびeliminateの実装を完了する必要があります。それ以外のrunoff.c内のものは変更しないでください (必要に応じて、追加のヘッダファイルは含めます)。

vote

vote 関数を実装します。

  • この関数は、引数voter、rankおよびnameを取ります。name が有効な候補者の名前と一致する場合は、グローバル配列preferencesを更新して、有権者voter がその候補者を優先順位rank として持つことを示す必要があります(ここで、0は最初の選好、1は2番目の選好などです)。
  • 選好が正常に記録された場合、関数はtrueを返します。それ以外の場合 (例えば、name が候補者の1人の名前ではない場合) はfalse を返します。
  • 2人の候補者が同じ名前を持つことはないと想定できます。

ヒント

  • candidate_countには、選挙の候補者の数が格納されることを思い出してください。
  • strcmpを使用して2つの文字列を比較できることを思い出してください。
  • preferences[i][j]はi番目の投票者のj番目の優先順位である候補者のインデックスを格納することを思い出してください。

tabulate

tabulate 関数を実装します。

  • この関数は、各候補者の決選投票の現段階での得票数votesを更新する必要があります。
  • 決選投票の各段階で、すべての有権者が、まだ落選していない最優先候補者に投票することを思い出しましょう。

ヒント

  • voter_countには、選挙の有権者数が格納されることを思い出してください。
  • 投票者iに対して、第１候補者はpreferences[i][0]で表され、第2候補者はpreferences[i][1]で表されることを思い出しましょう。
  • 構造体candidateには、候補が選挙から除外された場合にtrueとなるeliminatedと呼ばれるフィールドがあることを思い出してください。
  • 構造体candidateにはvotesと呼ばれるフィールドがあり、各投票者が選好する候補者に対して更新することができます。

print_winner

print_winner関数を実装します。

  • いずれかの候補が過半数の票を持っている場合、その名前をstdoutに出力し、関数はtrueを返します。
  • まだ誰も選挙に勝っていない場合、この関数はfalseを返します。

ヒント

  • voter_countには、選挙の有権者数が格納されることを思い出してください。では、当選に必要な票数はどのように表現しますか?

find_min

find_min関数を実装します。

  •  この関数は、まだ選挙に残っている候補者の最小投票総数を返す必要があります。

ヒント

  • 候補者をループして、まだ選挙に残っていて投票数が最も少ない候補者を探すのが良いでしょう。候補者をループするとき、どのような情報を記録しておくべきですか?

is_tie

is_tie関数を実装します。

  • この関数は引数minを取ります。これは選挙に参加している候補者の得票数の最小値です。
  • この関数は、選挙に残っているすべての候補者の投票数が同じ場合はtrueを返し、そうでない場合はfalseを返します。

ヒント

  • 選挙に残っているすべての候補者が得票数の場合には、引き分けが起こることを思い出してください。is_tie関数が引数minを取ることにも注意してください。これは、候補者の現在の得票数の最小値です。その情報を使用して、選挙が引き分けであるかどうか (引き分けでないかどうか) を判断するにはどうすればよいでしょうか。

eliminate

eliminate関数を実装します。

  • この関数は引数minを取ります。これは選挙に参加している候補者の現在の得票数の最小値です。
  • この関数は、得票数minの候補者を除外する必要があります。

ウォークスルー

使い方

プログラムは次の例のように動作します。

./runoff Alice Bob Charlie
Number of voters: 5
Rank 1: Alice
Rank 2: Charlie
Rank 3: Bob

Rank 1: Alice
Rank 2: Charlie
Rank 3: Bob

Rank 1: Bob
Rank 2: Charlie
Rank 3: Alice

Rank 1: Bob
Rank 2: Charlie
Rank 3: Alice

Rank 1: Charlie
Rank 2: Alice
Rank 3: Bob

Alice

テスト

コードをテストして以下を処理できることを確認してください。

  • 任意の数の候補者による選挙 (MAX の9まで)
  • 候補者の氏名による投票
  • 投票に参加していない候補者に対する無効な投票
  • 当選者が1人の場合は当選者を印刷
  • 残りの候補者全員が同点の場合、誰も排除しない

check50を使用して以下を実行し、コードの正確さを評価してください。ただし、コンパイルとテストは必ず自分で行ってください。

check50 cs50/problems/2021/x/runoff

以下を実行し、style50を使用してコードのスタイルを評価します。

style50 runoff.c

提出方法

次のコマンドを実行し、GitHubのユーザー名とパスワードを入力してログインします。セキュリティのため、パスワードには実際の文字ではなくアスタリスク (*) が表示されます。

submit50 cs50/problems/2021/x/runoff