唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

TopCoder Open 2012 Algorithm Round 1A

1172→1151.
250を解いている途中でPCの調子が悪くなって再起動,悲しみに包まれた.

250

概要
  1. 1ガロン飲み物が入った瓶が二種類あって,1ターン目は1種類目の1/2,2ターン目は2種類目の1/2,3ターン目は1種類目の1/4,4ターン目は2種類目の1/4,……と飲んでいき最も多く飲んだ人が勝者.最大量飲んだ人が複数の場合は勝者なし.
  2. 順番不同の誰が何回飲んだかという入力が与えられ,勝利の可能性がある人を辞書順で出力する.
解法

問題文は多少複雑ですが,実際はすごく簡単で以下のように場合分けして終わり.

  1. 2回以上飲んだ人は全員勝者の可能性がある.なぜなら1/2+1/4+1/8+...+1/2^N < 1なので2回飲んだ人には他全部を飲んでも追いつけない.
  2. 1回飲んだ人しかいない
    1. 複数いた場合勝者なし.同率首位になるので
    2. 一人だけの場合勝者

あとは勝利の可能性がある人をソートして返せばよい.

-->