競技プログラミングの勉強会を開催している話

2018/09/21
このエントリーをはてなブックマークに追加

ソフトウェアエンジニアの尾崎です。今年の6月頃から趣味で競技プログラミングに取り組んでいます。最近はカブクオフィスの会議室を借りて競技プログラミングの勉強会を開催するようになったので今日は競技プログラミングの紹介と勉強会の宣伝をしようと思います。

TL;DR

  • 競技プログラミングはオンラインで気軽に参加できて楽しいです。
  • 競技プログラミングで培った知識や思考力は仕事で役に立つかもしれません。
  • カブクオフィスにて競技プログラミング初級者向けの勉強会を開催しています。

競技プログラミングのこと

まずは競技プログラミングについて簡単に紹介します。

概説

競技プログラミングは与えられた課題に対して参加者がプログラムの形で解答し

  • 解答プログラムを作成する速さ
  • 解答の計算量の少なさ
  • 解答の使用メモリの少なさ

など定量的な基準のもとで優劣を競うものです。

オンラインジャッジ

オンラインジャッジとは文字通りオンラインで解答をジャッジする仕組みで、競技プログラミングを支える重要な技術です。一定の正解が存在するタイプの問題であれば、開催者は入力と出力の組み合わせからなるテストケースをサーバ上に用意しておきます。そして、参加者がアップロードした解答プログラムが全てのテストケースを満たすかどうかを判定して成否を返します。このように解答プログラムの成否判定を自動化することで、大勢の参加者が同時に同じ課題に挑戦することが可能になっています。また、オンラインジャッジを提供しているサービスの多くは過去の問題もオンラインジャッジ可能な状態で公開しているので、過去問にも気軽に挑戦することができます。

面白い例題

競技プログラミングを説明する際によく用いられる面白い問題があるので紹介します。この問題は北京大学が運営しているPOJというオンラインジャッジサービスに掲載されています。競技プログラミングの参考書として有名なプログラミングコンテストチャレンジブック^1の冒頭にも掲載されています。

Ants^2 (以下問題文和訳)
長さL cmの水平な柱の上をn匹の蟻たちが秒間 1 cmの速度で歩いています。蟻は柱の終点に到達すると即座に落下します。また、2匹の蟻が出会うと彼らは即座に反転して歩き始めます。(この手の問題のお約束ですが蟻の大きさは考慮しません。)初期状態でのn匹の蟻の位置(柱の左端からの距離x[1], x[2], x[3]…x[n])が与えられますが、蟻がどちらに向かって歩いているかはわかりません。この条件で、全ての蟻が柱から落下するまでにかかる時間の最小値と最大値を求めてください。

問題のイメージ図

一見するとそれぞれの蟻が左を向いている場合、右を向いている場合の全ての組み合わせでの所要時間を計算して最小値と最大値を求めなければならないように見えます。こうすると蟻の数nに対して2^n通りの場合を検証しなければならないため計算に莫大な時間がかかってしまいます。しかし、あることに気づくととても簡単に問題を解くことができます。ぜひ解法を考えてみてください。(スクロールすると解説に続きます。)

















解説です。個々の蟻を識別する必要はないので、「蟻同士が出会って反転する」という挙動は「出会った蟻同士がそのまま真っ直ぐ進み続ける」という挙動に読み替えることができます。

解説のイメージ図

こうすれば簡単です。それぞれの蟻について右向きのときと左向きのときの落下するまでの時間を簡単に計算することができます。それぞれの蟻がより短い時間で落下する向きでの落下までの時間を計算して、その中の最大値を求めれば最小時間を得ることができます。同様にして最大時間も導出できます。擬似コードでは下記のようになります。

// 変数宣言
int n, L;
array<int> antPositions;

// 標準入力を受付(下記のような入力を想定)
// n, L
// x[1], x[2], x[3]...x[n]
input >> n;
input >> L;
repeat(n) {
  int x;
  input >> x;
  antPositions.push(x)
}

// それぞれの蟻について落下までの時間がより短(長)い向きの時間を導出して、その中の最大(小 )値を取得
int minTime = antPositions.map(position => min(position, L - position)).getMax();
int maxTime = antPositions.map(position => max(position, L - position)).getMin();

