東工大主催のSuperCon2013に参加し、準優勝してきました。2人組です
予選
問題はこちら
2人でそれぞれ予選の解法を書く→ほぼ一致
僕が高速化して、提出
本戦
問題概要
N*Nのトーラス型の盤面がある。(上と下、右と左がループしている)
その上を、3*M個の星が動いている。
星は8方向のどれかに1秒あたり1ずつ進む。つまり早さは1かルート2。
星同士がぶつかると、星は向きを変える。どの向きに変わるかはあらかじめ配列として与えられる。
まず盤面の初期状態の候補がK個(これらをAと呼ぶ)、初期状態から(0.5T, 1.5T)、つまり約T秒たったあとの盤面の候補としてL個与えられる(これらはB)。
星の移動をシュミレートして、盤面の初期状態の候補をL個に絞り込む。
なお、星は3色あり、それぞれM個ずつ
制約
N=500
M=4000
T=5000
予選
K=25,L=10
本戦
K=250,L=100
必ず一つのBに対して対応するAがただ一つ存在する。
Bはそれぞれ、経過時間は違う(3000, 7000, 4500とかいろいろ)
初日
午後
二人でそれぞれプログラムを書いてみようとなる。
書き終わらない。強実装やなぁ
夜
二人とも同じようなアルゴリズムで書いていた。
(盤面1マスずつに対して1つスレッドを割り当ててシュミレーションする)
しかしもっといいアルゴリズムが発覚。プログラム廃棄(1回目)
どうやら星1つに対して1つスレッドを割り当てる方がはやそう
二日目
午前
星を比較するためのマージソートを任せ、プログラムを書く。書き終わる
昼ご飯
そば おいしい
もっといいアルゴリズムが発覚。廃棄(2回目)
どうやら星とは別に盤面も用意しておいて、それをつかって比較すればはやそうだ。
不安だがプログラムを分割して分担する方式でいってみることにした
午後
4時頃?
自分の担当部分が完成。
暇タイム(1回目)
早く書けとハラスメントしてた
6,7時頃?
書き終わる
バグ取りをして、完成
たしかex90(本番と同じサイズのサンプルデータ)が65sぐらいだった？
三日目
午前
中間発表が有るというので、それ用にテスト出力とか消した物を用意。
あと、高速化で45sぐらいまで縮めた
昼
べつのそば屋 おいしい
高速化の種切れが見えてくる。
3時
強制休憩タイム
中間発表、2位
ex30、つまりかなり小さなデータでテストしたらしい
1位、0.3s
2位、0.7s
3位、5s
とかそんなん
1位はCPUでシュミレーションしたらしい。未だに負けた理由が分からない。
午後
暇タイム(2回目)
まったり考えていた高速化をする。が、早くならず無駄骨
夜
暇すぎるのでなんか衝突表から規則を探し出そうとする
斜めに動いてる星の数が保存されている事に気づく
テンション上がり、優勝を確信
なぜもう少し頑張って規則を探そうとしなかったのか。慢心ですね。
四日目
午前
プログラムを俺しか読めなくなるの覚悟でスーパーbit演算タイム
仕方が無いとはいえここからはほぼワンマンチームになってしまった感はある
スレッドブロックのサイズを変えてどれが一番早くなるのかというのをやってもらっていた
高速化で、ついに40sを切る やったね
さらに夜気づいた枝狩りを組み込む事によって25sを切る 優勝を確信
午後
星の比較部分にバグ発覚 さすがに死にそうになる
多少の低速化を覚悟でプログラムを書き直す。
それを提出して終わり
対面で書いていたチームが怖かったが、60sぐらいだということを聞き、優勝を確信
五日目
教授がスライドでひたすらGPUの並列処理について語ってるのを見る。
今年もCPUが勝ってしまった事を匂わせる発言をしたので死を確信。
結果発表。爆笑。学会奨励賞を貰う
感想
楽しかったです。
多分GPU仲良し度ランキングとソースコードの長さ選手権は優勝だと思う。
CUDAガチ勢になればGCJで物によっては数百倍の速度を出せるので、嘘解法を通せるようになる気がした。
複数人でプログラムを俺には書けない事が発覚したので、将来が不安
情報系が集まるとヤバいってことを知った
東工大へ
詫び合格ください
