ICPC国内予選過去問
自分がこれまでに解いたICPC国内予選の過去問をまとめてみた。古いのもあって今見返すと妙に気恥ずかしい。問題全体を眺めてみると他のコンテストに比べて実装重めな気がする。記事書いてない問題や解いてない問題もあるので解決し次第追加していく方向で。
2010
- A: 角角画伯,かく悩みき (Pablo Squarson's Headache)
- B: 迷図と命ず (Amazing Mazes)
- C: ポロック予想 (Pollock's conjecture)
- D: ぐらぐら (Off Balance)
- E: 最強の呪文 (The Most Powerful Spell)
- http://d.hatena.ne.jp/komiyam/20110601/1306854318
- 冷静に見返すとこの年の問題はこれが一番難しい気がする。
- F: 古い記憶 (Old Memories)
- http://d.hatena.ne.jp/komiyam/20110328/1301259120
- 制限時間に余裕があれば実はそんなに難しくない。今までに書いたソースコードの汚さはこれがワーストだと思う。
- G: レーザー光の反射 (Laser Beam Reflections)
- http://d.hatena.ne.jp/komiyam/20110601/1306854322
- 幾何だし実装重めだけどアルゴリズム自体はただの総当たり。
2009
- A: 次期町長 (Next Mayor)
- B: 島はいくつある? (How Many Islands?)
- http://d.hatena.ne.jp/komiyam/20100710/1278760244
- 典型的なflood fill。
- C: 覆面算 (Verbal Arithmetic)
- D: 離散的速度 (Discrete Speed)
- E: カードゲーム (Cards)
- http://d.hatena.ne.jp/komiyam/20100809/1281370497
- 知識の有無だけで勝負がついてしまうので評判は悪いんじゃないかと想像する。
- F: 締まっていこう (Tighten Up!)
- まだ解いてない。当分解ける気がしない。
2008
- A: 等しい合計点 (Equal Total Scores)
- B: 月曜土曜素因数 (Monday-Saturday Prime Factors)
- まだ解いてない。
- C: 如何に汝を満足せしめむ? いざ数え上げむ… (How can I satisfy thee? Let me count the ways...)
- http://d.hatena.ne.jp/komiyam/20110206/1296968572
- アジア地区予選では頻出の構文解析。
- D: ちょろちょろロボット (Twirling Robot)
- E: 大玉転がし (Roll-A-Big-Ball)
- F: ICPC: チョコレートの知的合同分割 (ICPC: Intelligent Congruent Partition of Chocolate)
- まだ解いてない。
2007
- A: ICPC 得点集計ソフトウェア (ICPC Score Totalizer Software)
- B: ログイン/ログアウト記録の解析 (Analyzing Login/Logout Records)
- http://d.hatena.ne.jp/komiyam/20110206/1296968559
- いろんなやり方があると思う。そしてどのやり方でも通ると思う。
- C: ケーキカット (Cut the Cake)
- D: 崖登り (Cliff Climbing)
- E: くるくる (Twirl Around)
- まだ解いてない。無理ゲー臭しかしない。
- F: 部陪博士,あるいは,われわれはいかにして左右非対称になったか (Dr. Podboq or: How We Became Asymmetric)
- まだ読んでない。
2006
2005
- A: Ohgas' Fortune
- B: Polygonal Line Search
- http://d.hatena.ne.jp/komiyam/20100902/1283439631
- やるだけだけどバグを生まないような努力は必要。
- C: Numeral System
- http://d.hatena.ne.jp/komiyam/20100902/1283439386
- やるだけだった気がする。ソースを紛失してしまった。
- D: Traveling by Stagecoach
- E: Earth Observation with a Mobile Robot Team
- まだ読んでない。
- F: Cleaning Robot
2004
- A: Hanafuda Shuffle
- http://d.hatena.ne.jp/komiyam/20110608/1307487566
- 終わった状態から逆向きにシミュレーション、という手法は知っておいて損は無いと思う。
- B: Red and Black
- C: Unit Fraction Partition
- まだ解いてない。枝刈りむずかしい。
- D: Circle and Points
- http://d.hatena.ne.jp/komiyam/20100712/1278952065
- 幾何でよくある、「動かせるギリギリまで動かす」な問題。
- E: Water Tank
- まだ解いてない。バグ埋め込まないように工夫して書きたい。
- F: Name the Crossing
- まだ読んでない。