hotpepsiの練習帳

SRM 602

DP | 21:12

Div1 Easy (250) TypoCoderDiv1

問題

• LowerはTypoCoderに参加している
• レーティング2200未満が水色、2200以上が茶色である
• 一回の増減が配列Dで与えられる
• 増えるか減るかのどちらかを選べる
• 0未満にはならない
• 2回連続で茶色になりたくない
• レーティングの変化回数の最大値を求める

方針

• Dの値が大きいのでレーティングを配列で持てなさそう
• 2200以上になるときは、その次は2200未満になる必要がある
• rate+D[i]-D[i-1]が2200未満のとき更新というDPを書く
• 最後だけはその次がないので、2200以上のみ考慮する
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_602/TypoCoderDiv1.cpp

結果

o-- 101.85pt 530/789 rating 1298 -> 1301 (+3)

DP力が上がっている気がするが、一年間の実績では1327 -> 1301で進歩してなかった。

http://togetter.com/li/608415