読者です 読者をやめる 読者になる 読者になる

ICPC (チームメンバー募集中)

ICPCとはACM国際大学対抗プログラミングコンテストのことです.
ACM国際大学対抗プログラミングコンテスト - Wikipedia
入学シーズンが近いというこでICPCを知ってもらうために書きました(裏のテーマとしてはチームメンバーの募集).内容は入門ということで少しクドいかもしれません.また,私自身(競技プログラミングが)強くないということでツッコミどころが多々あると思います.そのときは,教えてくださると助かります.

理系の大学生を対象とした(参加できる)コンテストにはいろいろあります.探していたらいろいろあったので下にリンクを貼ります.情報系でもセキュリティ,モノづくり,芸術系,AIなど多種に渡ります.なので,それぞれの個人にあったコンテストが見つかるはずです.これらのコンテストを足がかりに大学生活を広げていくのもありだと思います.
それでは本題に入っていきます.ICPCはコンテストという枠組みで言うと競技プログラミングに入ります.なので,初めに競技プログラミングとはどのようなことをするのかについて説明を行います.

「競技プログラミングとは?」

次のような問題が与えられたとします.解けるでしょうか?

[問題]
電太君は春から念願の大学生活をスタートします.ウキウキで上京しました.一人暮らしのために家を借りました.PCも買いました.後は入学式を待つだけです.
心配症の電太君は入学式前日に大学までの道をシミュレーションしました.そこで,重大な問題に気づきました.PCを買ったせいか現在120円しか持ってないのです.
下の図のような路線図が与えられます.電太君の家はA駅,大学はH駅の場所にあります.120円で家から大学までいけるでしょうか?
行けるならYesを,行けないならNoと答えてください.
ただし,電太君は歩くくらいなら大学に行かないという変なポリシーを持っているので近隣の駅まで歩いてということは考えません.
f:id:tatanaideyo:20140308180623p:plain

例えば,A→E→F→Hという経路の場合は40円+120円+200円で合計360円の運賃がかかります.なので,この経路では電太君は大学に行くことはできません.同様にすべての経路の運賃を計算すると,この問題では駅の数が8駅なので頑張れば手で計算できます.やることとしては,A駅からH駅まで最小の費用で行ける経路を見つけます.そして,その時の費用が120円以下ならばYes,120円より大きければNoと答えます.

手で計算できるならコンピュータを使う(プログラミングをする)必要がないのでは?と疑問に思うかもしれません.しかし,電太君だけではなく,電子さん,東工さん,ホク子さん・・・などたくさんの新入生が同じ問題で困っていてあなたに助けを求めてきたらどうしますか?それぞれの新入生が,運賃が書かれた路線図と家の駅,大学の駅の場所と現在所持している金額をあなたにメールしてきて答えを求められたらどうしますか?
手でやっていたら入学式が終わってしまいます.しかし,コンピュータを使えば現実的な時間で,すべての新入生に答えてあげることが出来ます.(全国の駅の数が約9,300駅,新入生の数が約605,000人なので数時間あれば大丈夫・・・なはず)

まとめると競技プログラミングとは上のような問題が次のような形式で数問与えられて,時間内にたくさん解こうというモチベーションで行われます.

  • 問題文(どのような問題を解くのか)
  • 入力形式(どのような入力が与えられるのか)
  • 出力形式(何を答えるのか)
  • 問題の制約(入力のサイズ,入力が与えられてから答えを出力するまでの制限時間,メモリ)
  • テストデータ(正しい答えなのかを検査するデータ)

入力のサイズの制約とは先ほどの問題で言うと,所持金がM円以下,新入生の人数がN人以下,駅の数がS駅以下などのことを言います.
先ほど,「コンピュータを使えば現実的な時間で,すべての新入生に答えてあげることが出来ます」と言いましたがコンピュータにも限界があります.人間が手でやるよりは大きな入力に対して問題を解くことが出来ます.しかし,入力のサイズを無限大に大きくすると現実的な時間で解くことはできなくなります.
先程から言っている「現実的な時間」とは,例えば2時間のコンテストで1つの問題の答えを出力するのに12時間かかるようでは「現実的な時間」で解けたとは言えません..何をもって「現実的な時間」というのかは時と場所,人によって多少異なってきますが上の例のようなニュアンスです.
この時間に関係するのですが,(競技)プログラミングではただ正しい答えを出力する解法を思いつくだけではいけません.正しい解法でも解法の種類によって,答えを出力する時間が1年や1日,数秒など異なってきます.この嘘のような本当の話は体験しないと分かりづらいと思いますが実際にその通りです.このように,制限時間内で終わるような解法を考えるのも競技プログラミングの面白さの1つになります.
例として,整列(ソート)問題に対する解法の違いによる実行時間の結果を載せます.整列問題とは次のように10個の要素が与えられたときに昇順または降順に整列し直す問題です.
f:id:tatanaideyo:20140310063103p:plain