// 標準出力
output << minTime << endLine;
output << maxTime << endLine;

このように解法を閃けば簡単に解ける問題もあり、一方でアルゴリズムの知識を要求されるような問題もあります。競技プログラミングではいろいろな問題に挑戦しながら発想力を鍛え、アルゴリズムの知識を深めることができます。

はじめるには

競技プログラミングを始めるにはAtCoder^3というサービスがおすすめです。理由は国内のサービスでかつ参加者が多いこと、初学者向けのガイド^4が充実していること、初級者向け競技の開催があり参入障壁が低いことです。 AtCoderでは週末にオンライン参加型の競技が開催されていて、参加者は2時間前後の制限時間で4つから6つの問題に取り組みます。使用できる言語も多様で競技プログラミングの世界で定番のC++やJava, Pythonを始めとしてRustやGoといった新し目の言語でもコードを投稿することができます。

勉強会のこと

ここまでで競技プログラミングの概要を紹介したのでここからはカブクオフィスで開催している勉強会について紹介します。大前提として私自身が競技プログラミングを始めたばっかりの初級者なので初級者を対象にした勉強会を開催しています。

勉強会を開く理由

オンラインで参加できる競技プログラミングのオフライン勉強会を開いているのには理由があります。一つは、せっかく競技プログラミングという面白くて勉強になるコンテンツに取り組み始めたので私自身が長く続けてたいと考えていることです。オフラインのコミュニティを構築すればそれ自体が競技プログラミングのモチベーション向上に寄与すると考えています。もう一つの理由は、他の人のものの考え方を知りたいということです。アルゴリズムを勉強することと比べて問題文をアルゴリズムに落とし込んでいく能力を鍛えるのは少し難しそうです。勉強会では特に後者にフォーカスして解法にたどり着くプロセスを共有しながら問題を解いていきたいと考えています。

これまでの勉強会

これまでに勉強会を2回開催しています。^5

1回目

初回の勉強会は人づてに競技プログラマを集めて開催しました。また、取り組む問題のジャンルを組み合わせ問題に絞りました。最初に組み合わせ問題に頻出なアルゴリズムについて簡単な解説を実施し、事前に作成した擬似的なコンテストを解き進めていきました。結論から言うと主催側の勉強が不足していてアルゴリズムの解説に片手落ち感がありました。そのかわり参加者の積極的な意見交換が生まれて学べることは多かったです。問題を解き進めていく段階でも意見交換が活発でいろいろな問題の捉え方を知ることができました。ただ、疑似コンテストを小さく複数セットに区切ってしまったことが裏目に出て特定の問題の解法を思いついたかどうかで進度に大きな差が生まれてしまいました。ジャンルを固定することは良かったので問題点を改善しつつこの方針で次回も開催しようと考えました。

2回目

2回目の開催では参加者をWEBページから公募しました。その結果WEBやSNSを見て興味を持ってくださった競技プログラマが新規に2人参加してくれました。また、前回の反省を活かして初頭の解説を拡充し、時間いっぱいで一つの疑似コンテストを進めていく方針に切り替えました。結果は良好で、比較的ゆったりと一つの疑似コンテストに取り組んでいくことができました。問題点を上げるとすれば、2回目のジャンルとして指定したグラフ理論の問題は実装が難しいものが多く、前回よりも少し難易度が高かったです。

今後の予定

ある程度開催方針が固まったので今後も継続的に勉強会を開催していく予定です。月一ペースでおそらく土曜日のお昼頃から開催します。開催時はCompassのイベントページ[^5]から告知するので、興味がある方がいれば気軽にイベントメンバーに登録しておいていただけると嬉しいです。

おわりに

最後まで記事を読んでいただいてありがとうございます。競技プログラミングはオンラインで気軽に参加できるものなのでぜひ一度遊んでみてください。また、勉強会に興味を持ってくださった方がいらっしゃったら是非勉強会に遊びに来てください。カブクから飲料とお茶菓子の無償提供もあります。最後に、カブクでは趣味で競技プログラミングに取り組んでいるような知的好奇心旺盛なエンジニアを絶賛採用中なので是非ご応募ください。

