hotpepsiの練習帳

SRM 565

22:00

Div1 Easy (250) MonstersValley

問題

• N匹のモンスターに順番に遭遇する
• それぞれのモンスターは1～2枚の金貨で買収できる
• 遭遇したモンスターの恐ろしさが、買収したモンスターの恐ろしさの合計値を超えている場合、モンスターを買収する必要があり、そうでない場合は買収してもしなくてもよい
• 必要な金貨の枚数の最小値を求める

方針

• あからさまにDPだが、恐ろしさの数値がlong long
• 金貨の枚数は最大100なので余裕で収まる
• 提出
• バグってる...
• 再提出
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_565/MonstersValley.cpp

結果

o-- -1 50.0pt 444th rating 1302 -> 1327 (+25)

1文字写経をミスってチャレンジ失敗。なんとかプラス点は確保した。

今年のSRMは530以外は全て出て、ratingが1093->1327(+234)だった。

今のところ参加したコンテストは全て日記をつけているので自分にしてはかなりマメだと思う。

今年の目標(SRMで一瞬黄色になる＆GCJ R1突破)は達成した。来年は複数回黄色＆GCJ Tシャツを目指す。