SuperCon2015参加記
チームWestDivとして、SuperCon2015本選へ行きました。
関西勢です。
同じ久留米高専からもう1チーム(stairgr)出てます。
チームWestDiv
らてくん(2年) @LatteMalta
K君(仮名)(1年)
僕(2年)
チームstairgr
幸猫先輩(3年) @Koubyou_sachi
KO(2年) @sujinbemani_79c
てらくん(1年) @555Tera
ラテ君とテラ君は別人です。
0日目(移動日)
集合日に日付が変わった頃、ラテ君は星野村で元気に遊んでいました。
めちゃくちゃ星野村にいるけど明日出発？？＞＜
— らて (@LatteMalta) 2015, 8月 15
やばい出発日勘違いしてた
— らて (@LatteMalta) 2015, 8月 15
— らて (@LatteMalta) 2015, 8月 15
車で送ってもらったみたいです。
移動
新幹線でプログラミングしたら酔いました。
今回は切符落とさなかったです。
書店へ
しっかり15000円弱溶けました。
ここで大阪に来た最重要の目的を達成。
成果物 pic.twitter.com/mHTx5OzJIV
— 基礎reew言語学入門 (@wing3196) 2015, 8月 16
寝る
寝ました。
1日目
早起きしました。
問題概要
初めて聞く単語ばかりで僕もよく分かりませんが、まず簡単に問題を説明しておくと、
・化学振動のモデルの1つであるCCA(循環的セルオートマトン)というものがある
・今回のSuperConでは特定のルールに従ったCCAを使用
・CCAの初期盤面n*n(盤面はセルに分割された離散空間)と、CCAが進んでいったある時点でCCAの一部を撮った写真が与えられる
・ただし、写真は解像度が落ちている(複数のセルの情報をまとめている)
・CCAは1ステップ毎に進む
・そのようなとき、撮られた写真がいつ、どこで撮られたのか判定せよ
という感じでした。
CCAはざっくり言ってしまえば、一定のルールに従って各セルの状態が変化していくというものです。
絶対に作成しなければいけないプログラムは大きく2つに分けられます。
・CCAのシミュレート
・パターンマッチング(写真と盤面の一致部分を探す)
スパコン
今回の阪大のスパコン(SX-ACE)では、並列化以外に、「ベクトル計算」という配列に対するfor文を高速に行う仕組みがありました。
並列化もベクトル化も、それ自体はコンパイラが自動でやってくれます。
ただ、並列化やベクトル化ができるようにコードを書かなければいけません。
実装
初日は、割と素直に累積和を使ったCCAを実装しました。
(このときはまだ累積和が早いことを疑いもしなかった...)
パターンマッチングも、愚直なコードを書きました。
考察
ラテ君と話し合って、パターンマッチングのほうが時間がかかりそうだという結論が出ました。
1つの盤面を判定するのに、最悪O(n^4)だからです。
CCAのアルゴリズム自体はこれ以上改善が望めなさそうなので、頭の良いパターンマッチングを実装しようという方針を立てました。
2日目
印刷して持ち込んだ紙を写経したところ、写経ミスによるバグが出て4時間くらい飛んでいきました。
この日は前日実装したCCAとパターンマッチングのデバッグをひたすらしました。
それで、実際に動かしてみたらCCAが予想の遥か上を行くくらい重いという結果が出ました。
CCAが重い理由にはまだ気付かなかったけど、盤面が作為的に作られているわけではないので、パターンマッチングはO(n^4)もかかっていないと気付きました。
平均すればO(n^2)に定数倍くらいだろうと予想し、パターンマッチングよりもCCAを高速化する方針を立てました。
最悪計算量しか考えない、悪い競プロ脳でした。。。
3日目
絶望のままCCAが遅い原因を探りました。
累積和の部分が他の数百倍重いと気付き、更に訳がわからなくなりました。
午後になってからチューターに助けを求めたところ、累積和のコードを見て、これはfor文の中で同じ配列の定義と参照が行われている「漸化式型」だから、ベクトル計算の中ではかなり重い、ベクトル化してもそんなに早くなっていない、と教えてもらいました。
ここでベクトル計算機と普段のスカラー計算機の違いを思い知らされました。
とりあえずCCAも累積和を使わない愚直なコードを一から書いたらかなり早くなり、喜びました。(まだ最大ケースを解ける早さではなかった)
そして、ここで事案が発生します。
暇だったラテ君が全てのコードを一から愚直に書いたところ、何故か超高速(当社比)になりました。
どうも僕の書いたコードに(ベクトル計算では)遅くなる書き方があったみたいです。
ラテ君ありがとう。
これにより、突然最大ケースを余裕を持って解けるレベルになりました。
4日目(実装最終日)
パターンマッチングはいじらなくても高速だったので、ひたすらCCAの高速化に励みました。
しかし改善されるどころが遅くなるばかりで、結局そのまま3日目に書いたコードを提出しました。
ホテルに戻る前にチューターの方の爆速コードを見せてもらい、まだ自分達にはやれることがあったのだと反省しました。
4日目の夜、なぜか競プロしたさに火が付き、チーム全員で5日目の朝5時半までPCK2013予選を解く会をやりました。
5日目(結果発表)
準優勝とワークスアプリケーションズからの賞を頂きました。
ラテ君は誕生日での準優勝となったみたいです。
優勝チーム(駒場高校、チームgomaba)だけタイムが飛び抜けていて、実力の差を思い知らされました。
明石高専との交流
明石の人々(チームReewNen、ShinQ)との交流をしました。
とにかくプロだらけという印象でした。
下の学年の人からもやる気をもらうことが出来ました。
というか頭の良さで負けてそうでした。
あと明石の某IOI日本代表の人に惚れました。
明石と仲良くなれただけでもSuperConに来た意味があったと思います。
感想
今回のSuperConは全チームが手探り状態(ベクトル計算はSuperCon初？)だったこともあり、運があってこその準優勝でした。
それに、更なる高速化の手段もまだあったにも関わらず4日目で高速化することができなかったので、周りのチームに運があったら負けていたと思います。
あと、僕が今回一番頑張ったのはラテ君のマネージメントでした。
朝起きてパズドラ、ホテルに戻ってパズドラ、と大変でした。
朝起こしたら「やだ、嫌い！」と言って蹴られたりもしました。
結局はラテ君の書いたコードで準優勝したので何も言えませんが。
一年生のK君は、期間中、ファイル操作やプログラムのデバッグをしてくれました。
これは僕が一番役に立たなかったかもしれない。。。
