SuperCon2009 今さらだけど参加記
上記の記事でおおよそ話はついちゃうんだけれど、なんかちゃんと説明する必要に迫られたので書く。
参加チーム
チームZATORIKU。SuperCon2009優勝。
予選
面倒なので完全に省略。今年は本選の内容と関係なかったし。
与えられたデータサイズがあまりに小さく、差がつかないであろうところがちょっと不満だった。
問題
詳細はこれを見るといいと思う。
Supercomputing Contest 2009/本選問題 - Supercomputing Programing Contest Official Site
簡単に言うとこんな感じ。
- 三次元空間上に星がいっぱいある
- 星から天体観測できる→ある距離までの星が観測できる。
- これは天球上に射影されたベクトルで表される。向きはわからない。
- どの星から観測されたかなどを当てる
- (どの方向で撮影されたかも当てるんだけど説明の簡単のため無かったことにする)
- いっぱい当てるとウハウハ
「最近のSuperConはNP完全問題ばかりだといったことを言われていたので、今年は気合入れて難しいP問題を考えた」、との話だった。
環境
環境も上記ページに書いてあると思うけど、阪大にあるSX-9を借りて計算をさせてもらった。言語はCで、このスパコンはベクトル重視なので、単純な計算を配列に一気に適用するかんじのプログラムが良いということになる。
一日目
問題の一部だけ発表されてすぐに考えはじめたが、逆効果だった気がする。
このときに考えたのは
- 回転不変量で検索する必要がある
- 写真上で最短の星のペアとか
といった内容。
問題の詳細がわかってから、この最短の星のペアを発見するのに必要なことをずっと考えてウンウン唸ってた。酷いですねー。
あとは色々と環境整備。
コーディングに使ったクライアントはMacだったが、キーボードがHHKのUS配列のMac版とかいう凄いので、無茶苦茶苦労した。
あとVimが6で残念だったけどまあいいや。
二日目
上のようなことをずっと考えていました。このときはまだ動作するコードができてなかった。
この頃に考えていたのは、写真ごとに写っている星の数は一定であるということである。
このことから、上手にやれば、写っている星の数に依存する値を回転不変量として使用してよいことが分かる。
で、家に帰って考えてたら閃いた。風呂場だったと思う。そしてそれを三日目に実装した。
三日目
検索キーとして、「写真上の射影ベクトルの和」を使うことにした。この発想が当たりだった。
もし射影ベクトルが均一に分布していたとすると、これの合計は0になって使い物にならないな、と思っていたけれども、実際計算してみると案外偏っていたので使えた。ベクトルの和は回転不変量として使えるのでいい感じ。ただ、射影ベクトルの和とか意味論的には何の意味もないよねーなので、これは想定解ではないかもしれない。ただ、他の成績のよいチームも多くがこれを使っていたので、結局のところこれが正解だったと言えるだろう。
これをもう少し具体的に言うと
- 写真は前もって星の数の少ないものからソートしておく。
- 写真ごとに射影ベクトルの総和を計算しておく。
- それぞれの星について
- 周りの星を距離でソートして、内側から処理する。このとき射影ベクトルの総和を計算しつつ星を追加する。
- 追加された星の数がある写真のそれと等しい場合、射影ベクトルの総和の長さを比較する。
- それっぽかったらさらに処理をごにょごにょして出力
なお、後に誰かが、以下のような回転不変量を使うのが想定されていた、というような話をしていたのを小耳に挟んだので射影ベクトルの総和はやっぱり想定解じゃないような気がする。
- 写真から適当な射影ベクトルAを選び、他の射影ベクトルxとの距離|Ax|を計算して索引できるようにしておく。
- 星から適当な射影ベクトルBを選び、他の射影ベクトルyとの距離|By|を計算して上と等しいものがあればAとy、Bとxは対応する気がする。
まあ何はともあれ、これで動作するプログラムが作れたのであったが、問題サイズを大きくするにつれ精度と速度の両方で問題が出てきた。
四日目
わりと調子よくなってきた四日目。
速度の問題は、上記において「周りの星を距離でソート」するところであると考えた。星の数Nに対して、これではここの処理全体でN^2logNかかってしまう。
これを改善するために、バケット法を用いた。星の数Nは最大で100万まで行くが、必要な近隣の星M個に限定すれば10000程度以下まで減らせる。これによって処理時間が大幅に削減(単純計算で速度100倍)されたことになる。というか実際功を奏した。
精度の面は、もうこれは何とも言えないので、速度とのトレードオフを意識しながら手動で許容誤差を修正した。
最終的に、そこそこ満足のいくプログラムで出せたが、まさか優勝するとは思っていなかった。
審査
前述の通りこの問題はかなり気合の入った問題で、SuperConの歴史を見てもかなり難しいらしい。そのため、審査方法が変更になり、段階的に絞るかんじになった。詳しいことはまた省略するが、要するに段階が進むにつれて問題が大きくなり、使える資源も多くなる。正答数が高いほうが良く、同数なら解答時間となる。
結果であるが、あまり詳しいことは覚えていないが、とりあえず最初のテストを通過してホッとしたことは覚えている。ここでrand()に運命を託したチームとかが篩いにかけられたんだったと思う。覚えてないけど多分半分くらいが落とされた。
次のテストで4チームが残された。potassioとH5N1とzatorikuが残ったことは覚えているのだが、4位が誰だったかは忘れてしまった。
この時点では、H5N1が1位、zatorikuが2位、potassioが3位だったと思う。
この時点で、potassioが精度・時間ともにかなり成績を落としていて意外であった。僅かであるが確実にH5N1とzatorikuの間には点数差があったが、zatorikuは爆速であった。意外な結果に驚きつつ、飯を食った。
最終テストの結果、なんとH5N1は0点になってしまった。前処理に時間がかかりすぎたらしい。その結果、zatorikuはめでたく一位となった。
なお、バケット法を導入したチームは意外にも自分たちだけったようである。このバケット法が評価され、学会奨励賞ももらった。
景品
昔はPCが貰えてたとかそういう噂もあるが、今となっては金目のものは貰えない。
でも有名企業のグッズとかいろいろ貰えてウハウハだったり、何はともあれ楽しかったから何でもいいや。
感想
まず、potassioとH5N1とは本当に僅差であった。本当に彼らは恐ろしい。potassioは運が悪かったというか、詰めが甘かっただけで、そのままいけば2年連続優勝だったと言えるし、H5N1も同様だ。そして彼らに限らず、計算機が好きな多くの人達と一緒に楽しくプログラミングできたこの4日間は本当に楽しかった。皆ありがとう。
反省点は、今回は僕の独断でやりすぎた感が強かったことである。potassioはなんか皆デキる奴って感じだし、H5N1も役割分担をしているらしく眩しかった。
来年もぜひ出場して、その時は二人にももっと協力してもらい、あわよくば二年連続優勝を達成したい。
来年もし本戦出場できれば、東工大の新しいスパコンを使うことになるだろう。何かびっくりなことが起こらない限りは、東工大のスパコンはスカラー並列なので、今年とは違う感じになりそうで楽しみである。ぜひ出場した。
とにかくネックになるのは予選だ。学校から2チームという制限が辛い。僕としてはもう少し難しい問題のほうが差がついて嬉しいんだけども。
