2011 TCO Marathon Match Round2 : QualityPolygons　とかの反省

TopCoder

前回の記事の続き
何とか赤コーダーになれた。学生ぢから全開で時間を大量につぎ込んだだけに今回で決められてよかった。
次のRound 3は上位者が本気を出してくれる数少ない機会なので、自分も最大限誠意を持って取り組みたい。
Onsiteの12時間マラソンは時間が短すぎて個人的に殆んど別ゲーなので、自分にとっては次がFinalだと言っても過言ではない。

QualityPolygonsの反省

  • ForumのStatisticsを見ても分かるように、今回は弱点潰しゲーだった。
  • 意外なことに、smallでも１位複数人というケースはそんなに多くなかった。
  • 公開されている様々なデータを見るに、結局自分の弱点はsmallだったらしい。
    • largeも上にはすごい人がいっぱいだけど。
    • でもlargeがそこそこ強かったのは本当に意外だ。あとはsmallの焼き鈍しがすぐに見えるようになれば…
    • largeで歪な多角形の検出とかはできなくても問題なかったようだ。
  • largeでやった前処理は計算量下げる方法があった。ネックにならなかったので問題にはならなかったけど多分0.5秒くらいの損失があった。
  • 一番重要だったのは、各格子点についてもっとも近い点を取ってくることっぽい？
    • 多分この方法でやればlargeとsmallの場合分けとかしなくても70点くらいとれる。
    • バケット法とか4分木とかだと「一番近い」にならないのであまり点が上がらない。
    • かといってバケットのサイズを小さくすると計算量が減ってくれないし。
  • smallで発見即採用のgreedyがダメだというのは、他の参加者はすぐに気づいていたっぽい。
    • 本当に一目だったらしい。
  • smallで稼ぎまくってる人は焼き鈍しなので、やはりこれは必須スキルらしい。
  • 凸かどうかの判定はO(n)でできたらしい。ちゃんと五芒星とか弾けるのかなあ。
    • 作り方からして実際に五芒星が出るわけではないと思うが…。

Marathon Matchの取り組み方について

  • 自分の考える理想の勝ち方は、一番重要な部分がしっかりしていて後は適当なコーディングで一見楽をしてるように見えるもの。
    • プログラムのあらゆる部分が最適化されてる、というものではない。
    • 今までの自分の取り組み方はまるで正反対になっている。
    • pythonで1submit勝ちしている人とかいたらファンを通り越して信者になると思う。
    • 本当に楽をして勝つのを目指しているのではなく、考えることに力を割くべきだということ。
    • 動かしてみるまで分からない、ということも多いので本当に単なる理想でしかないけれど。
  • 理想の話は置いといて、Marathon Matchは順位表がすごく重要だと思う。
    • 最適化系のコンテストで順位表の公開/非公開は完全な別ゲーという感覚がある。
    • ある特定の条件下でのみ動作するコードを送信して他の参加者の差分を見るとか、そういうのは楽しい。
      • 例えば今回のだと、最大の差分を見ることによってpretest100個のうちlargeとsmallどれくらい偏ってるかとか調べられる。
    • algorithmのレーティングが高い人が上位に集中してたら綺麗な解き方があるんだろうなあ、とか。
  • スコアリングは重要な要素。
    • 得意分野を伸ばすゲーとか、弱点なくすゲーとか、最適解以外無意味ゲーとか。
    • QulityPolygonsみたいなのは、中下位層(偉そうな言い方だ)の傾向も気にしてやらないといけない。
      • largeだとなかなか偶然では負けにくいけど、smallだと終盤戦でその層の人たちがちょっと改良するだけですぐに抜かれてしまうことがある。
      • なのでsmallの弱い自分は順位下がりやすいんだろうと予想できた。
  • Marathon Matchは奇抜なアルゴリズムを競う場所ではない、というのは割と意識してる。
    • 普通のアイデアを丁寧に実装してアドホックに改良していくだけ、というのが初期の参加スタイルだったけど、そこまで酷いことにはならなかった。

自分の短所

  • 公開されているアプローチや参加記を読んで、自分の思考の癖とかの短所が少しは見えてきた。
    • パラメータによって解くロジックを切り替えることが多い。
      • QualityPolygonsやBeautifulCrosswordが良い例。
      • 入力の特性を生かしたアルゴリズムになるのでそんなに悪いことでもないとは思うけど、考えることや実装量が多くなるのが問題。
      • 問題の本質を見えにくくしているような気がしないでもない。
    • 早いうちから最適化をしてしまう。
      • これは明確な悪癖。
      • そしてこれをしてしまう理由も分かっていて、暫定の順位を少しでも上げたいから。見栄というか上位にいないことの不安感というか。
      • これを治療するために序盤はJavaで書くことにした回もあった。理由は自分の場合Javaだと最適化する気が全く起きないから。
    • 最適化の効果を過大評価しがちである。
      • いつも、「最適化をかければ後３点は上がるだろうから…」とか過度の期待をしてしまう。
      • 早いうちから最適化してしまうのと相まって、実際はそこまでの効果を上げられない。
      • しかも高速化して何をするかというと、大抵単なる多スタート法。これじゃ高速化の恩恵をあまり受けられない。
      • 自分が参加した過去のMarathon Matchで毎回C#かJavaが一位を取っているという事実を鑑みるまでもなく、大事なのは方針立てに決まってる。
    • 上位陣はみんな似た方針でやっているんだと思い込みがち。
      • なので、自分も上位に食い込むと今の方針が最適であると思って思考の方向性を狭めてしまう。
    • 早見え型ではない。自分の第一感は信頼できるものではない。
    • パラメータ調整の際の試行回数が少ない。
      • 計算機が貧弱なのも原因の一つではあると思うけど。
      • それ以上に作業の自動化が下手なのが問題なんだと思う。
  • ちなみに長所があるとすれば、モチベーションが続くことだと思う。
    • そしてそのモチベーション維持には、順位表やvisualizerが大きく寄与してると思う。
    • 思考が行き詰まったら大抵visualizerを動かしてみてぼんやりと眺めることにしている。