Topcoder Open 2015 Marathon Match(Round 1)の参加日記
初マラソンマッチ。目標は上位４割。ちなみにSRMは緑なのでかなり背伸びしている。
- コンテスト１週間前～前日
マラソンの知識がほぼゼロなので、Web上の記事をいろいろ漁る。
- 全般
- テクニックなど
ランダムフォレスト
焼きなまし法
shindannin.hatenadiary.comデータ構造など
いもす法
いもす法 - いもす研 (imos laboratory)
むしろSRMで使えそう。
ゾブリストハッシュ
Zobrist hashing - Wikipedia, the free encyclopedia
k平均法 - 体験記、過去問解説
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を改造して遊んでみたいところだったが・・・。
- １日目
問題が発表になったので読む。幾何だった。
- 二次平面上に座標点がいくつかと、整数Nが与えられる
- この点を頂点として使い、最大N個のポリゴンを作成する
- ポリゴンはシンプルでなければならない
- 点は必ず、どれかのポリゴンに属さなければならない
- 同じ点は２回使えない
- ポリゴンは交差してはならない。ポリゴン内に別のポリゴンを含むのはOK
- ポリゴンの面積の合計をなるべく小さくするのが今回の問題
- スコアは相対評価。テストケースごとに、他の提出者より小さい面積なら1点。イーブンなら0.5点。出力NGのときは0点。⁽この合計を参加者数‐1で割ったものが最終スコア⁾
- 座標点の数は20～99、100～499、500～1500の３パターン。確率は同じ
- X/Yは0～699
- 同じ場所に点は1個だけ
- ポリゴンの数(Nのことだと思われる)は2～20で選ばれる
- 点は均一、独立かつランダムに選ばれる
- Exampleは10ケース、仮FullSubmissionは100ケース
- 1テストケースのタイムリミットは10秒
初見の印象：
- crossとかdotとか復習しなくては
- ポリゴンの中にポリゴンを作るのは明らかに不利なので、必ず避けるべきだろう
- 最初に全点を使ったポリゴンを作成してから、
分割する
合体する
同ポリゴンの描画順を変える（凹点と凸点を交換する）
を繰り返す焼きなましでどうだろうか？ - ケースが多い場合は、K-meanなどでクラスタリングして、いくつかのポリゴンに分けてしまってから焼きなましを走らせるとか？
この時点で方針を考えてもしょうがないので、とりあえず解空間を理解するためVisualizerで遊んでみる。…が、マニュアルモードで、いくつかのパターンでスコアが出ない。Visualizerのソースが明らかにおかしいのでForumにポストして返答待ち(似たような指摘している人がすでにいた)。
Visualizerは置いておいて開発環境を整える。今日やったこと：
- 速度勝負になるかもしれないので、方針を変えてC++で書く。8年前は使ってた言語なので大丈夫のはず
- IDEは使わず、SublimeText+gcc
- Komakiさんのブログを参考に、時間測定関数を作成。さらにサーバーの速度を測定(サーバーよりローカルのほうが遅い…)
- ベクトル演算の基礎を復習
長丁場なのでこの辺で今日は終了。Bitbucketへのプッシュも忘れずにやっておく。
- 2日目
いきなり風邪をひいたので、今日はあまり根を詰めない。
前言撤回を繰り返すが、少なくとも中盤まではC#(+WPF)でコーディングすることにした。理由はビジュアライズしながらデバグしやすいから。
いま考えている方針は次の通り。
- 点をN個のグループに分ける。K-meanあたりでクラスタリングできればいいけど、数が多いときは時間がかかりそうなので均等分割でよいと思う
- 各グループごと、すべての点を使ってポリゴンを作成する。なるべく面積を小さく。この人の実装が参考になりそうだ
- 時間の限り、頂点を変える・ポリゴンを合体する・ポリゴンを分割する、の作業を繰り返す
- もっとも面積の小さかったものを回答する
予想だが、この問題は大量の局所最適があり、そしてその局所最適の間の山はあまり大きくないのではないだろうか。その仮定のもと、1、2ですばやく(それっぽい)局所解にたどり着いて、そのあと3をとにかく回す作戦にしている。
2の実装に取り掛かり、凸多角形は作れるようになった。明日には、凹多角形を作れるようにしたい。
- 3日目 ※いちど書きおわったあと日記が消えた・・・
まだバグってるけど、それっぽい回答をだすようになってきた。
K-meanでクラスタリングしたあと、グループごと凸多角形を作成→辺を適当に凹ましていくやり方。
(たまに内部に点がのこるバグあり)
現時点での問題：
- 特に点が少ないと、K-meansはあまり意味がない。また、ちゃんと実装しようとすると、意外と1グループ3頂点以上を保持したまま計算するのが重い
- 頂点数が多いと凹ます処理がかなり遅い。最悪パターン(750頂点)だと数分で完了しなかった。500頂点だと10秒くらい
もしかしたらトップダウンではなく、ボトムアップのほうがよかったか？
とりあえず明日はバグの修正と、凹ます処理のロジック見直しを行う。明後日くらいには、最初のSubmitをしたい。
・4日目
ひととおり、当初の構想に近いものができた。500頂点以上あると10秒以内に終わらない(指数的に処理が増える)ので、もっと小さな単位に分割して、できたポリゴンどおしをくっつける処理が必要になりそうだ。
(1500頂点、N=20の実行例)
それに頂点数が少ないと微妙な答えになりやすい(最初のK-meanに失敗してるので)。集合をランダムに選んで、とにかく数をこなすようにするつもり。
- 5日目
テスタとつないで動かしてみた。0点になるケースがある。
よく見ると、テスタのコードとIntersectの条件が異なっていた。とりあえず、JavaのコードをC#にそのまま書き換えてみる。OK。
このあたりでテスト提出してみよう。…ローカルでは問題ないのに、サーバー上だと半分くらいタイムアウトした。データ変換に大きなオーバーヘッドがあるのかもしれない。要調査。
なお、試しにSubmitしたら81位/100人だった。半分0点の割には悪くないね。
- 6日目
今日は休養と反省会。
これまで、なんとなく理解した他人のコード流用と組み直しばかりだった。なのであまり楽しくないし、身についているものも小さい。
初めに単純なプロトタイプを作り、点数を測定したあと、毎日少しずつアイデアをいれて改善していくやり方に変える。ほぼ作り直し、かつ残り日数も少ないため最終的な順位は下がるだろうが、このほうが悔いは残らないだろう。
土曜日なので、ビールを飲んで早めに寝た。
- 7日目
というわけで、大幅に書き換え。ほぼ有効回答を返すだけの単純なコードを提出してみたところ、82位/115人。目標の上位4割まで上げるには、勝率をほぼ倍にする必要がある。
ローカルにバッチテスト環境がまだ無かったので、ここでやっと構築した。100ケースのスコアをExcelに記録しておく。
- 8日目
最初に頂点を分割し、そのあと各グループごと適当なポリゴンを作り、面積が減る手をランダムに繰り返す貪欲法のコードがほぼ完成した。なお分割はK-meansのクラスタリングをそのまま使っている。
これで75位/123人につけた。やっと土俵に上がったような気持ちだ。目標まであと30位くらい。
- 8日目
クラスタリングを改善しようとがんばったが、まだ完成していない。
また昨日のコードを修正し、時間いっぱいループを回すように変更・・・しかし、ループ回数が増えているのにスコアが減ってしまっている。貪欲のところのバグが疑われるので明日調査する。
内部の更新状況のログを出力し、それをビジュアライズする仕組みが必要と思われる。（これも、もっと序盤で作成しておくべきだった。）
- 9日目
内部状況のログ出力と、そのビジュアライザが完了。それにそってデバグしたら2つほど不具合を見つける。貪欲がうまく動くようになった。
ビジュアライズしたら作業がかななり捗るようになった。もっと早く作っておくべきだった。
この時点で51位/138人。目標の上位4割に入れた。
明日はクラスタリングを見直すことにする。あと、頂点数が少ないと一瞬で部分解に収束してしまっているので、場合によっては焼きなまし化してもよいかもしれない。
- 10日目
クラスタリングを改善。ローカルでちょっとだけ得点があがったのでSubmitしてみる。
私より数分あとに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割には何とか入れるか？
- コンテスト終了
53位/171人で終了。ぎりぎり目標達成。
次のマラソンマッチ（参加できればRound 2)では、上位2割を目指して頑張ることにする。以下、反省点と気づいたこと。
- 知識不足で序盤かなり迷走したのが痛い（幾何の問題は初めて）
- さらに、知識不足にも関わらず、他人のコードを流用して組み始めてしまったのは最悪だった。先に勉強するしか手はなかったはず
- 問題把握が甘い。まずは組む前に、手元でしっかり考えたほうが良い。テストケースをプリントアウトして、鉛筆と定規でやってみるなど
- ビジュアライズとテスト自動化はどうせやるのだから、さっさと構築する
- できれば定数の設定を変えて試すバッチも作りたい
- 何か新しい案を思いついても、バグがあったら先にそちらを修正するべき
- 慣れているC#でまったく問題なし。ボトルネックはそれ以前にある
- ビジュアライザはもっと改造してもよかった
特に1・2・3は次回の最重点項目。
7位のtomerunさんのTweetが勉強になったので残しておく。
まずtomerunさんの出力がこれ（Tweetより）。スカスカでびっくりする。
seed2 pic.twitter.com/JHZsA6f884
— tomerun (@tomerun) May 4, 2015
seed5 pic.twitter.com/lAEd6DBb97
— tomerun (@tomerun) May 4, 2015
私のはこれ…。
あまりの違いにプログラミングを辞めたくなるが、気を取り直して頑張ることにする。
ご本人のTweetによると、クラスタリングしたあとの焼きなましらしい。状態遷移は頂点の移動。
方針：適当に初期解を作って焼きなます。遷移は 、p1-p2-p3と点が並んでるところで切って、p1-p3をつないでp2をどこか他のところにくっつける
— tomerun (@tomerun) May 4, 2015
点が多い場合は収束間に合わないので、初期解をk-means的にボロノイ領域に切って、各多角形を独立に考える。別の多角形に点を移動するのはあきらめる（かなり強い制約なので、多分このせいで点が多いケースは弱い）
— tomerun (@tomerun) May 4, 2015
p1-p2-p3を切ってp1-p3をつなぐとき、p1-p3が他の辺と交差してないかの判定が必要で、これは「他の点を内部に含まない三角形」を前もって全列挙しておけばO(1)でできる。三角形の列挙はナイーブにやったらO(点の数^4)だけどちょっと工夫してO(点の数^3)で
— tomerun (@tomerun) May 4, 2015
レベルの違いはともかく、アイデア自体は似ている。もっとも異なる点は、私のは焼きなましを棄却して貪欲のみにしたところと、遷移方法が重くて非効率なところだろう。
私の遷移のやり方：
- ランダムに凹頂点と辺を選ぶ
- 凹頂点をこの辺に移動できて、かつ面積が減るならやる
ダメな点は、
- ランダムなのでヒット率が低い
- 面積が減るときしか遷移しないので山を登って終わり
後日、レーティングがついて夢の青コーダーになれた。マラソンだけでも黄色を目指そう。
