強くなるためのプログラミング -様々なプログラミングコンテストとそのはじめ方-

みなさんは何のためにプログラミングをしていますか？
仕事のため、何かをつくるため。

それも良いけれど、「強くなる」ためにプログラミングしてみませんか。
様々なジャンルのプログラミングコンテストとまだ見ぬライバルたちがあなたを待っています。
今回はアルゴリズム/AI/機械学習/セキュリティ等の様々なジャンルのコンテストとその始め方について紹介したいと思います。

※これはPyConJPでの発表を文字におこしたものです。が、Pythonの話は殆どないです。

プログラミングコンテストとは？

プログラミングコンテストは、ひとことで言うと、

みんなで同じ問題を解いて
解くスピードや、スコアを競いあって
青春するイベント！

です。
プログラミングコンテストといっても、様々なコンテストがあります。

今回はここにある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 という制約があるためです。

以下の二点について考えてみましょう。

• 計算時間を見積もってみよう!
• デフォルトのPythonの再帰回数の限界を調べてみよう！

「計算量」についてはこの辺が参考になると思います。
[初心者向け] プログラムの計算量を求める方法 - 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の日記

https://code.google.com/codejam

私の知る限りで参加者が最多(n万人)のコンテストです。

アルゴリズムコンテストのおすすめ勉強方法

1. AtCoderのABCに出る
2. １度出てみて、難しいと感じたらABCの過去問を数回分解いてみる
3. CodeForces/TopCoderに出る
4. 慣れてきて、もう少し強くなりたいと思ったら、アルゴリズムを学ぶために本を読む！！！

アルゴリズムコンテストのオススメ本

アルゴリズムコンテストをはじめたばかりの人にはこちらがおすすめ。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

もっともっと強くなりたい人にはこれがおすすめ！（アルゴリズムコンテストのバイブルだぞ！）

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

アルゴリズムコンテストの探し方

コンテストがいつあるかは、TopCoder部のカレンダーで確認しましょう。
Googleカレンダーと同期するのがおすすめです。

はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知

ゲームAIコンテスト

次はゲームのAIコンテストです。対戦ゲームで、強いAIを作るコンテスト。
1~2週間のコンテストが多く、気軽に始められるので、社会人の娯楽にピッタリ。

文字ではなかなか表せないので、まずはどんなコンテストがあるのか動画を見てみましょう。

こちらは実際に最近あったコンテストのゲームです。
これは塗り返し ができないスプラトゥーンみたいなゲームで、マスを自分の色に染めるゲームです。
更にマスを8方向囲うと塗りつぶせます。たくさん塗り潰したら勝ちです。ルールは単純ですね。

codingame

先ほどの動画のコンテストが開催されてたのが、codingameです。

月に1回程度、1日から1週間とかのコンテストを開催しています。
他人と戦っているところがビジュアライズされるので、ゲームAIを書くというよりも、ゲームをしてる！という感じで遊べます。

CODE VS

CODE VSは、去年から社会人参加okになったAIのコンテスト。現在は前回と前々回の問題がプレイできます。
本選がニコファーレで開催されるため、ニコニコ生放送デビューできます。
開催期間は1ヶ月、年に一度（今までに5回）開催されていますが、次回コンテストは未定です。

こちらは一昨年のコンテストの様子です。

ちなみに、社会人参加がoｋになった去年ですが、
多くの大学院生・社会人が本戦に出場する中、優勝者は中学3年生の男の子でした！

ゲームAIコンテストの勉強方法

私はゲームAIは強くないので、参考になるかはわかりませんが、おすすめの勉強法はこんな感じです。

1. アルゴリズムコンテストでアルゴリズムの基礎を学ぶ
2. 自己流アルゴリズムでCodingameに出てみる
3. ゲームAIでよく使うアルゴリズムを学ぶ
4. 強い人のアルゴリズムを、コードを見ながら学ぶ

つぎ、ちょっと専門知識がいるコンテストを紹介していきます。

データマイニングのコンテスト

Kaggle: Your Machine Learning and Data Science Community

データマイニングといえばKaggle.

Kaggleはデータマイニングの精度の良さを競うのですが、
コンテストというよりも、どちらかといえば外注を請け負ったと考えて参加するのがよいかもしれません。

たくさんの企業が、解いて欲しい問題を提供しています。

「外注」なだけあって、上位入賞者の賞金は高いです。
賞金総額が10万ドル、なんてこと珍しくありません。

常時10個程度のコンテストが開催されています。
賞金なしの、楽しむためのコンテストも準備されています。

開催期間は数ヶ月の物が多いです。

Kaggleのはじめかた

