ACM国際大学対抗プログラミングコンテスト

ACM国際大学対抗プログラミングコンテスト (ACM International Collegiate Programming Contest、略称:ACM-ICPCまたは単にICPC) は、コンピュータープログラミングにおける勝ち抜き型のコンテストである。世界中の大学を対象として毎年開催されている。このコンテストはIBMにスポンサーとして協力を受けている。Executive DirectorのWilliam B. Poucher (大会本部であるベイラー大学に教授として在籍) のもと、ACMの後援によって六大州の各地で自律的に運営が行われている。

歴史

ACM国際大学対抗プログラミングコンテスト (ICPC) は1970年にテキサスA&M大学で開催されたコンテストがその始まりである。この年のコンテストはUpsilon Pi Epsilon Computer Science Honor Society (UPE) のAlpha Chapterが主催した。1977年にACM Computer Science Conferenceと併設して最初の決勝大会が行われ、この時から現在のような勝ち抜き型のコンテストとなった。

1977年から1989年の間は、主にアメリカ合衆国とカナダのチームを対象にして開催されていた。1989年からベイラー大学が大会本部となり、世界中の大学コミュニティの手で地区大会 (Regionals) が実施されるようになった。ACMの後援のもとで多くの企業のサポートを得て、2005年には84カ国からの参加がある世界的なコンテストに成長した。

1997年にIBMがスポンサーとなってから、コンテストの参加者は飛躍的に増大した。1997年の大会には560大学から840チームが、2007年には1,821大学から6,700チームが参加した。参加チーム数は毎年10-20%の割合で増え続けており、今後もさらに大規模になるだろうと考えられている。

ACM国際大学対抗プログラミングコンテストにおいて、世界大会 (ACM-ICPC World Finals) がその決勝戦である。歴史を振り返ると、世界各地の最高の開催地で4日間にわたるイベントが開催されている。このイベントで、Upsilon Pi Epsilonが全地区大会の優勝チームを表彰する。近年 (2009年時点) では、世界大会の優勝チームは自分たちの国の首脳から表彰を受け、毎年行われるACM Awards Ceremonyでも表彰されている。

日本における歴史

日本では、国内で初めてとなるアジア地区予選大会が1998年に早稲田大学をホストとして東京で開催された。これ以降、会場を変えながら、日本国内でも毎年アジア地区予選が開催されている。

日本では国内での初開催以来、アジア地区予選大会に参加するチーム数を制限するため、アジア地区予選大会の前にインターネットを通して国内予選が行われている。例年、この国内予選で優秀な成績をおさめたチーム (近年は、上位に入った2大学の最上位チームであることが多い) は、日本以外で開催されるアジア地区予選大会へ金銭的な支援を受けて派遣される権利を得る。

2000年に筑波大学をホストとして開催されたアジア地区予選つくば大会では、国内予選への参加が88チーム、アジア地区予選への参加が34チームであった。2010年には、国内予選への参加が67大学287チーム、アジア地区予選大会への参加が30大学35チーム (国内予選に参加していない6チームの海外チームを含む) となっている。

コンテストのルール

ICPCはチーム戦であり、それぞれのチームは3人の学生から構成される。参加者は、国内予選前の時点で大学入学から5年(4月入学で1-3月生まれの場合は6年)に満たない大学生でなければならない。過去に世界大会に2年出場、もしくは地区予選大会に5年出場した学生は再び参加する権利を失う。

コンテストの間、チームは5時間で8-12問 (典型的には10問) のプログラミングの問題を解く。与えられた問題を解く順番は不問である。選手は回答のプログラムをC、C++、Javaのいずれかで書いて提出しなければならない。提出すると、プログラムはテストデータを入力として実行される。このテストデータは、コンテスト中は公開されない。プログラムが不正に終了した場合や、正しい解を出すことができなかった場合は選手にその旨が伝えられ、選手は何度でも回答プログラムを修正し、提出することができる。各問題ごとに規定された実行時間内にプログラムが実行を完了しなかった場合は、不正解の扱いとなる。

