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

出典: フリー百科事典『ウィキペディア（Wikipedia）』
移動先: 案内、 検索

テンプレート:Refimprove

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

日本における進出ルール

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


過去の大会

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

過去の世界大会

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

過去に世界大会に出場した日本チーム
年 開催地 大学 順位 メダル メンバー
2013 Saint Petersburg 東京大学 3位/120チーム 金 Kazuhiro Hosaka, Kensuke Imanishi, Makoto Soejima
電気通信大学 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

外部リンク

「http://wikippe.e-do-match.com/index.php?title=ACM国際大学対抗プログラミングコンテスト&oldid=9605」から取得