読者です 読者をやめる 読者になる 読者になる

Topcoder Open 2015 Marathon Match(Round 1)の参加日記

Topcoder プログラミングコンテスト マラソンマッチ

初マラソンマッチ。目標は上位4割。ちなみにSRMは緑なのでかなり背伸びしている。

  • コンテスト1週間前~前日

 マラソンの知識がほぼゼロなので、Web上の記事をいろいろ漁る。

  1. 全般

    shindannin.hatenadiary.com

    topcoder.g.hatena.ne.jp

    マラソンマッチの取り組み方 | システム工房コルン

    chokudai.hatenablog.com

  2. テクニックなど
    ランダムフォレスト

    shindannin.hatenadiary.com

    焼きなまし法
    shindannin.hatenadiary.com

     データ構造など

    topcoder.g.hatena.ne.jp

    いもす法

    いもす法 - いもす研 (imos laboratory)
    むしろSRMで使えそう。

    ゾブリストハッシュ
    Zobrist hashing - Wikipedia, the free encyclopedia

    k平均法

    k平均法 - Wikipedia

  3. 体験記、過去問解説

    www.youtube.com
    ColunさんのTCO14MR1思考過程。試合中に録画されたもので、超面白かった。

始まってからの作業を減らすため、あらかじめ環境を整えておくことにする。IDEはVisualStudio。C#を使う予定だけど、速度が重要になってきたら途中でC++に移植するかもしれない。ただ、高速化は終盤まで行わず、慣れてるC#で多くのカイゼンサイクルを回すことを重視する。コードはBitbucketに置いて、会社からでもプルできるようにする(もちろん、コンテスト終了までは公開しない)。バージョン管理はMercurial SCMを使うことにした。

https://bitbucket.org/yambe2002/tco-2015-marathon-round-1
プロジェクトのひな形も作っておく。また、いかにも使いそうな機能(乱数、デバグ用ログ、時間管理)や、スケジュール管理、メモファイルも用意しておいた。

また、Visualizerの理解・改造が大事らしいので、Java開発環境も用意しておいた。Javaはほとんど知らないので、以下の記事の通りに構築。時間があれば過去問のVisualizerを改造して遊んでみたいところだったが・・・。

codezine.jp

  •  1日目

問題が発表になったので読む。幾何だった。

  1. 二次平面上に座標点がいくつかと、整数Nが与えられる
  2. この点を頂点として使い、最大N個のポリゴンを作成する
  3. ポリゴンはシンプルでなければならない
  4. 点は必ず、どれかのポリゴンに属さなければならない
  5. 同じ点は2回使えない
  6. ポリゴンは交差してはならない。ポリゴン内に別のポリゴンを含むのはOK
  7. ポリゴンの面積の合計をなるべく小さくするのが今回の問題
  8. スコアは相対評価。テストケースごとに、他の提出者より小さい面積なら1点。イーブンなら0.5点。出力NGのときは0点。⁽この合計を参加者数‐1で割ったものが最終スコア⁾
  9. 座標点の数は20~99、100~499、500~1500の3パターン。確率は同じ
  10. X/Yは0~699
  11. 同じ場所に点は1個だけ
  12. ポリゴンの数(Nのことだと思われる)は2~20で選ばれる
  13. 点は均一、独立かつランダムに選ばれる
  14. Exampleは10ケース、仮FullSubmissionは100ケース
  15. 1テストケースのタイムリミットは10秒

初見の印象:

  1. crossとかdotとか復習しなくては
  2. ポリゴンの中にポリゴンを作るのは明らかに不利なので、必ず避けるべきだろう
  3. 最初に全点を使ったポリゴンを作成してから、
     分割する
     合体する
     同ポリゴンの描画順を変える(凹点と凸点を交換する)
    を繰り返す焼きなましでどうだろうか?
  4. ケースが多い場合は、K-meanなどでクラスタリングして、いくつかのポリゴンに分けてしまってから焼きなましを走らせるとか?

この時点で方針を考えてもしょうがないので、とりあえず解空間を理解するためVisualizerで遊んでみる。…が、マニュアルモードで、いくつかのパターンでスコアが出ない。Visualizerのソースが明らかにおかしいのでForumにポストして返答待ち(似たような指摘している人がすでにいた)。

Visualizerは置いておいて開発環境を整える。今日やったこと:

長丁場なのでこの辺で今日は終了。Bitbucketへのプッシュも忘れずにやっておく。

 

  •  2日目

いきなり風邪をひいたので、今日はあまり根を詰めない。

前言撤回を繰り返すが、少なくとも中盤まではC#(+WPF)でコーディングすることにした。理由はビジュアライズしながらデバグしやすいから。

