SuperCon2008 2 - Yet Another Ranha

http://www.gsic.titech.ac.jp/supercon/supercon2008/final/index.html
公式で結果が出ました。
優勝したpotassio、準優勝したfungaa、そして3位だったmaruchan おめでとう御座います。
入賞を逃した皆さんも、来年またこの舞台に戻って来て更なる進化を見せつけてください！

今回の本選問題は上記のページを見ると分かるのですが、与えられた点を頂点として全て持つ面積最小の単純多角形(simple polygon)を求めよ、という問題でした。

問題自体に関しては補足する事があまり無いぐらいにシンプルな問題です。

予選が計算幾何の問題でしたので、予選で身につけた知識を上手く使って本選の問題を解かれたのでは無いかと思います。

目に見えるタイプの問題は矢張り、実際に可視化するなり自分で手で点を結んで多角形を作るなどして問題の核心(単純多角形の性質、単純多角形における面積の扱い、heuristic)を掴む事が大事です。
そして次に重要なのは、短い期間で自分の考えをコードに上手く落とし込む事が出来るかどうかという事です。

後は湧き出て来るアイディアをどれだけ沢山実装して解析する事が出来るか、という所もあったと思います。
もっとも最初に選んだ方法が上手く動けば後はそれをもっと上手く動かすという事でもあるのですが。

感想としては、やっぱり高校生若いなーという事。
最近疲れ気味だったので、見てて色々とエネルギーを貰いました。たっぷり持ち帰りましたのでw

後は模擬焼き鈍し法(simulated annealing)とかどこでそれ見つけて来たんだよwなんていうそこいらの大学生でも知らない事をちゃんと自分達で調べて来ていて驚きました。
最近の高校生は普通にシュプリンガーとかも読むのかな？将来が楽しみだ。
まぁ情報オリンピック周りでNP吹き込まれて適切な本を紹介してもらったりしている気がするけど。
興味がある高校生には色んな本なり問題を紹介してあげる機会が在れば良かったのですが、今回はちょっと無かったですw

ただやっぱりあの時間でNNとかGAで来たチームは無かったなーという事。実際正しい判断だけど突撃しているチームがあったらそれはそれで面白かったかもしれない。

私がやったプログラムの流れ。
1日目:わーなんか予選の流れだから、これCで補助関数書いて来ている高校生に勝てないんじゃないかと思ったらサンプルプログラムがあったので、そこから必要な部分を2つ抜き出して、ラップした奴をchokudaiに渡して私も書き始める。
初日は8:00になるまでに内部三角形をランダムで選んで行って初期多角形を生成するのを書いたんだけど、この時点でEcrossに変な点があったのに気付かなかったので、その後chokudai宅でここんとこやっぱおかしいじゃねーかwwwという話をしていた。
取りあえず2:00ぐらいにサンプルのソースコード全部読んで色々把握してから寝た。

2日目:朝持っていて動かしたら、入力最大点75点のやつでも初期解がすぐでてそのままひたすらランダムで動かす奴を走らせてたらある程度動いていて、確かこの時点でchokudaiには勝っていた様な。だが、午後になってから普通にchokudaiが書き上げたのでそれに負けてしまっていたとか。取りあえず方針は聞いたけど同じ方向に進むのももったいないので私は辺の入れ替えを行う方向で実装した。
辺の入れ替えは、TSPを解く時に出て来る2-opt(2-exchange),3-opt(3-exchange)とかほとんどそのまんまで。
私もannealingをこの時から書き始めていて、局所探索を2-exchangeで、解空間脱出を3-exchangeでやっていたが今ひとつchokudaiに勝てないので困った。世界3位は伊達じゃない。この後はchokudai家でバグを取りながらニコニコして寝た。

3日目:正直な所あんまやる事が残っていなかったし、どうせだからとchokudaiの方のパラメータを弄る事にした。で確か6時頃から急いでMPI化を私がやってなんとか帰るまでにTSUBAMEで動く様にしたあとは中学の頃の友人宅に向かった。

4日目:この日は流石に皆さんのチュートにあたってコード書くのは自粛していました。本番の問題を我々のプログラムに対してTSUBAME上で動かしたら一瞬で最適解が出ていてワロタのは秘密☆
後、審査の裏方の大変さが分かりました。しかしながら、今回の新たな試みが上手く行ったので私としては大満足です。

とかそんな感じ。スタートアップは良かったけど、2-exchangeと3-exchangeをもうちょっと上手く適用させられたらとかそんなん。

まとめ

まだ高1,2の皆さんは来年もありますので、その時までにもっともっと楽しんでプログラミングして成長して、また参加してください！
楽しみにしています。

現在高3の人はHaskellを使う様にしてください。楽しみにしています。

今回初めてNP問題(今回のminimum area simple polygonは確かNP-hardです)が気になった人は、過去のSuperConの問題を見てみると面白いと思えるものと出会えるかもしれません。
時間がある人は取り組んでみてください。

それとは別に、今この分野でどんな研究が行われているのか気になる、他にどんな問題や手法があるんだろうと思った人はちょっと専門的ですが、表紙が黄色いシュプリンガー社の計算困難問題の本や、組合せ最適化の本をぱらぱらと見てみると良いと思います。

ビバ　プログラミング！！！！