ガジェット通信

見たことのないものを見に行こう

第98回「今週のアルゴリズム:オリンピックの開催地はどうやって決まる?」正解者発表

DATE:
  • ガジェット通信を≫

「今週のアルゴリズム」とは

「今週のアルゴリズム」問題は、毎週火曜日にちょっとした問題を出題し、正解するとニックネームを掲載していくというシリーズ問題です。そして、正解した方全員に「たいへんよくできました」バッジも付与されます。

第98回は「今週のアルゴリズム:オリンピックの開催地はどうやって決まる?」の問題です。

問題文「第98回 オリンピックの開催地はどうやって決まる?」

いよいよリオデジャネイロ・オリンピックまで約50日。カウントダウンが始まります。
オリンピックの開催地が決まるまでには、IOC委員による投票があります。
2016年のリオは4か国の中から3回の投票で決まりました。
2020年の東京は3か国の中から3回の投票でしたが、どうやって決まるのか再確認しましょう。

開催地の決定に使われるのが「繰り返し最下位消去ルール」です。
トップが過半数を超えると、1回の投票で決定します。
トップが過半数を取れない場合、最下位を除外してもう一度投票を行います。
過半数を得るまでこの方法で投票を繰り返します。

ここでは、最下位が複数になった場合は、最下位1つが決まるまで上記の逆の投票を行うことにします。
(つまり、最下位が過半数を超えると1回で決定、過半数が取れない場合、最上位を除外してもう一度投票)
なお、投票を行ったときにすべての候補が同数になることはないものとします。

例えば、2016年のリオの場合は以下のような投票結果でした。
都市1回目2回目3回目リオデジャネイロ264666マドリード282932東京2220-シカゴ18–

2020年の東京の場合は以下のような結果でした。
都市1回目2回目3回目東京42-60イスタンブール264936マドリード2645-

n 個の候補地について、十分多くの人が投票することを考えます。
1つの候補地が決まるまでに必要な投票パターンが何通りあるかを求めてください。

例えば、n = 3の場合、
・1回目で1つが過半数を超えて決定
・1回目で1つが脱落し、2回目で残り2つの決戦投票
・1回目で下位2つが並び、2回目で下位2つの投票、3回目で決選投票
の3パターンがあります。

同様にn = 4の場合は16パターンがあります。
標準入力から n が与えられたとき、パターン数を標準出力に出力してください。
(n は最大で7とします)

【入出力サンプル】
標準入力
3

標準出力
3

正解者

おめでとうございます!正解者のみなさんです。(新着順)

イケナガテツヤ様
あいべくう様
えちごやえちぜん様
haruya様
abc_様
wand様
桜小路こいし様
fukayanegi様
toku-mori様
チクタック様
radian様
さとう菓子様
kyo0924様
Rose Line様
toufu様
はや14様
painfulness様
みかんず様
カニ戯(ry様
strauss様
みけCAT様
tnkayu様
peptide様
todaemon様
touran7様
nodoame2様
miura様
hirokun様
yudedako様
Brln様
Kimics様
wizpig様
なゆたん様
kankichi573様
teck様
noriok様
distancedsilhouette様
ikatakos様
ぶれぼ様
kasugai様
gmk様
antimon2様
ganchan0523様
watchd0g様
VanVan様
さむいも様
366様
Zuishin様
チャリネス様
a992571様
qwerty_rc様
hermanoid様
yoshnary様
Mattsun様
こたつがめ様
おじけん様
SHIMOSAM様
noy様
drhy様
ginneko様
ハハロ様
tochukaso様
ちゅうでん様
wx7890pack様
小野寺 建一様
rotary-o様
airis様
らび様
smz8110様
KKawa1様
ナタデココ様
nekoiscat様
shoek様
neko_the_shadow様
scherzo2様
deni_T様
ーTAKUー様
ニッカ様
nurikabe様
あっき様
L.star様
けーえすけー様
杉にゃん様
lightpurplewisteria様
doreddo様
R修行中様
shout_poor様
おすたー様
angel様
kotakun様
nicocodeiq様
fine_様
ゆん2様
むぎゅう様
たわたわ様
Count0様
PG_SSK様
kantan2015様
chat様
Kilisame様
Azicore様
kenj4様
たんでー様
tnakao様
Yasu.Hara.様
舞葉様
ciel様

カテゴリー : デジタル・IT タグ :
CodeIQ MAGAZINEの記事一覧をみる ▶
  • 誤字を発見した方はこちらからご連絡ください。
  • ガジェット通信編集部への情報提供はこちらから
  • 記事内の筆者見解は明示のない限りガジェット通信を代表するものではありません。

TOP