TopCoder SRM429 DIV1

Rating 1256 => 1489

夜ってのは本当よくない。

そうそう、今日10年上にあたるパ研の先輩をTopCoderで見つけて、話をした。感動した。

さらに追記、気づいたらid:lizanを追い越して校内順位2位になってた！やったー！
負けないようがんばります。

一問目 Subrectangles Of Table

文字の表(矩形)が与えられ、それが含む部分矩形を列挙して、それら全てから文字の出現頻度を調べる。

(x+1)*(w-x)*(y+1)*(h-y)を計算すればいいだけで、単なる実装ゲー。

二問目 Ingredient Proportions

自然数が入る変数の比率が与えられるので、与えられた比率を満たす最小の変数群を求める。

id:lizanが終わった後にDFSとか叫んでて免税店かと思ったら深さ優先探索だった。

三問目 Specific Polyomino Covering

ポリオミノAとポリオミノBを、指定された領域に敷き詰める。このとき敷き詰め方が指定された辞書順において最小のものを探す。

普通の探索でやったら余裕で落とされた。Challenged初体験。

えらいひとのソースを見たり話を聞いたところ、全部Bで敷き詰めてから考えるらしい。