hotpepsiの練習帳

SRM 504.5 Div2

15:06

Easy (250) TheJackpotDivTwo

問題

• 整数の配列と、jackpot jが与えられる
• 一番低い値のところにjを1ずつ分配する

考察

• どのindexまでに分配するかを求める
• 端数の処理

実装

• ソートする
• 最大のindexからはじめる
• index iまでの合計とjを合計する
• 合計の平均値averageと、[i]を比較して、averageが[i]以上なら分配対象
• 0からiまで配る
• 大きいindexから、端数を配りなおす
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_504/TheJackpotDivTwo.cpp

Medium (500) TheNumbersWithLuckyLastDigit

問題

• 下一桁が4か7ならアホになります

考察

• 規則性が見出せなかったので、手作業で表を作る
• 十分大きな数に対してはループしている

実装

• 手作業で99まで表を作っておいた
• アホの数に対してはmap<int,int>に突っ込んでおく
• 見つからなかったら-1を返す
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_504/TheJackpotDivTwo.cpp

Hard (1000) TheTicketsDivTwo

未着手 → 解き直し

問題

• n人を一列に並ばせて、その中から一人だけ選ぶ。
• 一人しかいなければ選んで終了。
• サイコロをふり、4が出たら先頭の一人を選んで終了。
• 奇数が出たら、先頭の一人を末尾に移動する。
• 偶数(2か6)が出たら、先頭の一人を取り除く。
• k回の試行で誰も選ばれなければ、先頭の一人を選んで終了。
• m番目の人が選ばれる確率を求める。

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_504/TheTicketsDivTwo.cpp

感想

xo- 147.04*0+239.15 991 -> 964

番号は、504がノーコンだったため、やり直しという意味っぽい。

500しかsystem testが通らなかったためrateが964に落ちてしまった。

しかしまずはちゃんと解けるかどうかが重要。