その他の記事

Other Articles


TypeScript で “radian” と “degree” を間違えないようにする

2019/02/05
Python3でGoogle Cloud ML Engineをローカルで動作する方法

2019/01/18
SIGGRAPH Asia 2018 参加レポート

2019/01/08
お正月だョ!ECMAScript Proposal全員集合!!

2019/01/08
カブクエンジニア開発合宿に行ってきました 2018秋

2018/12/25
OpenAPI 3 ファーストな Web アプリケーション開発(環境編)

2018/12/23
いまMLKitカスタムモデル(TF Lite)は使えるのか

2018/12/21
[IoT] Docker on JetsonでMQTTを使ってCloud IoT Coreと通信する

2018/12/11
TypeScriptで実現する型安全な多言語対応(Angularを例に)

2018/12/05
GASでCompute Engineの時間に応じた自動停止/起動ツールを作成する 〜GASで簡単に好きなGoogle APIを叩く方法〜

2018/12/02
single quotes な Black を vendoring して packaging

2018/11/14
3次元データに2次元データの深層学習の技術(Inception V3, ResNet)を適用

2018/11/04
Node Knockout 2018 に参戦しました

2018/10/24
SIGGRAPH 2018参加レポート-後編(VR/AR)

2018/10/11
Angular 4アプリケーションをAngular 6に移行する

2018/10/05
SIGGRAPH 2018参加レポート-特別編(VR@50)

2018/10/03
Three.jsでVRしたい

2018/10/02
SIGGRAPH 2018参加レポート-前編

2018/09/27
ズーム可能なSVGを実装する方法の解説

2018/09/25
Kerasを用いた複数入力モデル精度向上のためのTips

2018/09/19
Ladder Netwoksによる半教師あり学習

2018/08/10
「Maker Faire Tokyo 2018」に出展しました

2018/08/02
Kerasを用いた複数時系列データを1つの深層学習モデルで学習させる方法

2018/07/26
Apollo GraphQLでWebサービスを開発してわかったこと

2018/07/19
【深層学習】時系列データに対する1次元畳み込み層の出力を可視化

2018/07/11
きたない requirements.txt から Pipenv への移行

2018/06/26
CSS Houdiniを味見する

2018/06/25
不確実性を考慮した時系列データ予測

2018/06/20
Google Colaboratory を自分のマシンで走らせる

2018/06/18
Go言語でWebAssembly

2018/06/15
カブクエンジニア開発合宿に行ってきました 2018春

2018/06/08
2018 年の tree shaking

2018/06/07
隠れマルコフモデル 入門

2018/05/30
DASKによる探索的データ分析(EDA)

2018/05/10
TensorFlowをソースからビルドする方法とその効果

2018/04/23
EGLとOpenGLを使用するコードのビルド方法〜libGLからlibOpenGLへ

2018/04/23
技術書典4にサークル参加してきました

2018/04/13
Python で Cura をバッチ実行するためには

2018/04/04
ARCoreで3Dプリント風エフェクトを実現する〜呪文による積層造形映像制作の舞台裏〜

2018/04/02
深層学習を用いた時系列データにおける異常検知

2018/04/01
音声ユーザーインターフェースを用いた新方式積層造形装置の提案

2018/03/31
Container builderでコンテナイメージをBuildしてSlackで結果を受け取る開発スタイルが捗る

2018/03/23
ngUpgrade を使って AngularJS から Angular に移行

2018/03/14
Three.jsのパフォーマンスTips

2018/02/14
C++17の新機能を試す〜その1「3次元版hypot」

2018/01/17
時系列データにおける異常検知

2018/01/11
異常検知の基礎

2018/01/09
three.ar.jsを使ったスマホAR入門

2017/12/17
Python OpenAPIライブラリ bravado-core の発展的な使い方

2017/12/15
WebAssembly(wat)を手書きする

2017/12/14
AngularJS を Angular に移行: ng-annotate 相当の機能を TypeScrpt ファイルに適用

