DDCC2016 本戦 参加記

DISCO presents ディスカバリーチャンネル コードコンテスト 2016 本戦に参加しました。どこよりも早く、を目指して参加記書いてみます。

-N日目 (予選)

セキュリティミニキャンプ in 北海道(過去記事参照) の1日目の夜にDDCCの予選があったので、ホテルからコンテストに参加した。

A問題はすぐ解けた。B問題は日本語が難しかったけどAC。Cは制約をくぐりぬける方法が分からず、結局2完・・・。このときボーダーラインを把握していなかったので絶対通ってないだろうなあと思っていた。

あとあと調べて、自分の順位でも本戦の可能性があることを知った。結局、161位で通過してた。うれしい。でも前回のDDPCを見るにこのままだと本戦で玉砕されるので頑張らないとなあという気持ちになった。

0日目 (本戦前日)

本州に住んでいないので前日移動必須。東京到着が遅くなりそうだったので、空港でラーメンとビールを食べてから飛行機へ。なんか天気予報では雪が降るとか言われてて、飛行機飛ぶのかどうかちょっと怖かったけど無事飛んでよかった。22時くらいにはホテルについてまったりしていた。

1日目 (本戦当日！)

23時半くらいに就寝を試みるも寝れず、睡眠が断続的になる。でも当日は5時に起きた。はやすぎ。前回のDDPC解いたりとかあがいていた。

少し早めに会場につくものの電源争奪戦に敗れる。パソコン2台もってきてよかった。Tシャツとシールをもらって「これがオンサイトか・・・」という気持ちになりテンションが上がる。

オープニングビデオがDDCC開会の合図。自分は北海道から来たのに「北は東北からお越しいただき～」みたいなアナウンスが入り笑ってしまった。開会式終わったらへんからめっちゃ緊張してきてやばかった (緊張のあまり手を震わせながらツイートしていた)。あと隣がやたらインタビューされてて大変そうだった。

そしていよいよ本戦スタート！

• 1問目はEPS考慮したら逆にバグったりしてつらかった(たぶん自分のライブラリに問題がある？)けどAC。
• 2問目は3つ目のケースがどうもうまくいかず唸ってたら部分点解法出すの忘れていた。結局満点取れなかったしつらさしかない・・・。
• 3問目は見たけどやってない。4,5問目は見てすらいない。こうして私の初オンサイトコンテストは散ったのだった・・・(オンサイトの洗礼)

幾何っぽい問題と文字列で攻められたら途端に点数が全く取れなくなるのはダメですね。分野によって理解度にムラがありまくるので、もっと精進していきたい・・・。

コンテストが終わって昼食フェーズ(懇親会)に入る。フォロワーに何人か会えてとてもテンションが上がり、オンサイト最高という気持ちが最高潮に達した。他の大学の競技プログラミング事情とか、競プロサークル等に所属せず趣味でやっている人の話とかいろいろ聞けて面白かった。

特別講演で厚切りジェイソン氏のお話を45分間ほど聞いた。米国と日本の会社の体質の違いとか、厚切りジェイソン氏本人の経験などなど貴重な話をたくさん聞けて良かった。リンゴの話が一番なるほどなあとなって、今だけでなく未来も見据えたうえでベストな答えは何なんだろうということを常に頭に入れて動かないとなと考えさせられた。

表彰式後に、懇親会パート2が始まった。ここでもフォロワーの何人かとお話しできてとても良い時間を過ごせた。来年のICPCの話とかもしてて、来年は国内予選抜けてアジア地区でまたいろんな人に会いたいなあ・・・とか思ってた。

総括

今回が初オンサイトだった私は、問題が解けるかどうかももちろん不安だったけど、競プロerの輪の中に入れるかどうかが結構不安だった。でもそれは意外と何とかなってとても楽しい時間を過ごせたし、何より今回で競技プログラミングに対するモチベーションがだいぶ上がったので行けて本当によかったなあと思う。またオンサイトの機会があればぜひ行きたいし、行けるようにもっと頑張りたい。

こんなとこかな。次のオンサイトはいつだろう・・・。

競プロをやりはじめてから半年が経ちました

競技プログラミングを初めて、今日でちょうど半年です。(私が初めて使用したオンラインジャッジであるAtCoderの初AC日を、競プロ初日としています)

「競技プログラミングはじめたいけど、なにからやればいいのかな・・・」とか、「この大会の準備期間短いけど今から頑張ったら間に合うかな・・・」とか、その辺の疑問にお答えできたらいいなあと思い記事を書くことにしました！特に初心者のかたは参考にしてください(プロはこわいから見なくてもいいですよ ＞＜)

競プロ初心者がやるべきこと

入出力やSTL・簡単なアルゴリズムを勉強する

まず、プログラムが書ける状態までもっていかないと何も始まりません。まずは、図書館等で基本的なプログラミングの知識をつけましょう。標準入出力、for、while、if等使えるようになれば十分です。ポインタとかクラスとかは競技プログラミングではそんなに意識しなくてよいです(でもライブラリ作るときに必要になるかもしれないので勉強するに越したことはないです)

