らての精進日記

修行をします

SuperCon2015参加記

こんにちは。らて(@LatteMalta)です。SuperConの参加記を書きます。
僕はチームWestDivで出場していました。

チームメイトは、僕(@LatteMalta)とうぃんじー(@wing3196)と、あと1年生が一人。

-1日目

出発日前日です。

出発日を間違える

翌日新幹線に乗って大阪に行く予定でしたが、このとき実は出発日を明後日だと勘違いしていました。なので、田舎で遊んでました。



楽しい花火大会の途中でしたが、ここでとんでもないツイートが飛んできました。



同じ部活のカフェオレ先輩が助けてくれました。ありがとう。


ちなみに、早朝からお母さんが車で駅まで送ってくれました。ありがとう。

0日目

新幹線で大阪に行く

みんなで楽しく新幹線。楽しいな。

大阪到着

大阪に着いてからは、まず大きな本屋さんに行きました。

「初等整数論」と「プロの数学」という本を買いました。どちらも難しすぎてつらい。

そのあと適当にご飯を食べたりして寝ました。

1日目

朝

頑張って会場に行きました。

僕らのちょっとあとに、明石高専の怖い人たちが来て、とても怖い。

あのReewプロがいる。IOIのオーラがちょっとある。

本戦問題

なんか難しそうだと思いました。


問題の内容は、循環的セルオートマトン(CCA)に関する問題でした。
まず{\displaystyle N×N}の2次元グリッドの初期盤面の情報が与えられます。
あるルールに従って初期状態から1ステップ刻みに盤面が変化していきます。

初期状態とは別に、盤面が変化する途中を撮影した{\displaystyle \frac{N}{2}\times \frac{N}{2}}の写真の情報が与えられます。
この写真が盤面のどこを何ステップ目に撮影した写真かを判定する問題です。

ただし、写真は解像度が落ちています。具体的には、{\displaystyle 4×4}のグリッドを、大きな{\displaystyle 1×1}のグリッドに変換してあるみたいです。

スーパーコンピュータの特徴

今回使用するスーパーコンピュータは、大阪大学のSX-ACEというものでした。
スカラー計算機とは別にベクトル計算機を持っていて、同じ処理を同時に実行できるらしい。
さらに、CPUが4つある(?)らしく並列化もできるとか。

今回のSuperConではSX-ACEのベクトル化と並列化を十分に活用したプログラムを書かないと時間内に答えを出すことが出来ない、みたいなことが問題用紙に書いてあって怖かった。

競技開始

とりあえず遅くてもいいから動くプログラムを作ろうということになり、僕がCCAをシミュレートするプログラム、うぃんじーが盤面から写真を探し出すプログラムをそれぞれ書き始めました。

とりあえず愚直にCCAを書きました。
具体的には、まず盤面を{\displaystyle (N+4)×(N+4)}に拡張して、元の盤面の周囲2マスに反対側の端を持ってきました。
そして適当に累積和を取りました。


途中で昼食をとったりして（阪大の学食で食べました。おいしかった。）、午後からまた頑張りました。

競技終了

1日目が終わった段階では、やっとCCAが動いたという感じだった。


ホテルに帰ってから、{\displaystyle 16×16}のケースでCCAが正しいか確認しました。

普通にバグってたので頑張って修正してそのまま眠りにつきました。

2日目

競技開始

気合を入れて競技開始。しかし、ホテルで印刷したコードを写し間違える。
デバッグに4時間ぐらいかかりました。ごめんねうぃんじー。

なんとかデバッグを終え、CCAが正しく動くようになりました。
うぃんじーが写真を探すプログラムを書いてくれたので、マージしたら{\displaystyle 96×96}で正しい答えを出すことが出来ました。
進捗はあまりよくなかったけどとても嬉しい瞬間でした。

競技終了

なんとか正しく動くプログラムが出来たが、実行時間が最悪だったので結構焦ってた。

3日目

競技開始

高速化する工夫をいろいろしてみるが、あまり効果がない。{\displaystyle 400×400}のケースでも何百秒もかかるし、{\displaystyle 2000×2000}のケースを10分で3問とか絶望だった。


絶望の昼食、おいしかった。
絶望の強制休憩タイムでは、明石高専の人々と交流するなどした。


いろいろ試した結果、重い原因が累積和を取る部分だと判明する

for(int k=0;k<5;k++)
    for(int i=0;i<MAXCELL+4;i++)
        for(int j=0;j<MACCELL+4;j++)
            Sum[k][i+1][j+1]+=Sum[k][i][j+1]+Sum[k][i+1][j]-Sum[k][i][j];

このような一般的な累積和の式は、漸化式なのでベクトル化しても速度が出ない（もしくはベクトル化されない？）みたいな感じらしい。
SuperCon詰んだな(確信)という感じだった。

突然の高速化

うぃんじーが累積和を使わないもっと愚直なプログラムを書き始めたので、僕は累積和を使ったプログラムを高速化しようとしていた。

累積和使うプログラムとにらめっこするのに嫌気がさして、僕も累積和なしのプログラムを書き始める。


なんか突然高速なプログラムが生まれる！！

びっくりした（こなみ）

急に{\displaystyle 2000×2000}の一番でかいケースが144secで動くようになる。
さらに、自明に意味の無い文を消したら129secになった。

やったね。

競技終了

ホテルに帰り、CCAのさらなる高速化案を考える。

飽きたのでパズドラしてたらうぃんじーに怒られた。ごめんねうぃんじー。

4日目

競技開始

昨晩ホテルで考えてきた高速化案（そこそこ自信あり）を全部試してみる。
すると、どれも意味なかった。むしろ遅くなるものまでいた。きれそう(Reewプロ風に)


結局ほとんど何も変更せずに提出した。つらい。

競技完全終了

お疲れさまでした。

ホテルに帰って、適当に休んだ。

突然の競プロ

夜中に、チームメイト全員でPCK(パソコン甲子園)の過去問を解き始めた。朝の5時までやってた。(ただし、がっこうぐらしは見た)

5日目

僕の誕生日です。

結果発表

5位くらいだといいなあとか言ってたら2位だった。
あと、ワークスアプリケーションズ社から特別賞を貰った。

懇談会など

この日もほとんど明石高専の人としか交流しなかった。
ずーむとか白鷹とかそこらの怖い1年生が怖かった。

帰宅

お母さんにめちゃくちゃ褒められた。ありがとう。


感想と反省

一応2位をとれたが、1位のチームとの差が異様に開いていた。

1位のチームがかなり圧倒的だったが、2位以下はそこそこ僅差だったのでかなり怖かった。

実力のない僕としては、たまたま速いコードを錬成できてよかった。

まとめ

精進します。