Hatena::Grouptopcoder

Gus@topcoder

topcoderのid:gusmachineの記録です。普段の日記は揺動散逸日記をどうぞ。
 | 

2010-05-02

! topcoder open qualification round.

5/5に書いています。

oox 488.82 pts 372位.

  • 250 238.94 pts
  • 500 249.88 pts

500の解法が酷いものでした。

500

12:46

  • 500から開く。
  • ロボットの動きをシミュレートして踏んだ升目を数える。ただし動きの列が周期であたえられて非常に長くなる。
  • 基本は一周期で踏む升目の数 x 周期数。ただし同じ場所を踏むところが出てくるので、それを検出してマージすればよい。
    • まず、周期一つこなすごとに固定した幅だけずれる。そのずれをdiff.x/yとおく。
    • 一周期したときの升目を二つ取ってきて、それらの位置関係がdiff整数倍なら、同じところを踏むことを考慮して踏む個数を調整。
  • あれ、diff_x/yが0のときに面倒だな。こうやってこうやって。
  • あれ、はじめの何ループかはこれでは上手く解けないな。ループが少ないときは重ならない、というケースが存在するのか。
    • 10ループまでは展開して解くだけにしておこう。
    • この撃墜例を持っておこう。"ULLDDDRRRU" x 2.
  • なんとかできた。

250

12:46

  • bubble sortの交換回数 = 逆転の個数. 6分で撃破。

1000

12:46

二分探索で、あとでたらめな数が来るからオーバーフローを全て無視するようにする。

途中で意識が飛びかけて、二分探索が v 以下の数字の個数を探すのかv未満の数字の個数なのかわからなくなるほど意識レベルが低下。未完。

challenge

12:46

  • よーし500撃墜しちゃうぞ。
  • あ、あれ...
  • 500は始めループ回して、あとは増加数一定だからその分を実験的に求めてかけ算すれば終わりなのか。無駄に苦労してしまった。ついでに撃墜例はこれでは役に立たない。

感想

12:46

500で謎の混迷.

 |