自分はそのへんどうだったかというと、競プロ始める前はCしか知らなかったためC++の記法を勉強するときはちょっと大変でした。とはいえ、毎日のようにプログラム書いてたらそのうち覚えるので頑張りましょう。ネットで検索したら初心者向けのスライドが転がってるので、そういうのも参考になりますよ。

アルゴリズムに関しては「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」(通称: TLE本)や「プログラミングコンテストチャレンジブック」(通称: 蟻本)が非常に参考になります。最初に読むならTLE本ですかね、蟻本は初級編からけっこう難しいので・・・。TLE本がわかってきたら蟻本を読む、という流れが良いと思います。

オンラインジャッジで修行

初めのうちはコンテストに出るよりも、出題形式や提出方法に慣れるために、またアルゴリズムを学ぶために、問題を解きまくるのが良いです。例えばAtCoderの場合なら、AtCoder Beginner ContestのA・B問題が簡単なのでまずはそこから埋めていきましょう。で、だんだん慣れてきたらCとかDとかに挑戦して・・・という感じですかね。自分のレベルに応じて問題を選んでいってくださいね。

出題形式はコンテスト出る前に把握したほうが良いです。特にTopCoderがちょっと特殊で、main関数に処理を書くのではなくクラスのメンバ関数に処理を書くことになります。一度やっておかないとコンパイルエラー頻発でコンテスト中悲しい思いをするので、事前にやっておくことをおすすめします。

コンテストに参加する

ある程度経験を積んだらコンテストに参加してみましょう。私はコンテスト出たいマンなのでやたら参加してますが(5/19に初めて5/28にはもうコンテスト出てました。せっかちすぎる)、自分のペースで参加しましょう。というのも、コンテスト終了後に復習しないと出た意味がほとんどなくなるので、復習が可能なレベルで出る必要があります。

コンテストはTopCoder、Codeforces、AtCoder等で行われています。AtCoderは日本語で行ってくれますが、ほかは英語ですね。最近Google翻訳が強くなったらしいので、英語に抵抗のある方も是非参加してみては・・・？

ライブラリを作る

上位を狙うなら必須です。上位行ったことない私が言うのもなんですが・・・。

ライブラリとは、「このアルゴリズム使いたいぞ！」となったときにすぐに使えるように、予め用意しておくものです。グラフ理論とか幾何でよく使いますね。

で、これを作ることによって解答速度が速くなって良いのは当たり前なんですが、それ以上に「そのアルゴリズムを自分の中で咀嚼できる」のが大きいと自分は思っています。意味を理解しつつライブラリを作っていくと、自分の中で考えが整理できてとても良いので、ちゃんと理解するという意味でもライブラリ作ったほうが良いです。

自分の話

いろいろ書きましたが、実際お前はどんな感じでやってきたねん、ということで振り返ってみます。

大学の競技プログラミングサークルに初めて見学に行った(5/19)。この日から競プロはじめました。AtCoderの問題を使ってバーチャルコンテストをしていたので、AtCoderはじめました。当時Cしか書けず文字列の問題で詰みまくっていたのでC++を勉強するとぞと心に誓う。その時はICPC出ないでおこうかなと思ってたけどなんだかんだで出ることにした。

ICPC国内予選に参加した(6/24)。競プロ歴まだ1ヶ月くらい。自分のチームは、他のメンバーも同じくらいの経験値だったけど3完した。正直これは運が良すぎただけ。だってまだC++に慣れてなさすぎて、setにある要素が入っているかどうかってなんの関数使えば分かるっけ？みたいなレベルだったので・・・。グラフや幾何、DPは全く歯が立たなかったので、これから頑張っていこうと思った。

ICPC後はTopCoderとかCodeforcesとか、やたらいろんなものに手を出した。Twitterのフォロワーが頑張ってるのを見ると触発されて自分も出ちゃうんだよねー。Twitterにいるプロがモチベーションの源でした。

夏休みからライブラリを整備し始めた。AOJにはverify時に大変お世話になりました。特に幾何のライブラリが潤って、ライブラリ使うだけ問題は対処できるようになった。しかし経験が足りない。

あとは、夏休み中に蟻本の初級中級はだいたい読んだ。でもまだフローがわからない、むずい。上級は未だに読めてないなあ、あかん。

9月10月、こどふぇすワンチャンあるかなと思って予選参加するも通らず。まあ、当たり前ですね。来年に向けて1年間精進するぞと思った。

11月、全く狙ってなかったけど DISCO presents ディスカバリーチャンネル コードコンテスト 2016 予選突破してしまった。正直行ってB3補正のおかげで通ったようなもんだけど、オンサイトのコンテストに行けるというのはやっぱり嬉しいですね。本戦が楽しみです・・・。

本戦とかがかかったコンテストで勝つには、最低でも半年は必要な気がしますね。相当センスある人だったらもう少し短くても行けるかもしれないけど、経験が物を言うところがやっぱり大きいですからね・・・。

というわけで、ざっくり言うとこんな感じで取り組んでました。もっといろんなコンテストで結果出せるようになりたいですね。

目標とか

