Hatena::Grouptopcoder

Div1にとどまりたい記録

 | 

2010-12-29SRM492 Div2

年の瀬に7度目のSRM

250 TimeTravellingCellar

profitとdecayという2つの同じ長さを持った配列が与えられるので,profit[i] - decay[j]の最大値を求めよ.ただしi!=jである.前250をなめてたらえらい時間かかった上に落としてしまった経験があるので慎重にやろうと思っているのですが,これはほんとにやるだけって感じなので早い目にコード書いて提出しました.243.88pt

550 TimeTravellingGardener

  • 地平線上に高さ(height[i])と前の木との間隔(distance[i].サイズはn-1)がまちまちの地平線と垂直で直線とみなせる木がn(<=50)本あって,そのうちの何本でも高さ0までの範囲で任意に縮めることができる.このとき,木のてっぺんを結んで1つの直線にするためには,最小で何本の木を縮めればよいか.
  • ….
  • え,分からない….
  • たしか550は初めてだったような気がするので動転して間違った思考開始.
  • 頭の中で考えてみると直線は必ず高さ最小の木の頂点を通る?(間違っています!!!)
  • 高さ最小の木と他の木との頂点を結んだ直線を考えて,それを下回る高さの木がないとき,直線を越える高さの木の数を調べてその最小をとればいいのかな.(つづけて間違っています!!!)
  • ただし直線と地平線との交点が左端の木と右端の木との間に来ないようにする.(これはまあたぶん)
  • バグ出しながら適当に実装….
  • 提出(217.09pt).

1000 TimeTravellingSalesman

  • この時点であと10分くらいだったのでやる気もなく問題文も読まなかった.
    • 読むだけでも読んでchallengeに備えればよかったと途中で後悔.
  • 550の最大ケースとか作った.

Challenge Phase

  • 読んでる最中のコードが撃墜されてびびったりした.
  • せっかくテストケース作ったのでろくにコードを読まずにchallengeした.
    • TLEで落ちた!!
    • 初めてchallengeに成功したうれしい!!
  • 550をぽこぽこ落としてる人がいて震えながらも,落とされないし僕のコードにchallengeして失敗してるので微妙に安心.

System Test

ギヒー550落ちた….

ox- 1061->1130 293.88pt

Div1には上がれませんでした.来年に持ち越し….

感想

550はまず誤差で死んでいました.直線と木との高さを比較するところでうまくいってなかったようなので修正.さらに,”頭の中で考えてみると直線は必ず高さ最小の木の頂点を通る?”というのは,例えば{{1,1,1},{5,6,8,10}}を考えてみるとこの場合は高さ6,8,10の木の頂点を通って高さ5の木を4に縮めれば答えは1になるので間違ってますね.落ちるべくして落ちた感じ.

時間がなかったので1000はやらなかったけど,1000の方が簡単だったっていう人もいて,戦略を考えることが大事かなあと思いました.

抱負

1月2月は試験があるので忙しいし春に合宿もあるので時間がとれるか心配ですが,年度内にDiv1に上がることを目標に頑張りたいです.

 |