リクルートコミュニケーションズ (RCO) におけるプログラミングコンテストの活用について
この記事は Recruit Engineers Advent Calendar 2016 の3日目の記事です。
RCO プロコン部
RCO アドテク部には、プロコン部、Kaggle 部、SET (Sushi is Everything) などのサークルがあります。プロコン部は気ままにプログラミングコンテスト(プロコン)に参加するサークル、Kaggle 部は気ままに機械学習コンペの Kaggle に参加するサークルで、SET は寿司を食べているようです。
そもそもプロコンとは
「プログラミングのコンテスト」というと範囲が広くなりますが、ここでは、「与えられたプログラミングの問題を、制限時間内に早く正確に解くコンテスト」のことを指します。2時間程度で4問ほど出題されることが多いです。様々なコンテストサービスがあり、以下のサービスを利用することが多いです。
どんな人が参加しているの?
プロコン部と名乗って入るものの、何か決まったメンバーのサークルがあるわけではなく、コンテストになると集まってくる感じです。
よくいるメンバーとしては uwi さん、shiratty8 さん、KenjiH さん、dpforest さん、iehn さん、kenkoooo などがいますが、それ以外の人たちもたまに来たりします。機械学習エンジニアよりもアプリケーション開発エンジニアの方がよく参加している印象です。
日々の活動
プロコン部の日々の活動としては以下のようなものが挙げられます。
- 社内チャットの「プロコン部ルーム」に溜まる
- コンテストに参加する
- 社内 wiki に自分が解いた問題の解説記事を投稿する
- アルゴリズムイントロダクションを輪読する
これらの活動について書いていきます。
社内チャットの「プロコン部ルーム」に溜まる
参加したコンテストの問題の感想や、好きなデータ構造について話したりします。分からない問題などについても聞けたりします。
コンテストに参加する
業務時間中にコンテストがある場合、勉強会としてみんなで集まってコンテストに参加します。TopCoder SRM や HackerRank HourRank などは1〜2時間程度で終わるので、その後1時間ほど問題について議論する時間を設けます。その日に競技プログラミングを始めた人から世界トップクラスの人まで様々なレベルの人が集まるので、解法を議論したり、時間内に通らなかったコードをレビューしたり、別解を検討したりします。
プロコン部ご飯 pic.twitter.com/Ag7azgiAz9
— 宇宙ツイッタラーX (@kenkoooo) October 13, 2016
3時間の長丁場になるので、会社から弁当が支給されます。予算は1人1500円までで、ネット注文しておくこともあれば、八重洲が近いので東京駅まで駅弁を買い出しに行くこともあります。
このように、弁当で体力をつなぎつつ、コンテストを題材にした内容の濃い勉強会を行っています。
社内 wiki に自分が解いた問題の解説記事を投稿する
自分が解いた問題についてチャットで感想を言うこともありますが、内容を残しておきたい問題などについては社内の wiki に投稿することもあります。
アルゴリズムイントロダクションを輪読する
アルゴリズムイントロダクションを読む会が行われています*2。この本は、アルゴリズムの正当性や計算量の上界の証明が丁寧に書かれている教科書で、「プログラミングコンテストチャレンジブック(蟻本)」などと違ってプロコンに直接役立つ本ではありませんが、計算量の議論などはプロコン慣れしている方がやはり分かりやすく、参加者はプロコン勢がほとんどです。
進め方としては、毎週1人担当者を決め、発表者が好きな章を選んで発表しています。最近は、重たい章だけが残ってきたので、何回かに分けて発表します。
※僕が最大フローの章を担当した時の資料
業務の役に立つのか
このように RCO ではプログラミングコンテストを仕事に取り入れていますが、業務では役に立つのでしょうか。
実装が速くなる
個人的な感覚ですが、競プロ勢は実際の業務での実装スピードがかなり速いように感じます。もちろん設計などはまた別の問題で、素早く実装したコードが必ずしも優れた実装であるとは限りませんが、少なくとも自分の知る範囲では、他の人が5営業日かかる実装をプロコン勢は1日や2日で終わらせてしまうような気がします。
これにはいくつか要因が考えられますが、以下のような感じでしょうか。
- プロコンで何度もバグを埋め込んだおかげで、自分がバグを埋めやすい箇所などを把握しているため、バグに振り回される時間が短い。
- プロコンで何度も調べたおかげで、標準ライブラリや言語仕様の知識が蓄積していて、調べる回数が少なくて済む。
- プロコンでできるだけ共通化して記述量を減らすコツが蓄積していて、記述量が少なくて済む。
- プロコン用に設定やスニペットをゴリゴリに積んだ IDE を使っているのでスピードが出る。*3
プロコン特有のものではなく、単に四六時中プログラミングしていると身につくようなことばかりですね。ただ、プロコンでは特にまっさらな状態から実装するため、できるだけ速く少なく正確に実装する訓練が詰めるのかもしれません。
より強くなってくると、実装を始める前に頭のなかでコーディングを終えてしまうらしいので、さらに速くなるのかもしれません。早くその境地に達したいですね。
計算量の大まかな感覚がつかめる
プロコンで出題される問題の多くは「データのサイズが小さければ簡単に解ける問題」であることが多いです。
例えば、次のスライドに出てくる問題を見てみましょう。
スライドの中で、この問題は N=10 程度まであれば簡単に解けるが、N=1000などは発想を変えなければならないという話をしています。
実際の業務の中で、例えば最大フローや動的計画法などのアルゴリズムを駆使して計算を高速化する場面は多くはありませんが、計算量の感覚というのは重要だと思います。特にRCOアドテク部ではリアルタイム処理を行うことがあり、そういった分野では計算量の感覚は不可欠です。
コンピュータがざっくり1秒間に10億回くらい計算できると考えて、サービスに対して秒間10万のクエリが来るとき、1クエリあたり1万回くらいの計算ならできそうということが分かります。3億件のユーザーデータを抱えているので、ユーザー数を N とするとユーザー検索は O(log N) で終わらせる必要がありますね。
この「コンピュータが1秒間に計算できる回数」、「各操作にかかる計算回数」の感覚は非常に重要で、これがチーム内で共有されていることで「この関数は毎秒10万回呼ばれるから中の操作はこのくらいにしないと」「この関数は毎秒1000回しか呼ばれないから、計算量は少し悪くても可読性を優先しよう」などを考えることができます。
おわりに
プロコンは単純にゲームとして非常に面白いと思いますが、同時にプログラマの実装力を高めるかもしれません。色んな会社にプロコンを業務として取り入れる動きが広まってほしいですね。
いつの日か、ACM-ICPC のように会社対抗プログラミングコンテストが開催されるのを楽しみにしています。