ACM-ICPC 国内予選

国内予選の問題の総評・難易度など。2009年度までの、過去の国内予選の問題を全て実装・分析してみました。ネタバレを多分に含みます。

凡例

難易度は☆5段階で表しています。★は☆半分を表します。

  • ☆    :非常に易しい。全員が解いてほしい問題。
  • ☆☆   :易しい。アジア地区予選に進む為には絶対に解かなければならない。
  • ☆☆☆  :標準。アジア地区予選に進む為にはこのクラスの問題を1つは解けなければならない。
  • ☆☆☆☆ :難しい。上位に食い込む為には解かなければならない。
  • ☆☆☆☆☆:大変難しい。上位陣でも難しい。

解法・アルゴリズムでは、キーとなるアルゴリズム名を書いています。ad-hoc と書いてあるものは、その場その場で実装して解いていく問題を表しています。

ソースは、私が解いたソースへのリンクを張っています。

公式の output や PKU での問題と解答を比較していますが、解答が提供されていない問題もあるため、正答と比較出来ない場合があります。その場合備考に “Not Verified” と書いてあり、ソースの正当性は担保できません。間違っている恐れもあります。また、他の人が解を既に公開している場合、その解との比較を行って正解と見なした場合、その解へのリンクを張っています。また、PKU やプログラム・プロムナードへのリンクも、あれば張っています。公式の output があるものは PKU は通してないので、PKU だと TLE になる可能性があります。

1998 年

日本地区予選が始まった年。今から見ると簡単な問題のみで構成されています。それでもみんな解けていません。

問題問題名難易度解法・アルゴリズムソース備考
1Area of Polygons☆★多角形の面積1998A.ccNot Verified.
2A Simple Offline Text Editor☆☆ad-hoc1998B.ccNot Verified.
3Calculation of Expressions☆☆☆構文解析1998C.ccNot Verified.
4Board Arrangements for Concentration Games☆☆☆探索1998D.ccNot Verified.

1999 年

問題が5題に。今から見るとそれほど難しい問題は出ていません。

正答例がないため、Naoyuki Tamura さんの解答と比較しています。

問題問題名難易度解法・アルゴリズムソース備考n
AWhere'sYourRobot?ad-hoc1999A.cc
BUnableCount☆☆ad-hoc1999B.ccプロムナード
CFactorizationofQuadraticFormula☆☆ad-hoc1999C.cc
DSpiralFootrace☆☆☆★凸包に近い1999D.cc
EALongRideonaRailway☆☆☆探索1999E.cc

2000 年

前年よりは少し難しくなっていますが、まだそれでも今よりは簡単でしょう。E はやや問題文が理解しにくい。 この年の問題も正答例がないため、Naoyuki Tamura さんの解答と比較しています。

問題問題名難易度解法・アルゴリズムソース備考
AFermat's Last Theoremad-hoc2000A.cc
BPatience☆☆★探索2000B.cc
CCyber Guardian☆☆★ad-hoc2000C.cc
DStrange Key☆☆☆★ad-hoc2000D.cc
EFile Compression☆☆☆★ad-hoc2000E.cc

2001 年

前年と同程度の難しさ。

正答例が提供されていないため、東工大 Wiki の正答例と比較しています。

問題問題名難易度解法・アルゴリズムソース備考
AGet a Rectangular Fieldad-hoc2001A.cc東工大 Wiki (A) プロムナード
BMulti-column List☆☆ad-hoc2001B.cc東工大 Wiki (B)
CJigsaw Puzzles for Computers☆☆探索2001C.cc東工大 Wiki (C) プロムナード
DMissing Numbers☆☆☆連立方程式2001D.cc東工大 Wiki (D)
ENets of Dice☆☆☆★さいころ・探索2001E.cc東工大 Wiki (E)

2002 年

幾何問題が少し難しいですが、今のチームのレベルならおそらく全部解かれてしまうでしょう。A-D は今なら 80 分ぐらいで処理されてしまうかも。 東工大 Wiki, ACM-ICPC OB/OG の会に投稿されたソースと比較。C, D は未比較のため間違っているかもしれません。

問題問題名難易度解法・アルゴリズムソース備考
A Exploring Cavesad-hoc2002A.cc東工大 Wiki 2002 A
B Pile Up!☆☆ad-hoc2002B.cc東工大 Wiki 2002 B
C Kanglish : Analysis on Artificial Language☆☆ad-hoc2002C.ccNot Verified.
D What is the Number in my Mind?☆☆☆探索2002D.ccNot Verified.
E Enclosing Circles☆☆☆☆★幾何・円の共通接線2002E.ccACM-ICPC OB/OG の会 プロムナード

2003 年

E とそれ以外の難易度にかなり差があります。4問正解チームがかなりあり、全問正解は1チーム (Gokuri、自分のチーム)。E は探索ですが、ヒューリスティクスが必要なところが難しくなっています。最小全域木のアルゴリズムを知らないと、この年は苦しい戦いになったでしょう。

PKU に問題があるので、PKU で確認。

問題問題名難易度解法・アルゴリズムソース備考
AWhen Can We Meet?ad-hoc2003A.ccPKU 2028
BGet Many Persimmon Trees☆☆ad-hoc2003B.ccPKU 2029
CThe Secret Number☆☆☆動的計画法2003C.ccPKU 2030
DBuilding a Space Station☆☆☆最小全域木2003D.ccPKU 2031
ESquare Carpets☆☆☆☆★探索(ヒューリスティクス)2003E.ccPKU 2032

2004 年

