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

4bitにっき

ぽよ

SuperCon2015参加記

チームWestDivとして、SuperCon2015本選へ行きました。

関西勢です。

同じ久留米高専からもう1チーム(stairgr)出てます。

 

チームWestDiv

らてくん(2年) @LatteMalta

K君(仮名)(1年)

僕(2年)

チームstairgr

幸猫先輩(3年) @Koubyou_sachi

KO(2年) @sujinbemani_79c

てらくん(1年) @555Tera

 

ラテ君とテラ君は別人です。

 

 

0日目(移動日)

集合日に日付が変わった頃、ラテ君は星野村で元気に遊んでいました。

 

 

 車で送ってもらったみたいです。

 

移動

新幹線でプログラミングしたら酔いました。

今回は切符落とさなかったです。

 

書店へ

丸善&ジュンク堂梅田店へ本を買いに。

しっかり15000円弱溶けました。

ここで大阪に来た最重要の目的を達成。

 

寝る

寝ました。

 

 

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君は、期間中、ファイル操作やプログラムのデバッグをしてくれました。

これは僕が一番役に立たなかったかもしれない。。。

 

次はパソコン甲子園競技部門や学校のテストがあるので、数学&競技プログラミング頑張ります。

またパソコン甲子園で東のDiv君や明石高専の人々と会いたいです。