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

「っこ」のブログ

っこがプログラミングに関しての記事を書くブログ

SuperCon2015参加記

8/17~8/21にSuperCon2015の本選が開催されていました。
自分は幸猫さん(3年)、テラくん(1年)と共に「stairgr」というチームで参加していました。
同じ久留米高専から「WestDiv」という自分たちより強いチームも出ています。

↓「WestDiv」チームの一人であるうぃんじーのSuperCon参加記↓
winjii.hatenablog.com



8/16(競技開始前日)
福岡県→大阪府へ新幹線での移動です。3時間弱で着いたので驚きました。
到着後時間があったので、梅田駅に移動し、ヨドバシカメラジュンク堂に行きました。
正直、何も買わないつもりでしたが、ジュンク堂の数学関連の本が置いてあるあたりで一目惚れしてしまいました。

「鳩の巣原理」を用いた、面白い証明が載っている本です。数字パズルなどが好きな人は絶対好きだと思います。
ただ、この辺りの証明に詳しすぎると少し簡単すぎるかもしれません。僕には丁度いいです。まだ最後まで読んでいませんが、じっくりと読んでいきたいと思います。
その後は適当な店で食べてホテルに帰って寝ました。


8/17(競技1日目)
大学って広い。大学に入ってから目的地まで10~15分くらい歩いたような気がします。
受付の時点で問題が配られたので、待ち時間の間に問題を読みました。問題はこんな感じでした。
・化学振動がモデル。
・n*nのセル状に分割された盤面がある。
・各セルはそれぞれ、0,1,2,3,4のいずれかの状態である。
・各セルは周りのセルの状態により、次の状態(4の次は0とする)に変化したりしなかったりする。
・[全てのセルにおいて変化するかしないか判断する→変化する条件に当てはまったセルが変化する]の流れを1ステップとする。
・盤面の動きのモデルのことをCCAという。
[入力]
・最初の盤面
・写真(あるステップ数(100~50000の100刻み)進めた盤面の一部分。解像度が下げてある。)
[出力]
・写真は何ステップ進めた時にどこで撮られたものか。

この問題は、
・ステップを進める様子(CCA)をシミュレートする。
・盤面と写真の一致部分を探す。(パターンマッチング)
という二つの部分に分けることが出来る。
と問題文といっしょに書いてある「ポイント」という欄に書いてありました。

SuperConの特徴でもあるスーパーコンピュータ(スパコン)は、
阪大のスパコン「SX-ACE」。
並列化以外に、「ベクトル」という配列に対するループ文を高速に行う仕組みがありました。
並列化もベクトル化もほぼ自動でやってくれますが、それらが可能なコードを書かなければなりません。

競技時間になってから、自分たちのチームは、とりあえずしっかり考察をしようということになりました。
愚直にやったときの最悪計算量は、係数(2,1/8等)は無視で、
CCA:n*n*25(見るべき周りのセル)*50000(ステップ)
パターンマッチング:n^2*n^2*500(100ステップ毎のため)
と見積もりました。
ただ、パターンマッチングは、違う場所が見つかりしだい、breakすればいいので、そのbreakするタイミングがなるだけ早くなるように、確かめる場所の順番をバラバラにしようという話になりました。
CCAはn*n*25*50000は、n*nの部分を削るのは無理だという話になり、25(周りのセルを参照する回数)か50000(ステップ数)を短縮できるのではないかという話になった。
ここからは、具体的な解法もでたが、25の部分を25や25を上回ってしまう数になる解法ばかりで使えなかった。1文字もコードを書かずに1日目終了。
ホテルに帰ってからも考えるつもりだったが割と時間が遅くなってしまったのであまり何もしないで睡眠。