いま考えている方針は次の通り。

  1. 点をN個のグループに分ける。K-meanあたりでクラスタリングできればいいけど、数が多いときは時間がかかりそうなので均等分割でよいと思う
  2. 各グループごと、すべての点を使ってポリゴンを作成する。なるべく面積を小さく。この人の実装が参考になりそうだ

    github.com

  3. 時間の限り、頂点を変える・ポリゴンを合体する・ポリゴンを分割する、の作業を繰り返す
  4. もっとも面積の小さかったものを回答する

予想だが、この問題は大量の局所最適があり、そしてその局所最適の間の山はあまり大きくないのではないだろうか。その仮定のもと、1、2ですばやく(それっぽい)局所解にたどり着いて、そのあと3をとにかく回す作戦にしている。

2の実装に取り掛かり、凸多角形は作れるようになった。明日には、凹多角形を作れるようにしたい。

 f:id:yambe2002:20150422141600p:plain

 

  •  3日目 ※いちど書きおわったあと日記が消えた・・・

まだバグってるけど、それっぽい回答をだすようになってきた。

K-meanでクラスタリングしたあと、グループごと凸多角形を作成→辺を適当に凹ましていくやり方。

f:id:yambe2002:20150423014322p:plain

(たまに内部に点がのこるバグあり)

現時点での問題:

  • 特に点が少ないと、K-meansはあまり意味がない。また、ちゃんと実装しようとすると、意外と1グループ3頂点以上を保持したまま計算するのが重い
  • 頂点数が多いと凹ます処理がかなり遅い。最悪パターン(750頂点)だと数分で完了しなかった。500頂点だと10秒くらい

もしかしたらトップダウンではなく、ボトムアップのほうがよかったか?

とりあえず明日はバグの修正と、凹ます処理のロジック見直しを行う。明後日くらいには、最初のSubmitをしたい。

 

・4日目

ひととおり、当初の構想に近いものができた。500頂点以上あると10秒以内に終わらない(指数的に処理が増える)ので、もっと小さな単位に分割して、できたポリゴンどおしをくっつける処理が必要になりそうだ。

f:id:yambe2002:20150424132710p:plain

(1500頂点、N=20の実行例)

それに頂点数が少ないと微妙な答えになりやすい(最初のK-meanに失敗してるので)。集合をランダムに選んで、とにかく数をこなすようにするつもり。

 

  • 5日目

テスタとつないで動かしてみた。0点になるケースがある。

f:id:yambe2002:20150425153849p:plain

f:id:yambe2002:20150425153940p:plain

よく見ると、テスタのコードとIntersectの条件が異なっていた。とりあえず、JavaのコードをC#にそのまま書き換えてみる。OK。

このあたりでテスト提出してみよう。…ローカルでは問題ないのに、サーバー上だと半分くらいタイムアウトした。データ変換に大きなオーバーヘッドがあるのかもしれない。要調査。

なお、試しにSubmitしたら81位/100人だった。半分0点の割には悪くないね。

 

  •  6日目

今日は休養と反省会。

これまで、なんとなく理解した他人のコード流用と組み直しばかりだった。なのであまり楽しくないし、身についているものも小さい

初めに単純なプロトタイプを作り、点数を測定したあと、毎日少しずつアイデアをいれて改善していくやり方に変える。ほぼ作り直し、かつ残り日数も少ないため最終的な順位は下がるだろうが、このほうが悔いは残らないだろう。

土曜日なので、ビールを飲んで早めに寝た。

 

  • 7日目

というわけで、大幅に書き換え。ほぼ有効回答を返すだけの単純なコードを提出してみたところ、82位/115人。目標の上位4割まで上げるには、勝率をほぼ倍にする必要がある。

ローカルにバッチテスト環境がまだ無かったので、ここでやっと構築した。100ケースのスコアをExcelに記録しておく。

 

  •  8日目

最初に頂点を分割し、そのあと各グループごと適当なポリゴンを作り、面積が減る手をランダムに繰り返す貪欲法のコードがほぼ完成した。なお分割はK-meansのクラスタリングをそのまま使っている。

f:id:yambe2002:20150428141802p:plain

これで75位/123人につけた。やっと土俵に上がったような気持ちだ。目標まであと30位くらい。

 

  • 8日目

クラスタリングを改善しようとがんばったが、まだ完成していない。

また昨日のコードを修正し、時間いっぱいループを回すように変更・・・しかし、ループ回数が増えているのにスコアが減ってしまっている。貪欲のところのバグが疑われるので明日調査する。

内部の更新状況のログを出力し、それをビジュアライズする仕組みが必要と思われる。(これも、もっと序盤で作成しておくべきだった。)

 

  • 9日目

内部状況のログ出力と、そのビジュアライザが完了。それにそってデバグしたら2つほど不具合を見つける。貪欲がうまく動くようになった。

ビジュアライズしたら作業がかななり捗るようになった。もっと早く作っておくべきだった

この時点で51位/138人。目標の上位4割に入れた。

