1172→1151.
250を解いている途中でPCの調子が悪くなって再起動,悲しみに包まれた.
250
概要
- 1ガロン飲み物が入った瓶が二種類あって,1ターン目は1種類目の1/2,2ターン目は2種類目の1/2,3ターン目は1種類目の1/4,4ターン目は2種類目の1/4,……と飲んでいき最も多く飲んだ人が勝者.最大量飲んだ人が複数の場合は勝者なし.
- 順番不同の誰が何回飲んだかという入力が与えられ,勝利の可能性がある人を辞書順で出力する.
解法
問題文は多少複雑ですが,実際はすごく簡単で以下のように場合分けして終わり.
- 2回以上飲んだ人は全員勝者の可能性がある.なぜなら1/2+1/4+1/8+...+1/2^N < 1なので2回飲んだ人には他全部を飲んでも追いつけない.
- 1回飲んだ人しかいない
- 複数いた場合勝者なし.同率首位になるので
- 一人だけの場合勝者
あとは勝利の可能性がある人をソートして返せばよい.