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年度 つくば大会 筑波大学[※ 1]
- 2015年度 つくば大会 筑波大学[※ 2]
- 2014年度 東京大会 早稲田大学[※ 3]
- 2013年度 会津大会 会津大学[※ 4]
- 2012年度 東京大会 東京工業大学[※ 5]
- 2011年度 福岡大会 九州大学[※ 6]
- 2010年度 東京大会 国立情報学研究所[※ 7]
- 2009年度 東京大会 早稲田大学[※ 8]
- 2008年度 会津大会 会津大学[※ 9]
- 2007年度 東京大会 東京大学[※ 10]
- 2006年度 横浜大会 慶應義塾大学[※ 11]
- 2005年度 東京大会 東京工科大学[※ 12]
- 2004年度 愛媛大会 愛媛大学[※ 13]
- 2003年度 会津大会 会津大学[※ 14]
- 2002年度 金沢大会 金沢工業大学[※ 15]
- 2001年度 函館大会 公立はこだて未来大学[※ 16]
- 2000年度 筑波大会 つくば国際会議場[※ 17]
- 1999年度 京都大会 京都リサーチパーク
- 1998年度 東京大会 早稲田大学
過去の世界大会
編集2022年時点で、世界大会に進出した日本の大学とその回数は、東京大学18回、京都大学16回、東京工業大学7回、筑波大学4回、会津大学4回、埼玉大学2回、電気通信大学2回、早稲田大学2回、慶應義塾大学2回、大阪大学1回である。このうち、日本チームの過去最高成績は2013, 2015, 2019, 2022年の東京大学チームの3位である。世界大会が日本で開催されるのは2007年が初となる。
| 年 | 開催地 | 大学 | 順位 | メダル | メンバー | |
|---|---|---|---|---|---|---|
| 2022 | Dhaka | 東京大学 | 3位/132チーム | 金 | Hirotaka Isa, Riku Kawasaki, Yuta Takaya | |
| 東京工業大学 | 15位/132チーム | ― | Mikihito Matsuura, Takuto Yoshida, Tatsuhito Yamagata | |||
| 京都大学 | 23位/132チーム | ― | Chuta Yamaoka, Tomohito Omori, Yuya Kadono | |||
| 慶應義塾大学 | 42位/132チーム | ― | Keita Murase, Ryuto Kojima, Tomohiro Nakayoshi | |||
| 2021 | Moscow | 会津大学 | 27位/117チーム | ― | Aki Nakamura, Hiroki Ohashi, Hisato Matsukawa | |
| 2019 | Porto | 東京大学 | 3位/135チーム | 金 | Kohei Morita, Riku Kawasaki, Takuto Shigemura | |
| 筑波大学 | 21位タイ/135チーム | ― | Yuki Koike, Akio Matsuzaki, Nozomu Nakajima | |||
| 京都大学 | 41位タイ/135チーム | ― | Go Kato, Ryoma Sato, Shunta Masuda | |||
| 早稲田大学 | 41位タイ/135チーム | ― | Taiki Yamada, Ko Sato, Ryo Ishizuka | |||
| 2018 | Beijing | 東京大学 | 4位/135チーム | 金 | Kazumi Kasaura, Soh Kumabe, Kohji Liu | |
| 東京工業大学 | 31位タイ/135チーム | ― | Riki Fukunari, Mikito Ota, Takuto Yoshida | |||
| 筑波大学 | 順位無し | ― | Haruka Iwaki, Yuuji Moroto, Yasuaki Rokugo | |||
| 2017 | Rapid City | 東京大学 | 12位/133チーム | 銅 | Kazumi Kasaura, Soh Kumabe, Kohji Liu | |
| 東京工業大学 | 34位タイ/133チーム | ― | Ngoc Khanh Do, Hiroki Katsumata, Kohei Morita | |||
| 慶應義塾大学 | 56位タイ/133チーム | ― | Kento Nikaido, Naoya Niwa, Tetsui Ohkubo | |||
| 会津大学 | 56位タイ/133チーム | ― | Kazuya Watanabe, Tadamasa Yamaguchi, Takumi Yamashita | |||
| 2016 | Phuket | 東京大学 | 14位タイ/128チーム | ― | Ikumi Hide, Shogo Murai, Shinya Shiroshita | |
| 京都大学 | 28位タイ/128チーム | ― | Akifumi Imanishi, Yuta Ojima, Kazuki Takise | |||
| 大阪大学 | 順位無し | ― | Naohiro Kawamitsu, Kazuma Mikami, Yosuke Sameshima | |||
| 会津大学 | 順位無し | ― | Kazuki Omomo, Tadamasa Yamaguchi, Takumi Yamashita | |||
| 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-ICPC 2016 Asia Tsukuba Regional | 国際大学対抗プログラミングコンテスト2016アジア地区つくば大会
- ^ ACM-ICPC 2015 Tsukuba | 国際大学対抗プログラミングコンテスト
- ^ The 2014 ACM-ICPC Asia Tokyo Regional Contest The 2014 ACM-ICPC Asia Tokyo Regional Contest | ACM-ICPC 国際大学対抗プログラミングコンテスト
- ^ The 2013 ACM-ICPC Asia Aizu Regional Contest :: Home
- ^ ACM-ICPC 2012 in Tokyo
- ^ [1]
- ^ [2]
- ^ [3]
- ^ Aizu ACM/ICPC 2008 contest :: Home
- ^ [4]
- ^ [5]
- ^ [6]
- ^ [7]
- ^ The 2003 ACM/ICPC Regional Programming Contest, Aizu-Wakamatsu, Japan
- ^ Kanazawa Institute of Technology
- ^ [8]
- ^ [9]
外部リンク
編集- ICPC World Finals
- ACM 日本支部 - 閉鎖。（2012年11月24日時点のアーカイブ）
- 公益財団法人情報科学国際交流財団 - 解散した ACM 日本支部に代わって日本国内のACM国際大学対抗プログラミングコンテスト開催を引き継ぐ
- 楽天、ACM国際大学対抗プログラミングコンテスト 東京大会に特別協賛