第27回全国高等専門学校プログラミングコンテストに参加した

第27回全国高等専門学校プログラミングコンテストに参加した

Summary

#procon27

書くこと

1. 我々のチーム「パズル、それは競技道にとって大切なことかな」の動き
2. 私の伊勢旅行
3. 競技部門について
4. 感想

パズル、それは競技道にとって大切なことかな

　我々のチームは私ふるつきと、mi_24vくんと、後輩でかわいいT君（仮名）で構成されていました。それから、オブザーバーとしてmatsusaka_gyu先輩をお迎えしていました。

本番では

　我々のチームは、複合機とスゴイバッテリーを用意して、ピースとわくをスキャン、Solverにかけて適当な解を得た後、配置をプリントしてそれに従ってピースを並べる作戦を建てていました。

　予行演習ではSolverを走らせたところで時間切れ、一回戦では電源の安定した供給が出来ずに人力（多分シガーソケットのはまりが甘かったのだと思います）と用意した作戦がうまく使えず、準決勝でやっと作戦を実行することができました。しかしSolverが良い結果を出せず、配置は人力で行いました。ユニークな作戦で特別賞を狙っていたことを考えると、準決勝ははじめから人力で堅実に勝ちにいき、決勝でプリンタを使うべきであったなと思っていますが、決勝で複合機が動作する保証がなかったので仕方がなく、「負けてもいいから絶対に印刷を成功させる」という作戦で臨みました。

それまで

　Viewerと印刷部分をmi_24vに丸投げしました。Input部分は頂点の検出ができるところまでを私が書き、あとはT君におまかせしました。ここでは、matsusaka_gyu先輩の力もお借りしました。

　Solverは私が書きました。最初は角度を見て、ある角を「構成可能」なピースの組み合わせを部分和問題を解いて列挙し、完全解答を狙うプログラムを書いていましたが、実装力の低さから断念し、ピースをランダムに配置する焼きなまし法を書きました。

　焼きなまし法では全然だめだったのでもうすこしヒューリスティックに解を求めようと書いたのが実際に使用したSolverでMieFillingという名前になりました。各ピースはぶつかるとその分だけ逆方向に平行移動します。これだとそこそこの解がでやすいです。

私の伊勢旅行

金曜日は4限まで授業に出て、午後からの授業は公欠をとりました。そして、近鉄の急行を利用して宇治山田駅へ向かいました。

その日はなんか受付をして宿に行きました。山田館というところでしたが、高専生で埋まっていたようです。

　夕食

　宿では開発を続けました。指導教員には「三時間はかならず寝てください」と言われました。ぎりぎり三時間眠りました。

　翌日はそこそこに起きて汚い部屋を放置して観光文化会館に向かいました。お昼は「まんぷく堂」という店で唐揚げ丼を食べました。

　その日の夕飯は「昨日と同じところ」組と「新規店舗開拓」組にわかれましたが、最終的に合流しました。

　その日の晩もぎりぎりまで開発をしていました。

　起きたらすこぶる体調がわるいみたいな感じでした。朝ごはんも残してしまった。さらに生憎の天気でゴミ袋を裂いて複合機を覆ったり部屋を片付けたりしていそいそと出発しました。

　午前中に敗退したのでその場を去り、伊勢うどんと手こね寿司を食べました。

　それから、外宮を観光しました。人で賑わっていて嫌でしたが良い場所でした。貸し切りで観光したい。

　ゆっくり歩いても閉会式に十分に間に合いました。

　帰りはmatsusaka_gyu先輩と一緒に特急に乗りましたが、体調が悪すぎたので寝ました。近鉄特急格好良い。

競技部門が燃えた

　筋肉最強説がながれて実際最強だったので燃えてました。多分n-1Solverを書いて迅速Submitがツヨイかなと思ったのですが、入力の手間も考えるとそれでも「筋肉に余裕で勝てる」レベルには到達してないと思います。多分「めっちゃ練習をしていて筋肉より辛うじてツヨイ」程度になりそうです。そこまでしてプロコンで勝ちたいかというと私は違って、もしそんな考えで今回の問題を設定していたらそれはプロコン思い上がりすぎだろみたいな感じになります。こっちは長い時間を消費してるんだ。

　なぜこんな形になったかと言って、多分去年奈良が「まったく解を提出できず最下位」とかやったり「見た目がクソ地味」とか言われたりしたので今回のような競技形式になったのだと思いますが、前者に関しては「完全に奈良が悪い」のでもっとプログラミングさせてください。見た目がクソ地味はなんかしゃーないですよねでもアクロバティック将棋なんて見たくないですよねみたいな意見しか出せません。