最も多くの問題を正解したチームが勝者となる。メダルや賞を与えるために引き分けのチームに順位をつける必要がある場合、コンテスト開始時から各問題に正解を提出した時点までの経過時間に最終的に正解した問題について不正解の提出ごとに20分が加算され、その総和によってチームの順位が決定される。

例えば2つのチームRedとBlueがそれぞれ2問を正解して引き分けとなっている状況を考える。チームRedは、コンテストの開始から1:00後と2:45後に、それぞれ問題AとBに解答を提出した。このチームは問題Cに対して不正解の通知を受けたが、最終的に問題Cを正解していないため、これは無視された。チームBlueは、コンテスト開始からそれぞれ1:20後と2:00後に、それぞれ問題AとCに解答を提出した。このチームは問題Cに対して1回不正解の通知を受けた。このとき、チームRedの総時間は1:00+2:45=3:45と、チームBlueの総時間は1:20+2:00+0:20=3:40となる。最終的にチームBlueの勝利となる。

他のプログラミングコンテスト (例えば国際情報オリンピック) と比較して、ICPCの特徴は問題数が多いこと (ちょうど5時間で8問以上) である。他の特徴として、チームには3人の学生がいるにも関わらず、各チーム1台しかコンピュータを使うことができないということがある。このことが時間のプレッシャーをより大きなものにしている。勝つためには良いチームワークとプレッシャーに耐える能力が必要である。

日本におけるコンテストのルール

日本におけるアジア地区予選大会のルールは、基本的にはコンテスト全体で定められている上記のルールと同様である。1998年-2003年のアジア地区予選大会では問題数が8問だったが、2004年-2006年は9問、2007-2011年は10問で行われている。国内予選は3時間の制限時間で行われ、2003年までは5問、2004年-2009年は6問、2010-2011年は7問用意されている。

地区予選と世界大会 (進出ルール)

このコンテストはいくつかの段階で構成される。多くの大学では地区予選レベルの大会に参加するチームを決定するためのローカルコンテストを開催する。それから大学（の代表チーム）が地区予選大会に参加し、競技を行う。地区予選大会の勝者が世界大会に進出する。ある1つの大学から複数のチームが地区予選大会に参加することはできるが、世界大会には1つの大学から1つのチームしか参加することができない。各地区予選大会から、最低でも1チームが世界大会に進出する。多くのチームが参加する地区予選大会からは、複数のチームが世界大会に進出することがある。 (1つの巨大な地区予選大会から6チームものチームが出場することも時々ある)

1人の選手は世界大会に2回までしか参加することができない。

巨大な地区予選大会では、大学ごとのローカルコンテストと地区予選大会の間に小地区予選大会 (もしくは予選大会) を開くことがある。

アジア地区における進出ルール

2006年時点では、アジア地区からの世界大会進出チーム決定のルールが毎年のように変更されており、大きく揺れ動いている。

日本における進出ルール

日本で開催される地区予選大会から世界大会へ進出するチームの決定は、基本的にアジア地区全体のルールに則って行われる。

過去の大会

過去の日本におけるアジア地区予選大会

