ACM/ICPC国内予選突破の手引き

ACM/ICPCの2008年度の大会日程が公開されています。 国内予選は2008年7月4日，アジア地区予選会津大会は2008年10月25日～27日でホスト校は会津大学です。 参加登録締め切りは2008年6月20日です。

ここではACM/ICPC（ACM国際大学対抗プログラミングコンテスト: ACM International Collegiate Programming Contest）で 国内予選を突破するために必要な情報を載せています。 ACM/ICPC自体については2006年度の横浜大会のWebサイトなどを読んでください。

結局のところ，ACM/ICPCで良い成績を残すにはひたすら問題を解く練習をするしかありません。 ですが，出題される問題の多くはいくつかのカテゴリ，例えば探索問題やグラフ問題，あるいは幾何問題などに分類することができます。 つまり，「傾向と対策」が存在します。 本サイトでは，特にどのように勉強をしていったら国内予選を突破できるのかが分からないACM/ICPC初学者向けに， 典型的な問題を効率的に学べるように「問題の種類分け」と「アルゴリズムの解説」を記載していきます。

問題の解き方

ここに載せている問題はPKU JudgeOnlineもしくはUVaで解いてください （本サイトの各問題名のリンクは対応するPKUまたはUVaの問題ページに張っています）。 Webブラウザでソースコードをsubmitすれば自動的に正解かどうかを判定してくれるシステムです。 手元でサンプルインプットに対して正解が出たら，そのソースコードをコピーしてsubmitします。 英語に不慣れな方は，日本語問題文が存在する場合はそれを転載していますので，最初は日本語の問題から解き始めると良いでしょう。

PKUやUVaのサイトではプログラムの入力は標準入力からになっています。 日本でのアジア地区予選大会のようにPC2で正否を判定するシステムが使われている場合など， ファイルからの入力が要求されることもあります。 入出力でつまずいても面白くないので，入出力についてまとめたページを書きましたので慣れるまでは参照してください。 なお，出力は全て標準出力に書き出します。

一部の問題についてはPKU/UVaに載っていないので自動的に正否判定することができません。 その場合は手元で diff コマンドを使って自分の出力と正解出力が同じかどうかを判定することになります （「プログラミング環境を整える」を参照）。

問題の一覧

問題のだいたいの難易度は「☆：最も簡単」～「☆☆☆☆☆：最も難しい」で表しています。 ただし，難易度の基準は国内予選レベルにしています。

今までの国内予選の結果を見ていると，難易度が「☆☆」までの問題は全て確実に解けないと国内予選を突破することはできません。 そして「☆☆」までの問題が全て解けたチームは国内予選を突破できています。 しかし例年レベルが上がってきているので，2007年度は「☆☆」に加えて「☆☆☆」の問題も一つは解けないと国内予選を突破することができなくなるかもしれません。

Step by step

ACM/ICPCを始めたばかりの方は簡単な問題から順にこなしていきましょう。 以下に掲げる問題を順番に解いていけば，国内予選を通る実力が身に付いていきます。 解く必要のない問題は載せていません。

問題 難易度 問題の種類 解法の種類
（全て表示）		 解説
Hanafuda Shuffle（日本語） ☆ シミュレーション 表示 解説
Ohgas' Fortune（日本語） ☆ 文章読解 表示 解説
Keitai Message（日本語） ☆ シミュレーション 表示 解説
Exploring Caves（英語問題文） ☆ シミュレーション 表示 解説
When Can We Meet? ☆ 探索 表示 解説
Make Purse Light（日本語） ☆ 探索 表示 解説
Get Many Persimmon Trees ☆ 探索 表示 解説
Numeral System（日本語） ☆ 文字列操作 表示 解説
Red and Black（日本語） ☆☆ 再帰 表示 解説
Polygonal Line Search（日本語） ☆☆ 幾何 表示 解説
Dirichlet's Theorem on Arithmetic Progressions（日本語） ☆☆ 数論 表示 解説
Unit Fraction Partition（日本語）（判定データ） ☆☆ 探索 表示 解説
Organize Your Train part II（日本語） ☆☆ 文字列操作 表示 解説
Curling 2.0（日本語） ☆☆ 探索 表示 解説
Dragon Fantasy（日本語） ☆☆☆ 探索 表示 解説
The Secret Number ☆☆☆ DP 表示 解説
Gather the Maps!（日本語） ☆☆☆ DP 表示 解説
Circle and Points（日本語）（判定データ） ☆☆☆ 幾何 表示 解説
Area Separation（日本語） ☆☆☆ 幾何 表示 解説
Non-Stop Travel ☆☆☆ グラフ 表示 解説
Cleaning Robot（日本語）（判定データ） ☆☆☆ グラフ 表示 解説

＋α

Step by step で築いた基礎能力を定着させるための問題です。 早く正確に問題を解けるようにしましょう。 何分で解けたかを計ってみるとよいでしょう。

問題 難易度 問題の種類 解法の種類
（全て表示）		 解説
Mysterious Gems（日本語） ☆ シミュレーション 表示 解説
Amida, the City of Miracle（日本語） ☆ シミュレーション 表示 解説
Space Coconut Crab（日本語） ☆ 探索 表示 解説
Osaki（日本語） ☆ シミュレーション 表示 解説
Surrounding Area（日本語） ☆☆ 再帰 表示 解説
Railroad Conflict（日本語） ☆☆☆ 幾何 表示 解説
Square Route（日本語） ☆☆☆ 幾何 表示 解説

DP特集

