hotpepsiの練習帳

TCO 2013 Round 1A

01:02

Easy (250) HouseBuilding

問題

• 家を建てるために土地を買った
• 土地はでこぼこで、高さの配列が与えられる
• 全体の高低差を1以下にするためのコストを求める

方針

• 二重ループで全探索
• なぜかはまる
• 場合わけして書く
• 提出
• Passed System Test
• 書き直し
• https://github.com/firewood/topcoder/blob/master/tco_2013/HouseBuilding.cpp

Medium (500) TheFrog

問題

• 蛙が距離Xずつジャンプする
• 穴の開始と終了の座標が与えられる
• 穴を全て飛び越えるための最小のXを求める

方針

• 二分探索かな...複数の候補があるので無理っぽい
• 最小値は必ず最後のRを通る気がする
• 最後のRをN等分してみる
• なんか最後のLを通るケースもありそう
• サンプル通る
• 提出
• Failed System Test
• 書き直し
• 最小の距離で飛び越えようとすると、どれかの端点Rを通ることになる
• それぞれの端点RをN等分した距離で可能かどうか調べる
• https://github.com/firewood/topcoder/blob/master/tco_2013/TheFrog.cpp

結果

ox- 797th/1752 rating 1411 -> 1383 (-28)

mediumが手ごわい問題だった。