　あと個人的な不満を出すと、解の設計図をピースと比べていたときに運営に「やめてください」と言われたのがすごい嫌でした。カメラで取っているからなどの理由もあったのでしょうが、こちらはシステム詳細のようなものまで提出していて、レギュレーションにも違反してないのにみたいな感じでした。

　今回はサイコロ数え問題と並んで残念みたいな感じでしたが、良い問題をだしている年もあるときくのでがんばってください。

感想と反省

　競技はあんまり楽しくなかったけど「奈良すごい」と言ってもらえて満足です。でも来年はあんまり出たいと思えない。伊勢はとっても楽しかった。あの町並みとか海鮮とか、とっても良い街だった。

　練習不足が響いたりしました。A3スキャナではピース全部をスキャンできなかった……。

SuperCon（スーパーコンピューティングコンテスト）2016の本選に出た

SuperCon本選でチームワークを発揮したので、kingyo（は3位だった。すごいな。

SuperConについて

よくわからなかったが、SuperComputerのすっごい資源をつかって計算させてくれるプログラミングコンテストだと思う。今年は東工大のTSUBAMEというスパコンを使った。

予選

私は予選の問題はさっぱりわからなかったので。チームメイトが去年JOIの本選にでるなど健闘していたのでJavaで解コードを書いてもらい、C言語に移すなどしていた。要項にはANSI Cに準拠すること、とあったが、ANSI CがどんなCか全然わからず、不安のなか移植をした。

枝刈り全探索みたいなコードだったと思う。C言語のよくわからない型挙動に苦戦しつつなんとか動くコードにして、提出した。このときは予選突破があるとは思ってなかった。

それからn日くらいたって予選突破報告がTLに流れ始めたが、我らのチームにはメールが来ず、やはりだめか……と言っていた。しかし本戦出場の意思がないチームがあったのか、なんか一番お尻につっこまれて本選にでられることになった。かなり嬉しかった。

本選

本選では5日間阪大に通った。家からだと2.5時間くらいかかるので移動が長かった。 それはそれとして、とりあえず本選で問題の説明がされたりした。できるだけ良いスコアを出す系の問題だった。

私はそういう問題の対策は山登り法と焼きなまし法しか知らなかったので、焼きなましっぽいのの実装を始めた。チームメイトはランダムではない方法を模索したり、GPUで評価値を求めるプログラムを書いたりしていた。

二日目の終わりくらいにはほとんど焼きなまし完成みたいな感じで、動くコードができていた。手法としては、グラフ中の四点（二点同士が辺で結ばれている、などグラフの正則性を保つような制約つきでランダムに選択したもの）の辺をつなぎ替えるみたいな感じだった。これをtsunaginao_c関数と名づけて、ファイル名をtsunaginao.cとしてうまいじゃんと笑っていたが、後にcudaを導入してtsunaginao.cuになったりした。

あとは重み付けとか、評価関数とかを書いていた。評価関数のワーシャルフロイドをバグらせていたのは笑える。

三日目くらいにはちゃんと動くようになっていた。サンプルの小さいケースを食べて値が出る！　などと無邪気に遊んでいた。この時点では初期グラフの良さがそのまま出力に直結する感じだったので、初期グラフをn回つくれるように改良したりしていた。

提出練習でもそれなりに動いたので手応えを感じていた。チームメイトの一人が行列積のGPU高速化番を作ってくれていたのでそれを使ったら最大ケースで2.5s程度で評価関数が動作していい感じ。本当はもっと早く、10倍くらいにはなるらしい。

4日目は初期グラフをランダムではなく規則的に並べる方針を採用した。初期値は悪いが、焼きなましと相性が良かった。初期グラフが綺麗なのでプログラム名はkireiとなった。

さらに辺の交換ではなくて色の交換を行った。これ自体はあんまり機能しなかったがこれとtsunaginao_cを組み合わせるといい結果がでるケースがあり採用となった。これを用いたプログラムがchimeraとkirei_swapvと名付けられた。

さらに、競技直前に、「ある程度結果を出した後のグラフからもう一回やりたくない？」という話が出てこれの爆速実装を行った。これは初期グラフ生成のかわりにグラフを読み込む処理を加えるだけなのでそんなに難しくはない。しかしここまでで、gpu（これが最初のプログラム）、kirei、chimera、kirei_swapvと四つのプログラムを作ってしまい（それぞれコピーしてディレクトリごとに管理していた）、それらのすべてに手を加えなければならないので大変だった。実際、gpu以外のプログラムでのrestore機能の実装は競技開始してからだった。