動的計画法 (Dynamic Programming) 略してDPはACM/ICPCで頻出です。

問題 難易度 問題の種類 解法の種類
（全て表示）		 解説
The Secret Number ☆☆☆ DP 表示 解説
Gather the Maps!（日本語） ☆☆☆ DP 表示 解説
Sum of Different Primes ☆☆☆ DP 表示 解説
Common Subsequence ☆☆☆ DP 表示 解説
Honeycomb Walk ☆☆☆ DP, Hex 表示 解説

幾何特集

ACM/ICPCでは特に平面幾何の問題が多いようです。 線分の交差判定などの基本的な問題は確実に解けるようになっておきましょう。

問題 難易度 問題の種類 解法の種類
（全て表示）		 解説
Circle and Points（日本語）（判定データ） ☆☆☆ 幾何 表示 解説
Area Separation（日本語） ☆☆☆ 幾何 表示 解説
Railroad Conflict（日本語） ☆☆☆ 幾何 表示 解説

年代別

2007年度

2007年度（東京大会）の国内予選問題一覧：

問題 難易度 問題の種類 解法の種類
（全て表示）		 解説
A: ICPC Score Totalizer Software
B: Analyzing Login/Logout Records
C: Cut the Cake
D: Cliff Climbing
E: Twirl Around
F: Dr. Podboq or: How We Became Asymmetric

「OB/OGの会」の2007年度模擬国内予選問題一覧：

問題 難易度 問題の種類 解法の種類
（全て表示）		 解説
A: Space Coconut Crab（日本語） ☆ 探索 表示 解説
B: Osaki（日本語） ☆ シミュレーション 表示 解説
C: Surrounding Area（日本語） ☆☆ 再帰 表示 解説
D: Square Route（日本語） ☆☆☆ 幾何 表示 解説
E: Lifeguard in the Pool ☆☆☆☆ 幾何
F: Karakuri Doll ☆☆☆☆ 探索
2006年度

2006年度（横浜大会）の国内予選問題一覧：

問題 難易度 問題の種類 解法の種類
（全て表示）		 解説
A: Dirichlet's Theorem on Arithmetic Progressions（日本語） ☆☆ 数論 表示 解説
B: Organize Your Train part II（日本語） ☆☆ 文字列操作 表示 解説
C: Hexerpents of Hexwamp
D: Curling 2.0（日本語） ☆☆ 探索 表示 解説
E: The Genome Database of All Space Life
F: Secrets in Shadows

「OB/OGの会」の2006年度模擬国内予選問題一覧：

問題 難易度 問題の種類 解法の種類
（全て表示）		 解説
A: Mysterious Gems（日本語） ☆ シミュレーション 表示 解説
B: Amida, the City of Miracle（日本語） ☆ シミュレーション 表示 解説
C: X-Ray Screening System
D: Railroad Conflict（日本語） ☆☆☆ 幾何 表示 解説
E: Data Center on Fire
F: Water Pipe Construction
2005年度

2005年度（東京大会）の国内予選問題一覧：

問題 難易度 問題の種類 解法の種類
（全て表示）		 解説
A: Ohgas' Fortune（日本語） ☆ 文章読解 表示 解説
B: Polygonal Line Search（日本語） ☆☆ 幾何 表示 解説
C: Numeral System（日本語） ☆ 文字列操作 表示 解説
D: Traveling by Stagecoach
E: Earth Observation with a Mobile Robot Team
F: Cleaning Robot（日本語）（判定データ） ☆☆☆ グラフ 表示 解説

「OB/OGの会」の2005年度模擬国内予選問題一覧：

問題 難易度 問題の種類 解法の種類
（全て表示）		 解説
A: Keitai Message（日本語） ☆ シミュレーション 表示 解説
B: Make Purse Light（日本語） ☆ 探索 表示 解説
C: Dragon Fantasy（日本語） ☆☆☆ 探索 表示 解説
D: Area Separation（日本語） ☆☆☆ 幾何 表示 解説
E: Poor Mail Forwarding
F: Gather the Maps!（日本語） ☆☆☆ DP 表示 解説
2004年度

2004年度（愛媛大会）の国内予選問題一覧：

問題 難易度 問題の種類 解法の種類
（全て表示）		 解説
A: Hanafuda Shuffle（日本語） ☆ シミュレーション 表示 解説
B: Red and Black（日本語） ☆☆ 再帰 表示 解説
C: Unit Fraction Partition（日本語）（判定データ） ☆☆ 探索 表示 解説
D: Circle and Points（日本語）（判定データ） ☆☆☆ 幾何 表示 解説
E: Water Tank
F: Name the Crossing
2003年度

2003年度（会津大会）の国内予選問題一覧：

問題 難易度 問題の種類 解法の種類
（全て表示）		 解説
A: When Can We Meet? ☆ 探索 表示 解説
B: Get Many Persimmon Trees ☆ 探索 表示 解説
C: The Secret Number ☆☆☆ DP 表示 解説
D: Building a Space Station
E: Square Carpets
2002年度

2002年度（金沢大会）の国内予選問題一覧：

問題 難易度 問題の種類 解法の種類
（全て表示）		 解説
A: Exploring Caves（英語問題文） ☆ シミュレーション 表示 解説
B: Pile Up!
C: Kanglish : Analysis on Artificial Language
D: What is the Number in my Mind ?
E: Enclosing Circles プログラムプロムナードの解説

各種解説

さらに学ぶために

その他

$Id: index.shtml 2029 2008-02-10 09:53:00Z SYSTEM $