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

出典: フリー百科事典『ウィキペディア(Wikipedia)』
Jump to navigation Jump to search

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問) のプログラミングの問題を解く。与えられた問題を解く順番は不問である。選手は回答のプログラムをCC++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年時点では、アジア地区からの世界大会進出チーム決定のルールが毎年のように変更されており、大きく揺れ動いている。

日本における進出ルール[編集]

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


歴代優勝校[編集]

Years
Year Country Institution
2018 ロシアの旗 ロシア モスクワ大学
2017 ロシアの旗 ロシア サンクトペテルブルグ国立情報技術・機械・光学大学
2016 ロシアの旗 ロシア サンクトペテルブルク大学
2015 ロシアの旗 ロシア サンクトペテルブルグ国立情報技術・機械・光学大学
2014 ロシアの旗 ロシア サンクトペテルブルク大学
2013 ロシアの旗 ロシア サンクトペテルブルグ国立情報技術・機械・光学大学
2012 ロシアの旗 ロシア サンクトペテルブルグ国立情報技術・機械・光学大学
2011 中華人民共和国の旗 中国 浙江大学
2010 中華人民共和国の旗 中国 上海交通大学
2009 ロシアの旗 ロシア サンクトペテルブルグ国立情報技術・機械・光学大学
2008 ロシアの旗 ロシア サンクトペテルブルグ国立情報技術・機械・光学大学
2007 ポーランドの旗 ポーランド ワルシャワ大学
2006 ロシアの旗 ロシア サラトフ国立大学
2005 中華人民共和国の旗 中国 上海交通大学
2004 ロシアの旗 ロシア サンクトペテルブルグ国立情報技術・機械・光学大学
2003 ポーランドの旗 ポーランド ワルシャワ大学
2002 中華人民共和国の旗 中国 上海交通大学
2001 ロシアの旗 ロシア サンクトペテルブルク大学
2000 ロシアの旗 ロシア サンクトペテルブルク大学
1999 カナダの旗 カナダ ウォータールー大学
1998 チェコの旗 チェコ プラハ・カレル大学
1997 アメリカ合衆国の旗 アメリカ ハーベイ・マッド大学
1996 アメリカ合衆国の旗 アメリカ カリフォルニア大学バークレー校
1995 ドイツの旗 ドイツ アルベルト・ルートヴィヒ大学フライブルク
1994 カナダの旗 カナダ ウォータールー大学
1993 アメリカ合衆国の旗 アメリカ ハーバード大学
1992 オーストラリアの旗 オーストラリア メルボルン大学
1991 アメリカ合衆国の旗 アメリカ スタンフォード大学
1990 ニュージーランドの旗 ニュージーランド オタゴ大学
1989 アメリカ合衆国の旗 アメリカ カリフォルニア大学ロサンゼルス校
1988 アメリカ合衆国の旗 アメリカ カリフォルニア工科大学
1987 アメリカ合衆国の旗 アメリカ スタンフォード大学
1986 アメリカ合衆国の旗 アメリカ カリフォルニア工科大学
1985 アメリカ合衆国の旗 アメリカ スタンフォード大学
1984 アメリカ合衆国の旗 アメリカ ジョン・ホプキンス大学
1983 アメリカ合衆国の旗 アメリカ ネブラスカ大学
1982 アメリカ合衆国の旗 アメリカ ベイラー大学
1981 アメリカ合衆国の旗 アメリカ ミズーリ科学技術大学
1980 アメリカ合衆国の旗 アメリカ ワシントン大学
1979 アメリカ合衆国の旗 アメリカ ワシントン大学
1978 アメリカ合衆国の旗 アメリカ マサチューセッツ工科大学
1977 アメリカ合衆国の旗 アメリカ ミシガン大学

過去の大会[編集]

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

過去の世界大会[編集]

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

過去に世界大会に出場した日本チーム
開催地 大学 順位 メダル メンバー
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

外部リンク[編集]