機械学習系のコンテストについては、勉強法を語れるほど私自身が参加していないため、
参考にさせていただいたサイトを紹介させていただきます。
PyData.Tokyo Tutorial & Hackathon #1

サーバ/インフラのコンテスト

サーバインフラと分類してみましたが、紹介するのは、ISUCONと呼ばれる、
ウェブサービスを高速化するコンテストです。

ISUCON

ISUCONでは、1台もしくは複数台のサービスが動いているマシンを与えられ、一定時間に1番多くのリクエストを捌いたチームの勝ち！
具体的には、ミドルウェアの設定/データベースの高速化などを行っていきます。
Web業界の猛者たちが集まります。

年に1度開催されており、今年のコンテストは既に終了してしまいました。
出たことがない方は是非来年挑戦してみてください。

ISUCON勉強法

まずは過去問を解いてみましょう。
ISUCONの公式サイト過去のコンテストのAWS/GCEのマシンイメージが公開されています。

また、エントリを書くのがISUCON恒例のイベントになっており、
今年の予選には約300組が参加し、約100の参加エントリが投稿されています。
参加者のつまづいたところや解決方法を参考にしながらまた過去問を解いてみましょう。

【更新終了】ISUCON5 オンライン予選 関連エントリまとめ : ISUCON公式Blog
http://isucon.net/archives/45885523.html

ISUCONのお勉強につかった本

参加者のブログを見ればありがたいお話がたくさんあるはずですが、
インフラド素人からISUCONに参加するようになるまでの間に読んだ本です。（今でもど素人）

[Web開発者のための]大規模サービス技術入門 ―データ構造、メモリ、OS、DB、サーバ/インフラ (WEB+DB PRESS plusシリーズ)

[24時間365日] サーバ/インフラを支える技術 ‾スケーラビリティ、ハイパフォーマンス、省力運用 (WEB+DB PRESS plusシリーズ)

実践ハイパフォーマンスMySQL 第3版

セキュリティに関するコンテスト

セキュリティのコンテストには、CTF(Capture The Flag)呼ばれるコンテスト群があります。

CTFには主にクイズ形式と攻防戦方式の２つの形式のコンテストがあります。

SECCONに関しては、私は予選にちょっと出たことが有るくらいで、ほとんど経験がないため、参考になりそうなページをまず置いておきます。

CTFはとんでもないものを 盗んでいきました。私の時間です… from Hiromu Yakura

www.slideshare.net

SECCON

日本でCTFで有名なのはSECCONです。

12/5~6にオンライン予選が開催されます。

かなり問題数も多く、１人で解くのは無理なので、いろんな分野が得意人をあつめてグループで参加しましょう。
exeファイルがおちてきたりするのでWindows環境もあったほうがいい気がします。

攻撃をする側になることで、普段から気をつけなければならないことにも気がつけるようになるかもしれないです。
CTFは私の中で今から勉強したいコンテストNo1です。勉強するぞ！

CTF勉強方法

クイズ形式のCTFについては、以下で問題演習ができます。
まずはここで演習をするところからはじめましょう。
ksnctf.sweetduet.info

また、最近CTFに関する本も出ました！

セキュリティコンテストチャレンジブック -CTFで学ぼう! 情報を守るための戦い方-

でも予約してたのにまだ届いてない！！！！！！！！！！！！

これから始める人に参考になりそうなスライドも紹介しておきます。

Capture the flag! -タタカエ・セカイのために- from cocoa_dahlia

www.slideshare.net

伝えたいこと

さいごに

スライドのほうがだいぶ伸びてたので、
あらためてブログ書かなくてもいいかな…と思ったけど、
スライドだけだと伝えきれないことも多いので、書き上げました。

とはいっても最初はやる気にあふれてたので頑張って書いていたのですが、
最後の方はだいぶ適当になってしましました(_ _)

どのコンテストでもまだまだ初心者な私の紹介ですが、
今までコンテストに参加したことない人が参加してみるきっかけに、
普段からコンテストをやっている人がちがうコンテストにも参加してみるきっかけに、なったら良いなと思います。

間違っている部分等ありましたら是非コメントをください。

元の発表資料

強くなるためのプログラミング -プログラミングに関する様々なコンテストとそのはじめ方-#pyconjp from cocodrips

www.slideshare.net

解答例

def step(n):
    steps = [0 for i in xrange(n + 1)]
    steps[1] = 1
    steps[2] = 2
    steps[3] = 4
    for i in xrange(4, n + 1):
        steps[i] = steps[i - 1] + steps[i - 2] + steps[i - 3]
    return steps[n] % 1000000007
print step(99999)

※ バグがあったので直しました(_ _)

*1:アイディアを競うようなコンテスト、イベントについては紹介しません。