2017/12/08
Android Thingsで4足ロボットを作る ~ Android ThingsとPCA9685でサーボ制御)

2017/12/06
Raspberry PIとDialogflow & Google Cloud Platformを利用した、3Dプリンターボット(仮)の開発 (概要編)

2017/11/20
カブクエンジニア開発合宿に行ってきました 2017秋

2017/10/19
Android Thingsを使って3Dプリント戦車を作ろう ① ハードウェア準備編

2017/10/13
第2回 魁!! GPUクラスタ on GKE ~PodからGPUを使う編~

2017/10/05
第1回 魁!! GPUクラスタ on GKE ~GPUクラスタ構築編~

2017/09/13
「Maker Faire Tokyo 2017」に出展しました。

2017/09/11
PyConJP2017に参加しました

2017/09/08
bravado-coreによるOpenAPIを利用したPythonアプリケーション開発

2017/08/23
OpenAPIのご紹介

2017/08/18
EuroPython2017で2名登壇しました。

2017/07/26
3DプリンターでLチカ

2017/07/03
Three.js r86で何が変わったのか

2017/06/21
3次元データへの深層学習の適用

2017/06/01
カブクエンジニア開発合宿に行ってきました 2017春

2017/05/08
Three.js r85で何が変わったのか

2017/04/10
GCPのGPUインスタンスでレンダリングを高速化

2017/02/07
Three.js r84で何が変わったのか

2017/01/27
Google App EngineのFlexible EnvironmentにTmpfsを導入する

2016/12/21
Three.js r83で何が変わったのか

2016/12/02
Three.jsでのクリッピング平面の利用

2016/11/08
Three.js r82で何が変わったのか

2016/12/17
SIGGRAPH 2016 レポート

2016/11/02
カブクエンジニア開発合宿に行ってきました 2016秋

2016/10/28
PyConJP2016 行きました

2016/10/17
EuroPython2016で登壇しました

2016/10/13
Angular 2.0.0ファイナルへのアップグレード

2016/10/04
Three.js r81で何が変わったのか

2016/09/14
カブクのエンジニアインターンシッププログラムについての詩

2016/09/05
カブクのエンジニアインターンとして3ヶ月でやった事 〜高橋知成の場合〜

2016/08/30
Three.js r80で何が変わったのか

2016/07/15
Three.js r79で何が変わったのか

2016/06/02
Vulkanを試してみた

2016/05/20
MakerGoの作り方

2016/05/08
TensorFlow on DockerでGPUを使えるようにする方法

2016/04/27
Blenderの3DデータをMinecraftに送りこむ

2016/04/20
Tensorflowを使ったDeep LearningにおけるGPU性能調査

→
←

関連職種

Recruit

サーバーサイドエンジニア(Python/Go)

業務内容

カブク自社で開発・運営しているWebサービス(3Dプリンターなどを活用したデジタル製造サービス)のサーバサイド開発。WebサービスのバックエンドやAPIの設計・実装をお任せします。

フロントエンドエンジニア(TypeScript)

業務内容

自社で開発・運営しているWebサービス(3Dプリンターなどを活用したデジタル製造サービス)のフロントエンドの設計や実装をお任せします。 また、新規サービス開発プロジェクトへも参画いただけます。

機械学習エンジニア

業務内容

機械学習を用いた3Dデータや2Dデータからの情報抽出モデルの構築やセンサーデータの分析モデルの調査・研究・開発。 PoCだけでなく、データの前処理や学習、ハイパーパラメータチューニング、獲得モデルの評価、適用、運用のパイプライン構築まで、機械学習をプロダクション適用する全てのお仕事に携われます。

インターン(エンジニア)

業務内容

カブクの社員と肩を並べて、実業務を中心とした知識やスキルを身につけていただく実践型インターンシップ。スタートアップならではのスピードがあり、ダイナミックな就業経験を体験することが可能です。

→
←

お客様のご要望に「Kabuku」はお応えいたします。
ぜひお気軽にご相談ください。

お電話でも受け付けております
03-6380-2750
営業時間:09:30~18:00
※土日祝は除く