8/18~8/19(競技2~3日目)
幸猫さんがパターンマッチングの部分を実装している間、自分がCCAの部分のことを考えたりする。
そして2日目の午後くらい(違ったかもしれない)に色々思いつく。それまでは、幸猫さんがパターンマッチング、自分がCCAだったが、思いついた部分がそれぞれの逆だったので、仕事を交代する。
正直2日目の記憶は曖昧なので詳しくは書けない。
3日目は完全に方針が固まっていたので、固まった方針で実装をし始める。
方針
CCA:累積和でほぼ愚直に。
パターンマッチング:累積和と似たような方法で0の数を数え、全体と各列と各行の0の数があっていたら一致と判断。
CCAの担当になった幸猫さんはかなり速めに実装が終わったので、スパコンにCCAの部分のコードを投げて速い遅いの検討、高速化などをやる。
自分はパターンマッチングの部分をやっていたがバグらせまくり、作業時間の最後までバグり続ける。
バグってるが動いてはいたのでコードを印刷をしようとしていたのだが、自分が焦りすぎて、急いでUSBを抜いたところ、データが破損し、印刷できなくなる。
幸猫さんの最新バージョンのコードと自分のコード全てを印刷できずホテルに帰ることになる。ごめんなさい。
ホテルに帰り、自分はその日書いたはずのコードを全て書き直し、幸猫さんは最新バージョンを思い出しながら書き直す。
が、ここでも自分のパターンマッチングのコードがバグりまくる。
朝6時前くらいにやっと治る。CCAの部分の検討が終わり1時間30分程度仮眠を取った幸猫さんに統合を任せて自分は仮眠。
7:30くらいに起こされて自分のパターンマッチングがバグっていると告げられる。最悪の目覚めである。


8/20(競技4日目)
とりあえずホテルで書いたコードを印刷し、会場で写経したが、色々なバグが出る。
幸猫さんのCCAの部分が直ったのが確認できた後もバグっていたので、やはり、自分のパターンマッチングの部分がバグっている判明。
昨日書いて印刷できなかったコードのほうがバグが少ないと判断し、そっちのコードを統合してもらう。
それと同時にどこがバグっているか探していたがなかなかわからず。
色々いじくっているうちに直ったっぽい???ってなって統合したら直ったことが判明。どこがバグっていたかは今でも分からないです。
そしてこのタイミングが競技終了20分前です。
大きめのケースを投げたところ、CCAだけのときよりだいぶ遅くなっていることに気づいたが20分前だったので直せず。恐らく自分のコードになにか潜んでいたようです。


8/21(結果発表/懇談会)
結果

17位/20チーム
久留米高専から出たもう一つのチームは2位&企業賞をもらったので学校としては良かったのですが、自分たちのチームは散々でした。
この後反省すべきことを書きます。
懇談会では明石高専の人と交流できたのでよかったです。


反省点
[重要なこと]
・とりあえず実装する。(愚直解法でも)
 今回は、結局パターンマッチングは愚直解法で十分早く、CCAも、累積和など凝ったことをするよりは愚直にやったほうが速い結果となりました。
 いつもと違う実行環境でプログラミングをするので、何が速くて何が遅いか分かりません。実装してからなにが良いかを探りながらやっていく方がよいのだと感じました。
・わからないことはチューターさんなどに聞く。
 直接解法に触れること以外は教えてくれるチューターさんをうまく利用しなかったのは失敗でした。
 事前に渡されたベクトルに関する資料を読み込んだだけで、おおよそ分かったつもりになっていたのがいけなかったと思います。
・モチベが下がっても頑張る。
 自分のパターンマッチングのコードがバグりまくった時にモチベが下がり効率が落ちていました。そこで踏ん張る力は必要だと思います。
[さほど重要じゃないこと]
・英語力
 「USB抜き忘れないで!」を「USB刺しちゃダメ!」と和訳し間違えたのはまだしも、名づけに時間かかるのはアホだった。
・神経・脳・精神系の病気の人とエナジードリンクの相性
 ADHDなどの人がエナジードリンクを飲むと、逆に眠くなったり集中できなかったりすることがあるらしいです。
 自分はとても軽度の強迫性障害持ちですが、眠気は吹っ飛びましたが強迫性障害の症状は強くなり、集中力も吹っ飛んでいきました。


最後に
自分はSuperCon自体もあと一年あるし、他のコンテストもあります。今回は結果だけ見ると悲しい結果になってしまいましたが、様々な経験になりました。やはり、コンテストは参加するだけでも大きな意味があると思います。これからのコンテスト、特に来年のSuperConに今回の経験を活かしていきたいです。