みなさんは何のためにプログラミングをしていますか？
仕事のため、何かをつくるため。
それも良いけれど、「強くなる」ためにプログラミングしてみませんか。
様々なジャンルのプログラミングコンテストとまだ見ぬライバルたちがあなたを待っています。
今回はアルゴリズム/AI/機械学習/セキュリティ等の様々なジャンルのコンテストとその始め方について紹介したいと思います。
※これはPyConJPでの発表を文字におこしたものです。が、Pythonの話は殆どないです。
- プログラミングコンテストとは？
- すべてのコンテストに共通する、「コンテストに参加する利点」
- アルゴリズムのコンテスト
- ゲームAIコンテスト
- データマイニングのコンテスト
- サーバ/インフラのコンテスト
- セキュリティに関するコンテスト
- 伝えたいこと
- さいごに
- 元の発表資料
- 解答例
プログラミングコンテストとは？
プログラミングコンテストは、ひとことで言うと、
みんなで同じ問題を解いて
解くスピードや、スコアを競いあって
青春するイベント！
です。
プログラミングコンテストといっても、様々なコンテストがあります。
今回はここにある5つのジャンルのコンテストと、そのはじめ方について、
少しずつ紹介したいと思います。
これらのジャンルのコンテストのうち、
参加資格に制限のないコンテスト*1を紹介していきたいと思います。
すべてのコンテストに共通する、「コンテストに参加する利点」
1. 自分と同じ問題を解いた、他の人の解法を知ることができる
プログラミングのコンテストは、
基本的に、みんなで同じ問題に取り組みます。
そして、だいたいのコンテストでは、
参加者のコードが終了後に公開されたり、ブログで解法が紹介されます。
業務では、なかなかみんなで同じコードを書くことがないため、
自分の書いたコードが唯一の正解となってしまうと思います。
しかし、コンテストで同じ目的を持った、他の人と自分のコードや解法を比較することによって、自分の欠点だったり、より良い解決方法がわかることが多々あります。
2. 同じコンテストに出ていた、たくさんのライバルと知り合える
もうひとつ、大事な利点は、同じようなことを仕事にしている/勉強している仲間が見つかることです。
勉強会やコミュニティに参加したりしていると、同じ分野を勉強している人に出会うことができますが、コンテストでも同じです。スコアやランキングという明確な数値で殴り合うたライバルたちとは、強いきずなが生まれます。（多分！）
アルゴリズムのコンテスト
アルゴリズムのコンテスト、どんなことをするのか想像つかない人も多いと思うので、問題を見てみましょう
問題1
3つの辺を、a,b,cとすると、
こんな感じに仲間はずれを返してあげればいいですね。
def edge_length(a, b, c): if a == b: return c elif a == c: return b return a
難しくないですね。でもこれも立派なコンテストの問題です。
数学が得意な人はこんなふうにかいてもいいかもしれません。
def edge_length(a, b, c): return a ^ b ^ c
もう少し、難しい問題を見てみましょう。
問題2
だいぶ数学っぽくなってしまう問題ですが、
n段を下りる方法 = 1段おりて(n-1)段 + 2段おりて(n-2)段 + 3段おりて(n-3)段
という感じになるので、これをそのままコードにしてみます。
def step(n): if n == 0: return 1 if n < 0: return 0 return step(n - 1) + step(n - 2) + step(n - 3)
こんな感じになりました。マニアックなかんじになってきましたね。
さて、このコードで問題は解けるでしょうか？
答えはバツです。これでは正解にはなりません。
なぜなら、0 < N < 10^5 という制約があるためです。
以下の二点について考えてみましょう。
「計算量」についてはこの辺が参考になると思います。
アルゴリズム - [初心者向け] プログラムの計算量を求める方法 - Qiita
解答例は1番下に用意しました。
こちらの2問目の問題は数学っぽさがあって、「自分には無理」って思う人も多いと思います。
でもこれを解けるようになるのがアルゴリズムコンテストであって、最初から解ける必要はまったくありません。
それではさっそく、アルゴリズムのコンテストを３つ紹介します。
TopCoder Single Round Match
ひとつめは、アルゴリズムコンテストの王道TopCoder、Single Round Match.
次回開催：11/18(月) 25:00~
TopCoderについては聞いたことが有る方も多いかもしれません。
TopCoderには幾つものジャンルのコンテストがあって、その中でアルゴリズムに特化したのが、
通称するめと呼ばれているSingle Round Matchです。
75分で3問の問題が与えられます。
その後15分、他人のコードを読んで、
間違ってそうなプログラムを撃墜するフェーズ（バグ探し）があります。
撃墜すると結構得点がもらえます。
問題を解いても、終了時まであってるかどうかがわからない。他人に落とされるかもしれない！！ドキドキ度ナンバー1のアルゴリズムコンテストです。
早くたくさん解けば、高い得点が得られます。自分の得点から順位が計算され、順位に応じて参加者のレーティングが更新されます。
このSRMレーティング ＝競技プログラマー（コンテストをやってる人）の格みたいなところがあります。
レーティングに応じて、コンテスタントはグレーコーダー、グリーンコーダー、ブルーコーダ、イエローコーダ、レッドコーダーと呼ばれます。
アルゴリズムのコンテストをやってる人には、「はじめましての」の挨拶代わりに「おまえ何色？」って聞くこともあります。（ちょっと盛った）
週1くらいで開催されており、 毎回参加者は1000人程度です。
CodeForces
次回開催： 11/15 25:35~
CodeForcesは、今１番勢いのある競技プログラミングコンテスト！
毎週開催されてるのに毎回参加者は6000人~8000人ほど・・・！
問題が多いので、一問解けなくても、気にせず次の問題にいけるのが良いところです。
また、レーティングが上下しやすく一度落ちてもすぐに取り戻せるので、気軽に参加できます。
AtCoder
次回開催： 11/21(土) 21:00 ~ 23:00
AtCoderは日本のアルゴリズムコンテスト！終了後には解説がニコニコ生放送で見れるのが嬉しいです。初心者向けのABC, 一般向けのARCがあります。だいたい毎週どちらかのコンテストが開催されています。
AtCoderの社長の@chokudaiさんをフォローすると、コンテスト情報が手に入ります。
3つのコンテストの比較
下半分の、1,2…と数字は、1が1番簡単な問題、2が2番目に簡単な問題、という様な見方になっています。下にいけばいくほど、難しい問題です。
難易度は感覚で && 難しい問題はとけないのでなんとなくでつけてますが、よかったら参考にしてください。
これ以外にも、年に一度など、イベント開催されるコンテストが多数あります。
その他 おすすめイベント型アルゴリズムコンテスト
ICFPC
1年に一度、エンジニアが集まってコンパイラ書いたり、(」・ω・)」うー！(／・ω・)／にゃー！したりする、お祭りです。
3日間でグループを組んでやるコンテストで、エンジニア総合力が試されます。
ICFPC 2015 おつかれさまでしたー - Togetterまとめ
ICFP Programming Contest 2015 優勝 - iwiwiの日記
Google Code Jam
私の知る限りで参加者が最多(n万人)のコンテストです。
アルゴリズムコンテストのおすすめ勉強方法
1. AtCoderのABCに出る
2. １度出てみて、難しいと感じたらABCの過去問を数回分解いてみる
3. CodeForces/TopCoderに出る
4. 慣れてきて、もう少し強くなりたいと思ったら、アルゴリズムを学ぶために本を読む！！！
アルゴリズムコンテストのオススメ本
アルゴリズムコンテストをはじめたばかりの人にはこちらがおすすめ。
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
- 作者: 渡部有隆,Ozy(協力),秋葉拓哉(協力)
- 出版社/メーカー: マイナビ
- 発売日: 2015/01/30
- メディア: 単行本（ソフトカバー）
- この商品を含むブログ (5件) を見る
もっともっと強くなりたい人にはこれがおすすめ！（アルゴリズムコンテストのバイブルだぞ！）
プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?
- 作者: 秋葉拓哉,岩田陽一,北川宜稔
- 出版社/メーカー: マイナビ
- 発売日: 2012/01/28
- メディア: 単行本（ソフトカバー）
- 購入: 25人 クリック: 473回
- この商品を含むブログ (36件) を見る
ゲームAIコンテスト
次はゲームのAIコンテストです。対戦ゲームで、強いAIを作るコンテスト。
1~2週間のコンテストが多く、気軽に始められるので、社会人の娯楽にピッタリ。
文字ではなかなか表せないので、まずはどんなコンテストがあるのか動画を見てみましょう。
こちらは実際に最近あったコンテストのゲームです。
これは塗り返し ができないスプラトゥーンみたいなゲームで、マスを自分の色に染めるゲームです。
更にマスを8方向囲うと塗りつぶせます。たくさん塗り潰したら勝ちです。ルールは単純ですね。
codingame
先ほどの動画のコンテストが開催されてたのが、codingameです。
月に1回程度、1日から1週間とかのコンテストを開催しています。
他人と戦っているところがビジュアライズされるので、ゲームAIを書くというよりも、ゲームをしてる！という感じで遊べます。
データマイニングのコンテスト
Kaggle: The Home of Data Science
データマイニングといえばKaggle.
Kaggleはデータマイニングの精度の良さを競うのですが、
コンテストというよりも、どちらかといえば外注を請け負ったと考えて参加するのがよいかもしれません。
たくさんの企業が、解いて欲しい問題を提供しています。
「外注」なだけあって、上位入賞者の賞金は高いです。
賞金総額が10万ドル、なんてこと珍しくありません。
常時10個程度のコンテストが開催されています。
賞金なしの、楽しむためのコンテストも準備されています。
開催期間は数ヶ月の物が多いです。
Kaggleのはじめかた
機械学習系のコンテストについては、勉強法を語れるほど私自身が参加していないため、
参考にさせていただいたサイトを紹介させていただきます。
PyData.Tokyo Tutorial & Hackathon #1
サーバ/インフラのコンテスト
サーバインフラと分類してみましたが、紹介するのは、ISUCONと呼ばれる、
ウェブサービスを高速化するコンテストです。
ISUCON
ISUCONでは、1台もしくは複数台のサービスが動いているマシンを与えられ、一定時間に1番多くのリクエストを捌いたチームの勝ち！
具体的には、ミドルウェアの設定/データベースの高速化などを行っていきます。
Web業界の猛者たちが集まります。
年に1度開催されており、今年は既に予選が終了してしまいました。
出たことがない方は是非来年挑戦してみてください。
ISUCON勉強法
まずは過去問を解いてみましょう。
ISUCONの公式サイト過去のコンテストのAWS/GCEのマシンイメージが公開されています。
また、エントリを書くのがISUCON恒例のイベントになっており、
今年の予選には約300組が参加し、約100の参加エントリが投稿されています。
参加者のつまづいたところや解決方法を参考にしながらまた過去問を解いてみましょう。
ISUCONのお勉強につかった本
参加者のブログを見ればありがたいお話がたくさんあるはずですが、
インフラド素人からISUCONに参加するようになるまでの間に読んだ本です。（今でもど素人）
[Web開発者のための]大規模サービス技術入門 ―データ構造、メモリ、OS、DB、サーバ/インフラ (WEB+DB PRESS plusシリーズ)
- 作者: 伊藤直也,田中慎司
- 出版社/メーカー: 技術評論社
- 発売日: 2010/07/07
- メディア: 単行本（ソフトカバー）
- 購入: 80人 クリック: 1,849回
- この商品を含むブログ (132件) を見る
[24時間365日] サーバ/インフラを支える技術 ?スケーラビリティ、ハイパフォーマンス、省力運用 (WEB+DB PRESS plusシリーズ)
- 作者: 安井真伸,横川和哉,ひろせまさあき,伊藤直也,田中慎司,勝見祐己
- 出版社/メーカー: 技術評論社
- 発売日: 2008/08/07
- メディア: 単行本（ソフトカバー）
- 購入: 133人 クリック: 2,270回
- この商品を含むブログ (289件) を見る
- 作者: Baron Schwartz,Peter Zaitsev,Vadim Tkachenko,菊池研自,株式会社クイープ
- 出版社/メーカー: オライリージャパン
- 発売日: 2013/11/25
- メディア: 大型本
- この商品を含むブログ (7件) を見る
セキュリティに関するコンテスト
セキュリティのコンテストには、CTF(Capture The Flag)呼ばれるコンテスト群があります。
CTFには主にクイズ形式と攻防戦方式の２つの形式のコンテストがあります。
SECCONに関しては、私は予選にちょっと出たことが有るくらいで、ほとんど経験がないため、参考になりそうなページをまず置いておきます。
www.slideshare.netSECCON
日本でCTFで有名なのはSECCONです。
12/5~6にオンライン予選が開催されます。
かなり問題数も多く、１人で解くのは無理なので、いろんな分野が得意人をあつめてグループで参加しましょう。
exeファイルがおちてきたりするのでWindows環境もあったほうがいい気がします。
攻撃をする側になることで、普段から気をつけなければならないことにも気がつけるようになるかもしれないです。
CTFは私の中で今から勉強したいコンテストNo1です。勉強するぞ！
CTF勉強方法
クイズ形式のCTFについては、以下で問題演習ができます。
まずはここで演習をするところからはじめましょう。ksnctf.sweetduet.info
また、最近CTFに関する本も出ました！
セキュリティコンテストチャレンジブック -CTFで学ぼう! 情報を守るための戦い方-
- 作者: 碓井利宣,竹迫良範,廣田一貴,保要隆明,前田優人,美濃圭佑,三村聡志,八木橋優,SECCON実行委員会
- 出版社/メーカー: マイナビ出版
- 発売日: 2015/09/30
- メディア: 単行本（ソフトカバー）
- この商品を含むブログを見る
これから始める人に参考になりそうなスライドも紹介しておきます。
www.slideshare.net伝えたいこと
さいごに
スライドのほうがだいぶ伸びてたので、
あらためてブログ書かなくてもいいかな…と思ったけど、
スライドだけだと伝えきれないことも多いので、書き上げました。
とはいっても最初はやる気にあふれてたので頑張って書いていたのですが、
最後の方はだいぶ適当になってしましました(_ _)
どのコンテストでもまだまだ初心者な私の紹介ですが、
今までコンテストに参加したことない人が参加してみるきっかけに、
普段からコンテストをやっている人がちがうコンテストにも参加してみるきっかけに、なったら良いなと思います。
間違っている部分等ありましたら是非コメントをください。
解答例
def step(n): steps = [0 for i in xrange(n + 1)] steps[1] = 1 steps[2] = 2 for i in xrange(3, n + 1): steps[i] = steps[i - 1] + steps[i - 2] + steps[i - 3] return steps[n] % 1000000007 print step(99999)
*1:アイディアを競うようなコンテスト、イベントについては紹介しません。