さて、競プロ歴1年を迎える前に達成しておきたいことをまとめておきますかねー。

• レートあげたい

AtCoder、Codeforces、TopCoder全部そうなんだけど、青色になりたい。もう少しがんばれば到達しそうな雰囲気はあるから、このまま頑張っていきたい。

• ライブラリ充実させたい

ジャンルによってライブラリの充実度が違いすぎるので、どの分野も充実させたい。あとライブラリのバグ発見したい。

• 蟻本読み進めたい

もう難しいところしか残ってないし、なかなか読み進めるのが大変だけど、なんとか乗り越えたい。

こんなところですかね。次の半年間も実りあるものにしたいですね。精進します。

セキュリティ・ミニキャンプ in 北海道 2016 参加記

セキュリティ・ミニキャンプ in 北海道に参加しました。セキュリティ関係の勉強会は初めて行ったのでついていけるか不安でしたが、グループ議論や演習が充実していて私でも楽しめました。今後セキュリティ・ミニキャンプへの参加を考えている方の参考になればと思い記事を書くことにしました。とはいいつつもめっちゃ真面目に書くつもりはないのでフランクに書いてます。

0日目

このイベントの存在を知ったのは大学の講義中に教授が紹介してくれたのがきっかけ。セキュリティのセの字も知らない状態の私、せっかく近くでこういうのがあるなら行ってみようかなーということで、参加することにした。

その後セキュリティの講義で共通鍵とか公開鍵とか基礎的なことはやるものの、依然としてついていけるかどうか不安のまま・・・。(今思えば心配することなかった)

1日目

実はミニキャンプ当日の6時までラウワンオールしてて、そのあと5時間くらい寝て行きました()
人間がんばれば何とかなるものです。まあ、そんなことはさておき・・・

最初はセキュリティ・キャンプ全国大会の紹介。聞けば聞くほど魅力的な大会だなあと思った。もうちょっと知識つけて出たいなあ、予選は知識なくても通るチャンスはあるといえども、ちゃんと勉強したほうがより大会楽しめそう。セキュリティの資格取りに行くつもりで頑張ったら達成できるかなあ、とかいろいろ考えてた。

次は地域IoTの話。予算がない中でやりくりしなきゃいけないから大変らしい。安全な実装とか、メンテナンスとかどうすればいいかについてグループ議論したけど、取り上げている話題がそれなりに解決困難なのでいい答えは出ず。もっと頭良くなりたいと思った。

その次は演習。HTTP Request / Responseをいろいろいじくって、ムリゲー仕様の携帯ゲームを、脆弱性を突いてクリアしてしまおうというもの。いろいろ見てたら、敵からの攻撃を表すRequestを破棄すればダメージを受けないことが判明してクリア、自分がいたグループが一番早くできたので嬉しかった。でもこれは想定解ではなかったようで、講師側も悔しがっていた。というか想定解思いつかなかった・・・。やっぱり演習形式は、このアプリケーションの何がダメなのかとかが具体的にわかるから好き。

ここで夕食休憩。私からしたらいつもの学食だけど、やっぱり他の大学や高専の人にとっては新鮮なようで、学校の立地について話が弾んでいた 笑

最後は情報学に関する法律の話。自動運転に関する問題が出されて、それぞれの意見を言っていくんだけど、けっこう意見割れてた。どっちの意見もなるほどという感じで、考えされられた。

札幌市民だけど「ホテルが用意されているので泊まっていって！」、ということで、ありがたく宿を利用することに。その後DDPCに出るも2完で無事死亡。上に有資格者何人いるかしらんけどたぶん通らんだろうな・・・。(追記: 通った。ビックリ。本戦終わったらまた記事書きます)

2日目

ホテルで朝食を食べて会場へ。雪めっちゃ降っててつらかった。

朝はクラウドの講義。AWSちょっといじったことはあるけど詳しいことは何もわからないので新しい知識をたくさん得た。個人レベルでどうつかうかとかしか考えたことがなかったので、いちサービスとして提供する側に立った時に何を気をつけなければならないかについてはもう少し日頃から考えていかないとなあと思った。あとでメモ見返したい。

その後はRaspberry piを使った演習。高専生が強いのでサクサク進んだ(ありがとうございます)
あの小さい中にOSが入ってるなんてすごい。前に実験でArduinoを触ったことはあるけど、あれはOS入ってないのでなおさらびっくりした(まあ、ArduinoはOSが載ってない分ハードウェアをフルに使えるのがいいところなんだけどね)
頑張ったらいろいろできそうだし、もうちょい調べてみようかなあ・・・。

これで日程は無事終了。早かったなぁ。

まとめと雑感と

初めて参加したけどすごく楽しめました。来年も参加したいなあという気持ちになってる。

Markdown周りを整えていたおかげでメモがとてもとりやすかった。勉強会でるなら環境つくっておいたほうがいいかも。

あと、高専生つよい。大学よりもはるかにレベルが高そう(主観)なので、あぐらかいてられんなあと思った。

色々と刺激もらったので、これからに活かしていきたいなと思います！！内容のない記事でしたけど最後まで読んでくれてありがとうございました。