サイバー甲子園に参加した

まとめ

サイバー甲子園に参加しました

なんか会場入りしたら格好良い本がおいてあって最高でした。

机においたあったけどこれなんだろう……？ pic.twitter.com/HVrxnziE99

— ふるちゅき (@theoldmoon0602) 2016年11月12日

CTFが始まって、私はinsecureという一人チームでした。

解いた問題のWrite-Upは後に述べるとしてCTF中どうだったかと書くと、序盤は自明問題をさくさく解けたので2位か3位で「これいけるじゃんね最高」とかなってましたが、そこから詰まって結局2000ptsとれずにつらい思いをして終わりました。

結果は五位で、優勝したチームと2位のチームと3位のチームと4位のチームに負けました。4位のチームに負けたのと2000ptsボーダを超えられなかったのがとてもつらいです。

でもひとりで頑張ったので一人で頑張ったで賞として京都府警の課長賞（詳細な賞名はわからない）をいただきました。身に余る光栄です。なんかこれは履歴書にも書けるそうなんですが、どのくらいすごいんでしょうね。

それから懇親会に出ました。産技高専の人と喋ったり、沖縄の人と喋ったり、優勝したチームの人と喋ったりしました。懇親会は楽しいのでいいですね。

それから帰りました。有意義な一日でした。

Write Up

自明問題しか解けていない上、自明問題の中にも解けてないものがあったのでつらいです。解説をきいたら、これ三問くらいは解けて当然じゃ～んみたいな感じでした。stegsolveの名前をど忘れしたやつとSESSIONがmd5になってるのに気が付かないやつと、icmpのttlが変わってるのに気がついてないやつ。

それから、binaryが一問も解けてないので弱点が露呈した感じなりました。

Assembler Tanka

かの有名なアセンブラ短歌です。SECCON{57577}と吐くアセンブラ短歌を渡されて、これを実行できるというサイトの存在まで教えられたのでそこに投げるだけです。アセンブラ短歌すげぇ

gokai?

base64 -dを5回やるとSECCON{BASE64}が得られるような文字列が渡されました。

very easy

16進数が幾つかスペース区切りで渡されるので "".join(map(lambda x: chr(int(x, 16)), それ)) みたいにするとフラグになります

decode the flag

暗号化鍵と暗号化済みファイルが渡されるので、 "cat それ | openssl {} -d -k '鍵'".format(暗号化形式) みたいなのを回したら解けます。

gettheflag

なんどかHTTP通信をしているpcapがわたされるので strings それ | grep true みたいな感じにすると縦読みのflagが出ます

megrep

バイナリエディタで開くとSECCON{bsdbanner}というbitmap artが表示されます

x2.txt

ファイルをダウンロードしてきて "".join(map(lambda x: chr(ord(x)/2), open(それ).read()) すると解けます

decode the trapezoid QR code

QRコードをGIMPで補正してやると読めるようになります。

sum primes

エラトステネスとかで適当にたくさんの素数を生成してやって sum(primes[12344:31337]) とかすると解けるはずでしたが採点側がみすっていて時間を食いました。エラトステネスに自身がないときはどこかから素数表をもってくるだけです

blacked out PDF

黒塗りのPDFなので読めます

blacked out PDF again

同上ですが、今度はコピープロテクトがかかっています。でも私のViewerではコピープロテクトを無視していたらしく実質 blacked out PDFです

how much a fine?

なんか犯罪行為と犯罪名称を結びつける問題です。一発で解けますが、せいぜい20回かそこらためしたらおわりです。

acronym

googleです。

感想

解説をきいたら3問程度は解ける問題だったのでつらいです。

第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位だった。

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

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

その他

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