hotpepsiの練習帳

SRM 610

DP | 00:32

Div2 Easy (250) DivideByZero

問題

• 何枚かの紙に数字が書いてある
• 任意の2枚を取り出して、大きいほうの数÷小さいほうの数を計算する
• 商が紙にない数なら追加する
• 最終的に紙が何枚か求める

方針

• setに突っ込む
• 追加されなくなるまでループする
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_610/DivideByZero.cpp

Div2 Medium (550) TheMatrix

問題

• 0か1からなる升目がある
• チェス盤状になっている長方形の面積の最大値を求める

方針

• DP
• 横方向と縦方向それぞれ、一つ前と模様が異なっていたら、網目の長さを+1していく
• 現在位置より前の最大の高さは全て既知
• 現在位置の高さからはじめて、幅を+1、高さをminで求めていく
• 最大の面積が答え
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_610/TheMatrix.cpp

結果

oo- -1 227.78 + 338.56 -25 = 541.34pt 30th/766 rating 1170 -> 1257 (+87)

典型的なDPが普通に解けた。

http://togetter.com/li/634761