• 2016年度 つくば大会 筑波大学 http://icpc.iisf.or.jp/2016-tsukuba/
• 2015年度 つくば大会 筑波大学 http://icpc.iisf.or.jp/2015-tsukuba/
• 2014年度 東京大会 早稲田大学 http://icpc.iisf.or.jp/2014-waseda/
• 2013年度 会津大会 会津大学 http://sparth.u-aizu.ac.jp/icpc2013/
• 2012年度 東京大会 東京工業大学 http://www.cs.titech.ac.jp/icpc2012/
• 2011年度 福岡大会 九州大学 http://icpc2011.ait.kyushu-u.ac.jp/ja
• 2010年度 東京大会 国立情報学研究所 http://icpc2010.honiden.nii.ac.jp/
• 2009年度 東京大会 早稲田大学 http://www.waseda.jp/assoc-icpc2009/jp/
• 2008年度 会津大会 会津大学 http://sparth.u-aizu.ac.jp/icpc2008/index.php?lang=jp
• 2007年度 東京大会 東京大学 http://www.logos.ic.i.u-tokyo.ac.jp/icpc2007/jp/index.html
• 2006年度 横浜大会 慶應義塾大学 http://www.acm-japan.org/icpc2006/jp/
• 2005年度 東京大会 東京工科大学 http://www.teu.ac.jp/icpc/jp/
• 2004年度 愛媛大会 愛媛大学 http://www.ehime-u.ac.jp/ICPC/jp/
• 2003年度 会津大会 会津大学 http://www.u-aizu.ac.jp/conference/ACM/j/
• 2002年度 金沢大会 金沢工業大学 http://www.kitnet.jp/icpc/j/
• 2001年度 函館大会 公立はこだて未来大学 http://www.fun.ac.jp/icpc/index-j.html
• 2000年度 筑波大会 つくば国際会議場 http://icpc.score.is.tsukuba.ac.jp/index-j.html
• 1999年度 京都大会 京都リサーチパーク
• 1998年度 東京大会 早稲田大学

過去の世界大会

2017年時点で、世界大会に進出した日本の大学とその回数は、東京大学15回、京都大学14回、東京工業大学5回、会津大学3回、埼玉大学2回、筑波大学2回、電気通信大学2回、早稲田大学1回、大阪大学1回、慶應大学1回である。このうち、日本チームの過去最高成績は2013年と2015年の東京大学チームの3位である。世界大会が日本で開催されるのは2007年が初となる。

過去に世界大会に出場した日本チーム

年	開催地	大学	順位	メダル	メンバー
2017	Rapid City	東京大学		―
		慶應大学		―
		東京工業大学		―
		会津大学		―
2016	Phuket	東京大学	14位タイ/128チーム	―
		京都大学	28位タイ/128チーム	―
		大阪大学	順位無し	―
		会津大学	順位無し	―
2015	Marrakesh	東京大学	3位/128チーム	金	Kensuke Imanishi, Shogo Murai, Makoto Soejima
		京都大学	28位タイ/128チーム	―	Shogo Ehara, Shoichi Nishimura, Tomohiro Oka
		筑波大学	28位タイ/128チーム	―	Takaaki Hiragushi, Ryosuke Koyanagi, Nozomu Nakajima
2014	Ekaterinburg	東京大学	7位/122チーム	銀	Ikumi Hide, Kengo Nakasuka, Ryoga Tanaka
		京都大学	19位タイ/122チーム	―	Shogo Ehara, Shoichi Nishimura, Tomohiro Oka
		東京工業大学	45位タイ/122チーム	―	Shogo Kishimoto, Osamu Koga, Kotaro Osada
		筑波大学	45位タイ/122チーム	―	Takaaki Hiragushi, Isamu Takagi, Shunsuke Takano
2013	Saint Petersburg	東京大学	3位/120チーム	金	保坂和宏, Kensuke Imanishi, 副島真
		電気通信大学	14位タイ/120チーム	―	Izuru Matsuura, Naoto Osaka, Masafumi Yabu
		東京工業大学	順位無し	―	Osamu Koga, Masaya Suzuki, Kohei Suzuki
2012	Warsaw	東京大学	11位/112チーム	銅	Takuya Akiba, Masaki Watanabe, Kota Yoshizato
		京都大学	18位タイ/112チーム	―	Kentaro Imajo, Mitsuru Kusumoto, Shingo Mori
		電気通信大学	順位無し	―	Ryota Fujii, Ryo Matsumiya, Masafumi Yabu
