Runoff - CS50x 2026

解決すべき問題

あなたはすでに、選挙の勝者を決定するための非常にシンプルなアルゴリズムに従う最多得票選挙（plurality elections）について知っています。すべての有権者が1票を投じ、最も多くの票を獲得した候補者が勝利するというものです。

しかし、最多得票制にはいくつかの欠点があります。例えば、3人の候補者がいて、以下のような投票が行われた場合はどうなるでしょうか。

5つの投票用紙、AliceとBobが同点

最多得票制では、AliceとBobがそれぞれ2票ずつ獲得しているため、ここでは同点と宣言されます。しかし、それは正しい結果でしょうか。

優先順位付投票制（ranked-choice voting system）として知られる別の種類の投票システムがあります。優先順位付投票制では、有権者は複数の候補者に投票することができます。単に第一希望の候補者に投票するのではなく、好みの順に候補者をランク付けすることができます。その結果、投票用紙は以下のようになります。

優先順位が付けられた5つの投票用紙

ここでは、各有権者は第一希望の候補者を指定するだけでなく、第二希望と第三希望も示しています。これにより、以前は同点だった選挙に勝者が現れる可能性があります。もともとAliceとBobが同点であり、Charlieは圏外でした。しかし、Charlieを選んだ有権者はBobよりもAliceを好んでいたため、ここではAliceが勝者として宣言される可能性があります。

優先順位付投票制は、最多得票制のもう一つの潜在的な欠点も解決できます。以下の投票用紙を見てください。

優先順位が付けられた9つの投票用紙

この選挙では誰が勝つべきでしょうか。各有権者が第一希望のみを選択する最多得票制では、Bobの3票、Aliceの2票に対し、Charlieが4票を獲得してこの選挙に勝利します。しかし、有権者の過半数（9人中5人）は、CharlieよりもAliceまたはBobの方を好んでいます。ランク付けされた好みを考慮することで、投票システムは有権者の好みをより良く反映した勝者を選ぶことができるかもしれません。

そのような優先順位付投票制の一つが、即時決選投票制（instant runoff system）です。即時決選投票では、有権者は希望する数だけ候補者をランク付けできます。いずれかの候補者が第一希望の票の過半数（50%超）を獲得した場合、その候補者が選挙の勝者となります。

過半数の票を獲得した候補者がいない場合は、「即時決選（instant runoff）」が発生します。最も得票数の少なかった候補者が選挙から除外され、その候補者を第一希望として選んでいた人の票は、次に第二希望が考慮されます。なぜこのようにするのでしょうか。実質的にこれは、もし最も不人気な候補者が最初から選挙に参加していなかったらどうなっていたかをシミュレートしています。

このプロセスが繰り返されます。どの候補者も過半数の票を獲得していない場合、最下位の候補者が除外され、その候補者に投票した人は代わりに（まだ除外されていない）次の希望の候補者に投票します。候補者が過半数を獲得すると、その候補者が勝者として宣言されます。

最多得票制よりも少し複雑に聞こえますね。しかし、選挙の勝者が有権者の好みをより正確に表す選挙システムであるという利点があると言えます。runoffというフォルダの中のrunoff.cというファイルで、即時決選投票をシミュレートするプログラムを作成してください。

デモ

配布コード

配布コードをダウンロードする

cs50.devにログインし、ターミナルウィンドウをクリックして、cdを単独で実行します。ターミナルウィンドウのプロンプトが以下のようになっていることを確認してください。

$

次に、以下のコマンドを実行して、

wget https://cdn.cs50.net/2026/x/psets/3/runoff.zip

runoff.zipというZIPファイルをcodespaceにダウンロードします。

次に、

unzip runoff.zip

を実行して、runoffというフォルダを作成します。ZIPファイルはもう必要ないので、

rm runoff.zip

を実行し、プロンプトで「y」に続いてEnterを押して、ダウンロードしたZIPファイルを削除します。

次に、

cd runoff

に続いてEnterを押し、そのディレクトリに移動（つまり開く）します。プロンプトは以下のようになっているはずです。

