hotpepsiの練習帳

SRM 520 Div2

14:53

SRMの回。ナイスな問題。

Easy (250) SRMRoomAssignmentPhase

問題

• 部屋割り
• K部屋にレートの高い順に割り当てる
• 同じ部屋で自分よりレートが高い人の人数を答える

方針

• 逆から数えた
• 数えなくてもindexがわかればよい
• ソートしなくてもcount_ifで数えるだけでよかった
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_520/SRMRoomAssignmentPhase.cpp

Medium (500) SRMCodingPhase

問題

• コーディングフェーズ
• 75分以内に解けるとポイント加算
• luckを使うと時間が短縮できる
• 得られる点数の最大値を求める

方針

• 全試行
• DPでできそうだが...
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_520/SRMCodingPhase.cpp

Hard (1000) SRMSystemTestPhase

問題

• ランキングが確定している
• ランキングとsubmitしたかどうかが既知
• スコアボードが何通りあるかどうかを答える

方針

• 最下位からDPでできるはず...
• わからなかったのでkusanoさんのを写経
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_520/SRMSystemTestPhase.cpp

結果

oo- 227.74+198.49=426.23 rating 1174 -> 1169

medium遅し。

hardはめっちゃ時間かかった。