2011	Orlando	東京大学	27位タイ/105チーム	―	Kazuhiro Hosaka, Eiichi Matsumoto, Yoko Oya
		京都大学	27位タイ/105チーム	―	Yasuharu Hirasawa, Norihiro Kamae, Shohei Nishida
2010	Harbin	東京大学	14位タイ/103チーム	―	Yoichi Iwata, Masatoshi Kitagawa, Song Gi Ryang
		京都大学	14位タイ/103チーム	―	Yasuharu Hirasawa, Norihiro Kamae, Shohei Nishida
2009	Stockholm	東京大学	20位タイ/100チーム	―	Yoichi Iwata, Masatoshi Kitagawa, Song Gi Ryang
		会津大学	49位タイ/100チーム	―	Yuki Hirano, Takashi Tayama, Nobuyuki Wachi
		埼玉大学	順位無し	―	Eiichiro Iwata, Junichi Tamura, Hiroshi Watabe
2008	Banff	東京大学	13位タイ/100チーム	―	Kazuki Ohta, Shuhei Takahashi, Sukehide Ushioda
		京都大学	47位タイ/100チーム	―	Toshiyuki Hanaoka, Norihiro Katsumaru, Yuichi Yoshida
2007	Tokyo	京都大学	14位タイ/88チーム	―	Toshiyuki Hanaoka, Norihiro Katsumaru, Yuichi Yoshida
		東京大学	26位タイ/88チーム	―	Nobuo Araki, Hiroshige Hayashizaki, Koichi Suematsu
		埼玉大学	44位タイ/88チーム	―	Masaya Kiwada, Kei Tateno, Hiroshi Watabe
2006	San Antonio	京都大学	19位タイ/83チーム	―	Ryota Kinjo, Takayuki Muranushi, Hideyuki Tanaka
		東京大学	19位タイ/83チーム	―	Toru Nishikawa, Shun Sakuraba, Yu Sugawara
2005	Shanghai	京都大学	29位タイ/78チーム	―	Ryota Kinjo, Takayuki Muranushi, Hideyuki Tanaka
		東京大学	順位無し	―	Kazuhiro Inaba, Shinya Kawanaka, Toshihiro Yoshino
2004	Prague	東京工業大学	27位タイ/73チーム	―	Yusuke Izumi, Tomohiro Kaizu, Dai Mikurube
2003	Beverly Hills	東京大学	11位/70チーム	銅	Kazuhiro Inaba, Masahiro Kasahara, Toshihiro Yoshino
		東京工業大学	21位タイ/70チーム	―	Yusuke Izumi, Yusuke Kikuchi, Dai Mikurube
2002	Honolulu	東京大学	18位タイ/64チーム	―	Tsuyoshi Ito, Masahiro Kasahara, Masashi Seiki
2001	Vancouver	京都大学	14位タイ/64チーム	銅	Yasutaka Atarashi, Tetsuo Ogino, Hiroki Yanagisawa
2000	Orlando	京都大学	7位タイ/60チーム	銅	Norimasa Fujita, Takashi Sumiyoshi, Satoshi Yamada
1999	Eindhoven	京都大学	18位タイ/62チーム	―	Yasutaka Atarashi, Takashi Sumiyoshi, Hiroki Yanagisawa
		早稲田大学	順位無し	―	Shinya Cho, Masaya Kurisu, Yusuke Sato
1998	Atlanta	京都大学	順位無し	―	Masashi Hayakawa, Ryo Yokoyama, Takuya Yoshihiro

外部リンク

• 公式サイト
• ACM 日本支部 - 閉鎖。（2012年11月24日時点のアーカイブ）
• 公益財団法人情報科学国際交流財団 - 解散した ACM 日本支部に代わって日本国内のACM国際大学対抗プログラミングコンテスト開催を引き継ぐ
• 楽天、ACM国際大学対抗プログラミングコンテスト 東京大会に特別協賛