問題が6題になり、易しい問題が一題追加されました。D, E, F はそれぞれ別の能力を要求しており、全て解ききるのは難しめ。D は幾何のひらめき、E は実装力、F は情報科学的なアルゴリズム構築能力と、かなり良いセット。全問正解が1チームあった(Gokuri-squeeze、これも自分のところのチーム)。

D は -O2 をつけて (あるいは Release build で) コンパイルしないと非常に遅くて、正解なのに正解と思ってなかったというチームがありました。

問題問題名難易度解法・アルゴリズムソース備考
AHanafuda Shufflead-hoc2004A.ccPKU 1978
BRed and Black☆☆再帰2004B.ccPKU 1979
CUnit Fraction Partition☆☆探索2004C.ccPKU 1980
DCircle and Points☆☆☆☆幾何・2点を通り半径が与えられた円2004D.ccPKU 1981
EWater Tank☆☆☆☆ad-hoc (シミュレーション)2004E.ccPKU 1982
FName the Crossing☆☆☆☆Floyd2004F.ccPKU 1983

2005 年

少し易しくなりました。E は幾何とシミュレーションの両方をこなす必要があって、やや難しめ。1チーム (GNC) が全問正解。

問題問題名難易度解法・アルゴリズムソース備考
AOhgas' Fortune☆★ad-hoc2005A.ccPKU 2683
BPolygonal Line Search☆☆★ad-hoc2005B.ccPKU 2684
CNumeral System☆☆構文解析2005C.ccPKU 2685
DTraveling by Stagecoach☆☆☆☆ダイクストラ2005D.ccPKU 2686
EEarth Observation with a Mobile Robot Team☆☆☆☆★幾何・線と線の距離2005E.ccPKU 2687
FCleaning Robot☆☆☆全探索2005F.ccPKU 2688

2006 年

少し難し目のセット。F は分かればそんなに難しくないが、本番で解くのは厳しい。C は実装が面倒。Input, Outout は こちらにある。5問正解が2チーム。C, F が両方とも国内予選で最難クラスの問題なので、全問正解はかなり厳しいだろう。

問題問題名難易度解法・アルゴリズムソース備考
ADirichlet's Theorem on Arithmetic Progressions☆★エラトステネス2006A.ccPKU 3006
BOrganize Your Train part II☆☆ad-hoc2006B.ccPKU 3007
CHexerpents of Hexwamp☆☆☆☆探索2006C.ccPKU 3008
DCurling 2.0☆☆☆探索2006D.ccPKU 3009
EThe Genome Database of All Space Life☆☆☆★ad-hoc (再帰)2006E.ccPKU 3010
FSecrets in Shadows☆☆☆☆★幾何・円と円の接線2006F.ccPKU 3011

2007 年

E を除いて易しいセット。E はおそらく国内予選の史上最難問題と思われます。A は国内予選最易。この年は特別に予選通過チームが多くなっていました。5問正解が4チーム。

問題問題名難易度解法・アルゴリズムソース備考
AICPC Score Totalizer Softwaread-hoc2007A.ccPKU 3325
BAnalyzing Login/Logout Records☆☆ad-hoc2007B.ccPKU 3326
CCut the Cake☆☆★ad-hoc2007C.ccPKU 3327
DCliff Climbing☆☆☆★ダイクストラ2007D.ccPKU 3328
ETwirl Around☆☆☆☆☆幾何・円と線分の交差判定2007E.ccPKU 3329
FDr. Podboq or: How We Became Asymmetric☆☆☆★DP あるいはキャッシュ付き再帰2007F.ccPKU 3330

2008 年

全問正解が3チームも出た年。F 以外は易しく、最難問題としての F は例年並。

おそらく来年は、難しい問題2題のレベルがあがるだろうと予想します。E が難しい問題のレベルとしては簡単すぎるため、F を解く時間を与えてしまっています。みんな確かに幾何は苦手です。しかし、、これぐらい単純だと苦にならないので、幾何問題として選手を苦しめるには至っていません。

問題問題名難易度解法・アルゴリズムソース備考
AEqual Total Scoresad-hoc2008A.cc
BMonday-Saturday Prime Factors☆★エラトステネスのふるい2008B.cc
CHow can I satisfy thee? Let me count the ways...☆☆構文解析2008C.cc
DTwirling Robot☆☆☆ダイクストラ2008D.cc
ERoll-A-Big-Ball☆☆☆★幾何・線分と線分の距離2008E.cc
FICPC: Intelligent Congruent Partition of Chocolate☆☆☆☆探索2008F.cc

2009 年

全問正解が1チーム。D は拡大グラフのダイクストラ、E は2部グラフの最大マッチングと、知識と経験がものをいう問題が並びました。5問以上正解は15チームもあるという、レベルの高い争いでした。5問正解しても予選落ちしたチームがついに東大以外からも出ました。上位陣向けに、中盤の問題をもう少し難しくしないとだめかも。F は幾何で難しそうなのだが、落ち着いて書いてみると意外とあっさりと書ける問題。F の解答ソースは長さが更新されるまでループということにしています。誤差がゆるいのでこれで大丈夫でしょうが、議論の余地はあるでしょう。

問題問題名難易度解法・アルゴリズムソース備考
ANext Mayorシミュレーション2009A.cc
BHow Many Islands?☆★ad-hoc2009B.cc
CVerbal Arithmetic☆☆dfs2009C.cc
DDiscrete Speed☆☆☆★ダイクストラ2009D.cc
ECards☆☆☆☆二部グラフの最大マッチング2009E.cc
FTighten Up!☆☆☆☆★幾何2009F.cc
2009-12-31
icpc