明日はクラスタリングを見直すことにする。あと、頂点数が少ないと一瞬で部分解に収束してしまっているので、場合によっては焼きなまし化してもよいかもしれない。

 

  • 10日目

クラスタリングを改善。ローカルでちょっとだけ得点があがったのでSubmitしてみる。

f:id:yambe2002:20150501114152p:plain

私より数分あとにSubmitしたchokudaiさんのテスト消化がすごい早く、一瞬で追い抜いて行った。10秒使っているようには見えないのだが、時間いっぱい解を探すような方法ではないということか・・・?それとも、単にC#とC++の起動時間の差だろうか。とにかく46位/142人まで上がった。

さらに、少ないケースでかなり時間があまるので、初期値を変えて何度かトライする処理を投入。これで40位/142人。最終日までここをキープしたい。

残り使えるのは3日。頂点数の多いケースで時間が足りていない(貪欲が完了していない)ので、そろそろ高速化にとりかかるべきか?ローカルで30秒設定でテストバッチを流してみたところ、3割くらいのケースで少し点数が伸びている・・・が、この程度であと3日順位をキープできるかは微妙な気がして悩む。

なお、このときにまれに起こる不具合を発見した。明日は一番にこれを修正する。

 

  •  11日目

ふと思いついた方法をざっと10分くらいで実装してみるも、処理が重すぎで結果が悪化するので破棄する。

昨日のバグを修正したところ、ローカルで少し点数が上がったのでSubmitしておいた。ちなみにこの修正は結構やっかいで、これだけで今日の分が終わってしまった。

順位は43位/149人。みんな追い上げをしているのだろう。

明日は、ビジュアライズを眺めて気が付いた修正案があるので、それを実装する。うまく行けば、大きいケースでの点数が上がるはず。

 

  •  12日目

昨日思いついた案を実装してみるも効果はほぼ無かった。速度が低下するデメリットのほうが大きそうだ。

定数変更、および初期配置のパターン追加で小さな改善が見られたのでSubmit。点数は少し伸びるが順位は変わらず。

いまさらだが、定数の組み合わせを試すのに手間がかかる。バッチを作っておけばよかった・・・。

高速化で点が伸びることがわかっているので、明日はそれをトライして、今回のマラソンマッチは終了になりそう。

 

  • 13日目

最終日。今日は高速化に注力した。といっても、不具合を出したら元も子もないので、Linqを書き換えるとか、ループを見直すなどの軽いもの。

スコアは少し上がったが、周りの追い上げもあり順位はほぼ変動せず46位/169人。このままなら上位4割には何とか入れるか?

f:id:yambe2002:20150504150346p:plain

 

  •  コンテスト終了

53位/171人で終了。ぎりぎり目標達成。

f:id:yambe2002:20150505063712p:plain

次のマラソンマッチ(参加できればRound 2)では、上位2割を目指して頑張ることにする。以下、反省点と気づいたこと。

  1. 知識不足で序盤かなり迷走したのが痛い(幾何の問題は初めて)
  2. さらに、知識不足にも関わらず、他人のコードを流用して組み始めてしまったのは最悪だった。先に勉強するしか手はなかったはず
  3. 問題把握が甘い。まずは組む前に、手元でしっかり考えたほうが良い。テストケースをプリントアウトして、鉛筆と定規でやってみるなど
  4. ビジュアライズとテスト自動化はどうせやるのだから、さっさと構築する
  5. できれば定数の設定を変えて試すバッチも作りたい
  6. 何か新しい案を思いついても、バグがあったら先にそちらを修正するべき
  7. 慣れているC#でまったく問題なし。ボトルネックはそれ以前にある
  8. ビジュアライザはもっと改造してもよかった

特に1・2・3は次回の最重点項目。

 

 

7位のtomerunさんのTweetが勉強になったので残しておく。

まずtomerunさんの出力がこれ(Tweetより)。スカスカでびっくりする。

私のはこれ…。

f:id:yambe2002:20150505070640p:plainf:id:yambe2002:20150505070701p:plain

あまりの違いにプログラミングを辞めたくなるが、気を取り直して頑張ることにする。

ご本人のTweetによると、クラスタリングしたあとの焼きなましらしい。状態遷移は頂点の移動。

レベルの違いはともかく、アイデア自体は似ている。もっとも異なる点は、私のは焼きなましを棄却して貪欲のみにしたところと、遷移方法が重くて非効率なところだろう。

 

私の遷移のやり方:

  • ランダムに凹頂点と辺を選ぶ
  • 凹頂点をこの辺に移動できて、かつ面積が減るならやる

ダメな点は、

  • ランダムなのでヒット率が低い
  • 面積が減るときしか遷移しないので山を登って終わり

 

後日、レーティングがついて夢の青コーダーになれた。マラソンだけでも黄色を目指そう。