四日目なのでお昼すぎから競技だった。だいたい、一つの問題ケースにたいして5minずつ割り当てて、chimeraとkireiをつかって頑張っていた。最初はGPU利用の競合を懸念して一つしかSolverを走らせなかったが、とちゅうから並列で走らせた。ちゃんとプログラムが遅くなって面白かった。

最初は全然振るわなかったkingyoだが、なんか次数がでっかいケースなどつよいのでは？とか適当に考えて6問目を回したところ、1位かそれに準ずる順位を取れて俄然士気が上がった。それぞれの問題で10～6位程度を取れたので、restoreプログラムを活躍させて一回submitしたファイルから計算を再開させるなどしてちょっとずつスコアを改善するちくちく作戦をやっていた。ここでrestoreでは焼きなましが走ってしまいなんかせっかく山に登っていたのに降りやすくなってしまっておもしろかった。kireiに関しては完全に山登りにしたnouseというプログラムをforkして走らせたりしていた。どちらでも結果はそんなに変わらない感じだった。

そんなことをしていると1位を取れる問題がいっこでたので、それのSolverは競技中ずっと走らせていた。

競技終了前の平均得点は4位相当だった。最後の５分も計算させてsubmitし四日目を終えた。

最終日は表彰式があった。なんか最後の5分で4位くらい浮上している問題があり3位だった。

表彰後は懇親会みたいなのがあったのでたこ焼きとフライドポテトを食べながら優勝チームやそうでないチームと話をした。

他のチームのひとの話をきいていると考察がなされていて頭がいいとおもったり、うちの評価関数はめちゃおそいということがわかったりしてもっと戦えたのではと思った。

その他

何かもっと書きたかったかもしれないが忘れたのでいいや。

mixi git challenge に参加した

blogに書くまでが遠足らしいので。

summary

mixi git challengeという催し物がありました。mixiさんが開催している、gitの問題解決コンテストのようなものです。

私はそれに出場しました。

結果、2位でした。

とても楽しかったし学びになりました。部内でgit challengeみたいなものを開きたいな、などと思いました。

summaryじゃないやつ

学校の先輩に紹介されてmixi git challengeというものを知りました。git限定のCTFのようなものだと理解して、早速申し込みました。ちょうどSANS NETWARSの後の日で非常に都合が良かったです。

運良く、行けることになりました。同じ学校、同じ部活から kyumina と mi_24v も参加できることになり非常な幸運でした。

SANS NETWARSに出た次の日、mixi git challengeに行きました。NETWARSでの疲れがでて、当日の朝はちょっと寝坊をして、朝ごはんを食べそびれました。

mixiさんのオフィスにたどり着くと、私達チームのテーブルに案内されました。チーム名はfoxtront。alpha、bravo、charlie……でhotelまでありました。

チームメイトはkyuminaでした。

コンピュータのセッティングをしたりしていると、開会しました。この時点では mi_24v が来ていなかったのが面白かったです。

お昼のタイミングでは、チュータの方（mixiのひとです。宗教はEmacsらしいです）とお話をさせてもらいました。kyuminaと一緒に結構突っ込んだ話などもして、楽しかったです。

さてお昼から3時間半くらい、競技をやりました。簡単なものでは、「昔のコミットメッセージが間違っていたので修正してください」というものや、難しいものでは、大量のブランチとコミットによる地獄をなんとかしろみたいなものがありました。

得点の幅は1 - 6でしたが、圧倒的に2点問題が多かったので、3点、5点、6点が非常に怖くみえました。

私たちはとりあえず1点の問題に着手し、kyuminaがいい感じに点をとってくれました。

その後、やっと最初に手を出した問題を解くことができ、もう一問1点の問題を解いて、さらに、2点問題を2個か3個くらい解いたと思います。これらは、googleと push -f でなんとかなる問題でした。

そんなこんなをしているうちにあっという間に競技時間が終わり、気がつけば2位でした（1位のチームは3点問題を2問解いており、さらに私達が解けなかった2点問題を1問解いていたので、8点もの差がありました）。

2位なので、Octcatをもらったりしました。 その後は懇親会があって、 mixiの人のありがたいお話をきいたり、とにかく楽しい時間を過ごしました。

おわり