runoff/ $

すべてが成功していれば、

ls

を実行すると、runoff.cという名前のファイルが表示されるはずです。code runoff.cを実行すると、この問題セットのコードを記述するファイルが開きます。もし表示されない場合は、手順を振り返って、どこで間違えたかを確認してください。

runoff.cのコードを理解する

既存のコードの機能を拡張する場合は、まず現在の状態を理解しておくのが最善です。

まず、runoff.cの冒頭を見てください。2つの定数が定義されています。選挙における候補者の最大数を示すMAX_CANDIDATESと、有権者の最大数を示すMAX_VOTERSです。

// Max voters and candidates
#define MAX_VOTERS 100
#define MAX_CANDIDATES 9

MAX_CANDIDATESが配列candidatesのサイズ指定に使用されていることに注目してください。

// Array of candidates
candidate candidates[MAX_CANDIDATES];

candidatesはcandidate型の配列です。runoff.cでは、candidateはstruct（構造体）です。すべてのcandidateには、名前のためのstringフィールドname、現在持っている票数を示すint型のvotes、そしてその候補者が選挙から除外されたかどうかを示すbool値のeliminatedがあります。配列candidatesは、選挙のすべての候補者を追跡します。

// Candidates have name, vote count, eliminated status
typedef struct
{
    string name;
    int votes;
    bool eliminated;
}
candidate;

これで、2次元配列であるpreferencesをよりよく理解できるでしょう。配列preferences[i]は、有権者番号iのすべての好みを表します。整数preferences[i][j]は、有権者iにとってj番目の好みである候補者の、candidates配列におけるインデックスを格納します。

// preferences[i][j] is jth preference for voter i
int preferences[MAX_VOTERS][MAX_CANDIDATES];

プログラムには、voter_count（有権者数）とcandidate_count（候補者数）という2つのグローバル変数もあります。

// Numbers of voters and candidates
int voter_count;
int candidate_count;

次にmain関数です。候補者数と有権者数を決定した後、メインの投票ループが始まり、すべての有権者に投票の機会が与えられます。有権者が好みを入力すると、それらすべての好みを追跡するためにvote関数が呼び出されます。もし途中で投票用紙が無効であると判断された場合、プログラムは終了します。

すべての投票が完了すると、別のループが始まります。このループは、勝者が決まるまで、勝者のチェックと最下位候補者の除外を行う即時決選投票のプロセスを繰り返します。

ここでの最初の呼び出しはtabulateという関数で、これはすべての有権者の好みを確認し、まだ除外されていない各有権者の最優先候補を確認することで、現在の得票総数を計算します。次に、print_winner関数は、勝者がいればその名前を出力します。勝者がいればプログラムは終了です。そうでなければ、プログラムは（find_minの呼び出しを通じて）選挙に残っている誰かが獲得した最小得票数を決定する必要があります。もし選挙に残っている全員が同じ得票数で同点である（is_tie関数によって判断される）ことが判明した場合、選挙は引き分けと宣言されます。そうでなければ、最下位の候補者（または複数の候補者）はeliminate関数の呼び出しを通じて選挙から除外されます。

ファイルのさらに下の方を見ると、残りの関数（vote、tabulate、print_winner、find_min、is_tie、eliminate）がすべて未完成であり、あなたが完成させる必要があることがわかります。runoff.cのこれらの関数のみを変更してください。ただし、必要に応じてrunoff.cの先頭に追加のヘッダーファイルを#includeしても構いません。

ヒント

以下のトグルをクリックしてアドバイスを読んでください。

vote関数を完成させる

vote関数を完成させます。

  • この関数は、voter（有権者）、rank（順位）、name（名前）の3つの引数を取ります。
  • nameが有効な候補者の名前と一致する場合、有権者voterがその候補者をrank番目の好みとして持っていることを示すように、グローバルなpreferences配列を更新する必要があります。（0が第一希望、1が第二希望などとなることに注意してください）。同じ名前を持つ候補者は二人といないと想定して構いません。
  • 好みが正常に記録された場合、関数はtrueを返す必要があります。そうでなければ、関数はfalseを返す必要があります。例えば、nameが候補者の名前のいずれでもない場合などを考慮してください。

