雑記

書きたいことを書く

SuperCon2018参加記~予選篇~

はじめに

 SuperCon2018の予選に出ました。僕は提出コードにほぼ手を加えてないので実質マスコットですが、キーボードが打てるマスコット*1としての仕事はしたのでここに記します。

ところで

予選篇とか書いてるけど本選なかったらクソザコですよね、まあ通ると信じてこうしましたが

6/20 更新しました

keymoon.hatenablog.com

SuperConってなんやねん

 高校生がチームで参加できるプログラミングコンテストです。予選、本選ともに長期間*2で一問を解きます。スコアで競う場合もありますが、今回の予選は特定の解を出すための実行時間で競います。

 チームは2,3人で、本選出場者は関東・関西でそれぞれ10チームずつです。

 本戦だとスーパーコンピューターを使って問題を解きますが、予選は普通のパソコンで解ける程度の問題です。

問題概要(PDF)

 予選に関係する1級認定問題のみ説明します。*3

 端的にいうと、

格子上で(0,0)を始点とする閉路のうち、交差しない(同じ点は1度しか通らない)かつ特定の点を通らないような閉路の総数を求めなさい

という問題です。*4(分からなかったらPDFを見るなりすると雰囲気が掴めます)

僕がしたこと(概要)

ひたすらテストした 以上。*5

詳細

C++が書けないので、C#でexeを実行してランダムにテストケースを実行させ、ベンチマークを取ったり愚直解と比較したりするテストを書きました。ログはJsonで吐き出して解析しやすくしました*6

愚直解ですが「絶対に間違いでないと保証されている解」が欲しいとのことで最低限の枝刈りを*7行ったDFS*8で解を出しました

最高320万くらいで、6分くらいで終わります(平均3分程度。遅い)

失敗一覧

人の失敗って見てて面白いですよね。教訓にしてください

  • めんどくさがり性のせいでtesterを書くのが1日遅れた*9
  • コンパイルオプションの-Oを-oとしていてコンパイルオプションがかかっていなくて、遅い奴で動かしていた*10
  • パフォーマンスを比較する時に別実行ファイルを比較しているつもりでいたら同じ実行ファイルを比較していた*11
  • Seedからの復元性がなかった*12
  • そもそもこれを書いてる時にまだ提出が済んでいない。

経過

5/30

SuperCon、組めたら組もうね~ってKMCodeと話した

5/31

部でいろいろ聞いて回ったけど確定した1チームしか観測できなかった

~~(僕は)虚無~~

6/10

SuperConに出るっぽい流れになったので取り組むことに。

いきなり1000msが来て、その少し後に600msのソースが降ってくる。

僕がテスターを作る感じになったけど、サボる(クズ)

6/11

テスター今日中にできる?って5時くらいに聞かれる。焦って適当に書いた

6/12

一晩寝かせて400ケースくらい調べたけどWAが出なかった。

いろいろと改善が降ってきて試したが、漏れ/被りがちらほら出て怖かったのでやめた(1/1500くらい)。

オーバーフローに気がつく。ソースコードへの唯一の貢献!

テストケースをいっぱい錬成して試すことに。テストケースはハッシュ値から再生成ができるようにする

6/13

解析したデータをスプレッドシートとかに起こした

最適化オプションの指定漏れに気がつく。死

指定し直して適当に解析したら400ms程度を出す。このまま提出用のコードを書いて後はテストするだけ

あれ?????テストケースの再生成できなくない?????→テストケース5000個くらいが無に帰す

引数自体を愚直に保存すればいいのに。って思ってそうする

チーム名を適当に考えるも何も思いつかない*13

ここらへんで英字8字縛りに気がつく→何も思い浮かばずに死

6/14

パソコンの自動スリープをオフにして持ち運び中もテストケースを錬成できるようにした。ThinkPadのぬくもりを感じて「これが彼女か…」ってなった。*14

昼休み(12:20頃)に提出準備*15。その頃にテストケースが4000個くらい生成できたので並行してテストする。

WAが0だったので満を持して提出。

テスターを公開すればコンテスト後に情報が迅速に集まる可能性があるな~って思ってテスターを改修。

あとテストケースが10000個くらいあると嬉しいかもしれないと思ったのでマイニングを継続

6/15

334のがしたけどテスターの改修が終わった ガバガバだけど動く

みんなの報告を全裸待機 それだけ*16

感想

つかれた。僕がポンコツで相方さんに迷惑がかかるので割と申し訳のなさみりてぃが高い。

なんかね、本選に行けたらいいねって感じです。*17*18

ということで

なんか最後の方にも書いたけどテスターを公開します。情報が欲しいです*19

一応コマンドラインでヘルプとかは完結するようにしましたが、readmeを読むと使い方がより詳細に書いてます。

ダウンロードリンクは以下です*20

ダウンロード

*1:SuperCon、マスコットとしてついていくとは言ったけどキーボードが打てるマスコットとしての作業程度はする()

*2:予選は15日くらい、長い。

*3:肩慣らしみたいなのがついてますが、それはどうでもいいです

*4:自己回避ループ (Self-Avoiding Loop、略して SAL) と呼ぶらしい

*5:というとちょっと嘘で、一箇所オーバーフローを見つけた えへへ

*6:区切りのカンマを忘れて死んだりとかした

*7:マンハッタン距離が残りターン数より少なければ切る,スタート地点の近傍が埋まったら切る

*8:いつもBFSなのでなにげに書くのは初めて

*9:謝罪しか無いです。懺悔of懺悔

*10:バカすぎる

*11:差が出ないしWAがも出ないしで喜んでいたら死んだ

*12:後述しますが、クソ致命的だった

*13:候補案:Tourist抗酸化物質国務長官,スーパー皆伝68

*14:電車で発熱するPCが入ったケースを抱いて壁にもたれていた時に、PCケースとお布団の類似性を見出した。

*15:準備室のパソコンがポンコツでむっちゃ固まった。

*16:Keidarooさんが提出できるかが割とヒヤヒヤでした

*17:正直どんくらいのタイムなのか、高速化の方針があってるかとかが無茶苦茶不安でマジで不安です

*18:というか恣意的に落とすコーナーケースとかをあまり検討しなかったので結構怖い

*19:解析したら是非、というかTwitterでつぶやいてくれ~~~~

*20:ソースは本選で使えそうな気がするので一応非公開です。たった100行くらいだけど。