横軸を要素の数N,縦軸を実行時間として,初期配列をランダムにしたときの結果をプロットしてます.解法の種類はマージソート(赤色),バブルソート(緑色),クイックソート(赤色)です.解法の違いによって実行時間が異なることが分かると思います.
f:id:tatanaideyo:20140310065125p:plain

この解法のことをアルゴリズムと呼びます.このような具体的な問題を解くために必要な部分だけを取り出して抽象化していくと,他の具体的な問題を抽象化した問題と同じという場合があります.これらの問題は研究が行われており,より実行速度が速いアルゴリズムが開発されています.
先ほどの問題は「単一始点最短路問題」として知られています.また,そのアルゴリズムとして,「ダイクストラ法」,「ベルマンフォード法」などがあります.これらの問題は現実的な問題の部分問題としてよく現れてきます.
競技プログラミングでは問題解決力を養うことができるので,他の現実的な問題を解くときに役に立つと思います.あと,単純に面白いです.是非競技プログラミングを・・・.

何だかんだでだいぶ長くなってしましました(反省).ICPCの説明に入ります.
ICPCでは先ほどの競技プログラミングをチーム戦で行います.
先ほどの電太君をモデルに話を進めていこうと思ったのですが,家から駅まで最小の費用は160円かかるので電太君は入学式に間に合わ・・・話を進めます.

第1フェーズ 「参加 - コミュ力 -」

同じ大学に所属する3人を1チームとして参加します.このとき,2人や1人のチームは参加出来ません.また,コーチが1人必要です.コーチは複数のチームのコーチになることができます.コーチは大学院生や教員です.
個人の参加資格や詳しい内容はその年のICPC国内予選のホームページでチェックしましょう.参考に2013 ICPC Aizuのホームページのリンクを貼っときます.
The 2013 ACM-ICPC Asia Aizu Regional Contest :: Registration page

このチームメンバーとコーチを探すのは大変な作業です.
大学によってはICPCの練習会などを開いているところがあります(一番下に探せたところだけリンクを貼っときます).その場合はコーチも個人で見つける必要はないことが多いと思います.他にサークルや研究室等が挙げられます.
また,参加登録期間が近づくと学内にICPCのポスターが貼られる場合があります.
ICPC ポスター - Google 検索
このポスターを掲載しているところに直に尋ねるのも1つの案です.(しかし,私の場合は4つほどたらい回しにされて結局誰も分からないという謎の現象がありました.)

第2フェーズ 「練習 - 国内予選突破に向けて -」

ICPCの流れは次の通りです.
f:id:tatanaideyo:20140309091643p:plain
毎年詳しい日程が変わるので必ずホームページをチェックしてください.国内予選はオンラインで行われます.そして成績の良かった数チームがアジア地区予選へのチケットを獲得できます.そして,アジア地区予選で成績の良かった数チームが世界大会に行くという流れになっています.
百聞は一見に如かずです.2013年のアジア地区予選と2012年ACM-ICPC世界大会の様子を見ると雰囲気がつかめると思います.下に動画を貼り付けます.


ICPC2013 Aizu 2 - YouTube


2013 ACM-ICPC World Finals Recap - All Teams - YouTube


国内予選までに何をすべきなのでしょうか.
まず,プログラミング言語を学ぶ必要があります.
ICPCで使えるプログラミング言語は次の3です.

まずは,1つプログラミング言語を習得してください.お勧めの学習方法としてはプログラミング言語の本で挫折しない程度の厚さの本を選び学習することです.この時,100%の理解度よりはなんとなく分かったという感覚で良いと思います.そして,競技プログラミングの学習に入ります.それから,プログラミング言語について分からないところを逐次調べたり,詳しい本を読むというように肉付けを行うのが良いと思います(人によるので自分の学習スタイルをみつけてください).

プログラミング言語を習得したら次に問題を解いていきます.
AIZU ONLINE JUDGE: Programming Challengeに過去のICPCの問題があります.また,AOJ-ICPCにAOJと連携してICPCの問題に難易度をつけたサイトなどがあります.たぶんプログラミング言語を習得してすぐトライすると難しく感じる思います.難しいと感じた場合はAOJのVolume100の問題から始めるのが良いと思います.

競技プログラミングの入門としては次のスライドが良いと思います.
実践・最強最速のアルゴリズム勉強会 第一回 講義資料(ワークスアプリケーションズ & AtCoder)
また,この方が書いている本もお勧めです.

ある程度,シミュレーションや全探索の問題が解けるようになったら次の本がお勧めです.「ダイクストラ法」などのいろいろなアルゴリズムの説明が書いてあります.競技プログラミングのバイブル的な本です.
プログラミングコンテストチャレンジブック [第2版] ?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

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


他にも力をつけていくときに役に立つ本やサイトなどたくさんありますが,すべてを書くと長くなるので省略します.あとは,チームメンバーとコーチを見つけて,参加登録を忘れずに国内予選に参加するだけです.長くなりましたが読んでくださって有難うございました.
電気通信大学の方で2014年度一緒に出てくれるかた募集です.