コードを書く際は、以下のヒントを考慮してください。

  • candidate_countには、選挙の候補者数が格納されていることを思い出してください。
  • 2つの文字列を比較するにはstrcmpを使用できることを思い出してください。
  • preferences[i][j]には、i番目の有権者にとってj番目にランク付けされた好みの候補者のインデックスが格納されていることを思い出してください。

tabulate関数を完成させる

tabulate関数を完成させます。

  • この関数は、即時決選投票のこの段階における各候補者のvotes（得票数）を更新する必要があります。
  • 即時決選投票の各段階において、すべての有権者は、まだ除外されていない自分の最優先候補に実質的に投票することを思い出してください。

コードを書く際は、以下のヒントを考慮してください。

  • voter_countには選挙の有権者数が格納されており、選挙の各有権者について1つの投票用紙をカウントしたいことを思い出してください。
  • 有権者iにとって、第一希望の候補者はpreferences[i][0]、第二希望の候補者はpreferences[i][1]などで表されることを思い出してください。
  • candidate構造体にはeliminatedというフィールドがあり、候補者が選挙から除外されている場合はtrueになることを思い出してください。
  • candidate構造体にはvotesというフィールドがあり、各有権者の好みの候補者に対してこれを更新することになるでしょう。
  • 有権者の除外されていない最初の候補者に票を投じたら、そこで停止し、投票用紙をそれ以上読み進めないようにする必要があることを思い出してください。条件文の中でbreakを使用することで、ループを途中で抜けることができます。

print_winner関数を完成させる

print_winner関数を完成させます。

  • いずれかの候補者が過半数（票の半分より多く）を獲得している場合、その名前を出力し、関数はtrueを返す必要があります。
  • まだ誰も選挙に勝利していない場合、関数はfalseを返す必要があります。

コードを書く際は、以下のヒントを考慮してください。

  • voter_countには選挙の有権者数が格納されていることを思い出してください。それを踏めて、選挙に勝つために必要な票数をどのように表現すればよいでしょうか。

find_min関数を完成させる

find_min関数を完成させます。

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

コードを書く際は、以下のヒントを考慮してください。

  • 候補者をループして、まだ選挙に残っており、かつ得票数が最も少ない候補者を探すとよいでしょう。候補者をループする際、どのような情報を追跡し続ける必要がありますか。

is_tie関数を完成させる

is_tie関数を完成させます。

  • この関数は、選挙で現在誰かが持っている最小得票数である引数minを取ります。
  • 選挙に残っているすべての候補者が同じ得票数を持っている場合、関数はtrueを返す必要があり、そうでなければfalseを返す必要があります。

コードを書く際は、以下のヒントを考慮してください。

  • 引き分け（タイ）は、まだ選挙に残っているすべての候補者が同じ得票数を持っている場合に発生することを思い出してください。また、is_tie関数は、現在候補者が持っている最小の票数である引数minを取ることにも注目してください。minを使用して、選挙が引き分けであるか（あるいは、そうでないか）をどのように判断できるでしょうか。

eliminate関数を完成させる

eliminate関数を完成させます。

  • この関数は、選挙で現在誰かが持っている最小得票数である引数minを取ります。
  • min票持っている候補者（または複数の候補者）を除外する必要があります。

ウォークスルー

テスト方法

コードが以下を処理できるか確認するために、必ずテストを行ってください。

  • 任意の候補者数（最大9人まで）の選挙
  • 名前による候補者への投票
  • 投票用紙に載っていない候補者への無効な投票
  • 勝者が一人の場合の選挙の勝者の出力
  • 残っている全員が同点の場合に、誰も除外しないこと

正確性

check50 cs50/problems/2026/x/runoff

スタイル

style50 runoff.c

提出方法

ターミナルで以下を実行して作業を提出し、表示されるプロンプトにも回答してください。

submit50 cs50/problems/2026/x/runoff