Hatena::Grouptopcoder

prosho奮闘記 RSSフィード

2012-03-20

SRM538

05:03 | はてなブックマーク - SRM538 - prosho奮闘記

まず結果:Div2 oo- 0/0 93th. 1191→1233 念願のDiv1昇格!!

Div1昇格は嬉しい.やっとスタート地点に立つことができました.

LeftOrRight

  • 全探索が効かないことに気付けるかどうか
  • 何ケースか実験して?を全部LかRに置き換えれば良いことに気付く

LeftOrRight.cpp

EvenRoute

    本番中考えたこと..

  • dfsかな? だけど最悪計算量2^50だから無理
  • メモ化再帰, dp, dfsが頭の中をぐるぐる.なかなかうまくいかない.焦る
  • 40分後, ようやく本解に辿り着く
  • 本解

  • (0,0)からのマンハッタン距離(以下M距離)がdaの点Aとdbの点Bの間のM距離dは

    daとdbの偶奇が一致するとき偶数, 一致しないときは奇数

  • つまり任意の二点間のM距離の偶奇を考える場合, 原点からのM距離の偶奇を考えればよい
  • サンプルからソースコードにある関係を予想し, 証明できたのでsubmit.

EvenRoute.cpp

SkewedPerspective

まだてつかず

TurtleSpy

割と簡単な問題だったけど実装に手間取った.

    方針

  • なるだけbackかforwardに一直線に進んで, 180度回転(できれば)してから先ほどと逆方向(backだったならforward, forwardだったならback)に一直線に進めれば理想
  • 180度回転できなければ180度になるたけ近い可能な角度分回転
  • 180度になるたけ近い可能な角度の求め方がミソ

TurtleSpy.cpp(清書せず)

bmerryさんのデータの受け取り方が鮮やかだった.今後真似したい.