hotpepsiの練習帳

SRM 536 Div1

00:00

三ヶ月ぶりのdiv1参加

Easy (250) MergersDivOne

問題

• いくつかの会社があり、それぞれの利益が配列で与えられる。
• 会社を合併すると、新会社の利益は、各社の利益の総和÷社数となる。
• 最終的にできる会社の利益の最大値を求める。

方針

• なんか赤字のとこからマージしてくと良さそうなのでまずソートする
• これ最小のとその次のマージするのを繰り返せば、赤字の効果が最も薄まるんじゃ
• 一度に任意の社数をマージできるけど、2で良さそう
• sample通ったのでとりあえずsubmitして検算する
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_536/MergersDivOne.cpp

Medium (500) RollingDiceDivOne

問題

• N個のサイコロがある。
• それぞれのサイコロの面は1からk=dice[i]までの番号が振られていて、出目の確率は等しい。
• 最も出やすい出目の合計値を求める。複数ある場合は最小値。

方針

• 個々の期待値は(1+k)/2
• 足すと1が含まれているサンプルが合わない
• 1のとき場合わけするとサンプルと合うのでとりあえずsubmit
• 何人かresubmitしてるので読み直す
• 自分を撃墜するパターンは見つけたが、実装間に合わず
• 終了後解き直し
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_536/RollingDiceDivOne.cpp

Hard (1000)

openだけしてみた。

結果

ox- 235.23 + 395.84*0 + 50*1 = 285.23 174th rating 1258 -> 1404 (+146)

できすぎな結果。

easyはsubmitしてから落ち着いて考えて、計算手順は合ってそうだが、誤差死するのかどうか確認したりした。一意に定まるので、誤差が出ることはなかった。

setに突っ込んでいる人が落ちていたのだが、理由は同じ値が消えるためだった。よくある不具合だが実行しないとわからなかったので、修行が足りない。

mediumはとりあえずサンプルは合って、div1mediumがそんな簡単なわけはないと思ったがやはりそうだった。しかしコーナーケースはわかったので、最速で1撃墜した。

最後だけ大きいケースの場合が、それまでの最大値+1になるのは、パターンを書いてみて直感的には理解した。最後の出目を加えたパターンは、最大値+1までは場合の数の分布になり、最大値+1のところから先は変化しなくなるから、みたいな感じ。

ちなみに和をaccumulateで求めるとoverflowするというおまけつきだった。