hotpepsiの練習帳

SRM 525 Div2

02:35

Easy (250) RainyRoad

問題

• 道路に水溜りがある
• 迂回してゴールできるかどうかを答える

方針

• 同じカラム(上と下の両方)が埋まっているかどうかだけ調べる
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_525/RainyRoad.cpp

Medium (600) DropCoins

問題

• 升目にコインが乗っている
• 盤全体を上下左右いずれかに動かすことにより、乗っているコインを落とせる
• 残ったコインをK枚にするための最小の手数を答える

方針

• 最初に、上と左右または下と左右を削るものを書いたら通らず。
• 考え直したら、削るのではなく、任意の大きさの長方形で評価すればよいという結論に。
• 効率的なのが思いつかなかったので軽い気持ちで6重ループする全探索。
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_525/DropCoins.cpp

Hard (950) MagicalSquare

問題

• 3x3の升目に文字列を記入する。
• 横方向に連結した文字列をrowStrings、縦方向に連結した文字列をcolumnStringsとして
• それらを満たす文字列の組み合わせが何通りなのかを求める。

方針

• capythmさんのを写経
• 全探索
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_525/MagicalSquare.cpp

結果

oo- 243.14+261.63=504.77 rating 1190 -> 1227

easyは、こんな単純で良いのかとは思ったが、反例が思いつかなかったのでsubmit。通った。

mediumは、いったん下に動かしてから上に行くというパターンがサンプルにあり、それが通らないコードを書いていたため、書き直し。結局50分近くかかった。なのであまり見直しせずsubmit。TLEしなかったため通った。

ようやくdiv1に上がった。easyしか解けそうにないがぼちぼちやっていくつもり。