過去の国内予選の分析

松永賢次（専修大学ネットワーク情報学部）

学生の練習のために，久々に，過去の国内予選の問題を調べて分析してみた。
★の数で難易度を示しています。
★：これを解けないようでは参加している意味がない。
★★：難しくはないが，コーディングに注意深さは必要。この問題が早くできれば，予選通過はできるが，このレベルまでしかできないと，アジア地区予選では参加するだけのチームになってしまう。
★★★：アルゴリズムの知識が必要，あるいは，コーディングにタフなところがある問題。このレベルの問題が１つ解ければ，ほぼ確実に予選突破できる。
★★★★：さらに高度でタフな問題。アジア地区予選で上位に入るチームであれば，このレベルが解ける必要がある。
★★★★★：コンテストの時間ではまず解けない。

1999年京都大会

出題言語：英語，時間：3時間半。

このときは，専修大学からは予選突破しても不思議ではないチームが４チームあったのだが，3問正解が１チーム(A, D, E)，2問正解が１チーム(A, B)，1問も正解できないチームが2チームあった。どの問題も解けないほど難しくはないが，やさしそうな問題でも微妙に落とし穴があるようだ。現在（2004年）の参加チームのレベルだと，全問正解が続出するであろう。

A: Where's Your Robot? ★: 問題に書いたある通りにプログラムを書けばよいシミュレーション問題。この大会ではもっともやさしい。
B: Unable Count ★★: 組み合わせを調べるGenerate and Testの問題。データの最大が100万ということになっているので，まともに多重ループを書くとだめ，という問題。計算量を意識して，どうやったらさぼれるのか考えられないといけない。この大会では二番目にやさしい。この問題の解説はこちらにある（情報処理学会誌解説）。
C: Factorization of Quadratic Formula ★★★(2.5): これも組み合わせを調べるGenerate and Testの問題。結果の出力順序を意識して，どの順序でループをまわしていくべきか考えられないといけない。場合分けに面倒なところもあるので，Bよりは手間がかかるであろう。
D: Spiral Footrace ★★★: 図形の問題については，外積を使うというのは代表的なパターンのようである。現在の点Aと，余った点の中から任意の2点(B, C)を選んで，すべてのCが線分ABの内側にあるような点Bを選ぶ。内側にあるかどうかは外積を求めたときの符号で判断できる。さらに，同じ線上にのっているときの判断を加える必要がある。基本的な枠組みは総当りで，検査する方法に外積を使うということになる。
E: A Long Ride on a Railway ★★★: グラフの接続行列を作って，バックトラックで調べればよい。

2000年つくば大会

A: Fermat's Last Theorem ★: Generate and Testの基本的な問題。この大会ではもっともやさしい。数式の読み方さえわかれば何でもないので，プログラムの問題というよりは数学の問題。前ふりも長いので英語の問題とも言えるかもしれない。なお，このときの大会は25分くらいで，この問題だけを解ければ予選通過となった。数学の能力で識別することになってしまう出題はやめてほしい，と主張したことが，多分，出題チームに理解されているので，今後は，Aの問題には，このような出題パターンは出ないと思われる。
B: Patience ★★★(2.5): バックトラックの問題。２問解くとなると，この問題かCを解くことになるだろう。
C: Cyber Guardian ★★: パケットフィルタリングのルールを読んでシミュレーションする問題。ルールが競合したときの取り扱い，デフォルトルールなどをきちんと把握すること（問題をよく読むこと）が重要。間違えたときに，ジャッジデータの量がものすごく大きくて，デバッグしにくいように作られている。
D: Strange Key ★★★★★: 今回の問題セットで一番難しいと思われる。1位のチームでも４問しか解いていないので，おそらく，この問題が解けていないのであろう。自分がプログラムを書いていないので本当に解けるか怪しいが，図形を正規化した表現にした上で，回転オペレータを作って，比較オペレータを作る必要がありそうだ。正規化した表現もやっかいで，並べ替えをした上で，原点から出発するように移動することを考える
E: File Compression ★★★: 説明文がものすごく長いので，難しい問題に思えるが，実際には書かれた通りにプログラムを書いてみると，あっさりできてしまう。この問題は，英語読解の問題になってしまっている。

2001年函館大会

A: Get a Rectangular Field ★: Generate and Testの基本的な問題。２次元で６重ループを書かなければならないところが，前年より難しくなっているところ。この問題の解説はこちらにある（情報処理学会誌解説）。
B: Multi-column List ★★: 書かれたとおりにシミュレーションすればよいのだが，ページをまたいだときの動作など，少しコーディングに面倒なところがある。適切に関数わけするといったコーディングテクニックは必要だろう。
C: Jigsaw Puzzles for Computers ★★★: バックトラックの問題。前年よりは回転する操作があるだけ難しくはなっているが，それほど難しい問題ではない。問題文に，いろいろと条件が書いてあり，それが問題をやさしくする条件になっているのだが，そのことがわからない学生がいるかもしれない。この問題の解説はこちらにある（情報処理学会誌解説）。
D: Missing Numbers ★★: 自分でアルゴリズムを考える必要があるが，やってみると，意外にできてしまう問題。文字と数字が混在する入力の取り扱いがやっかいなくらい。2問目に解く問題としては勇気がいる（アルゴリズムが間違っていたとっきのことを考えると）
E: Nets of Dice ★★★★: 今回の問題セットで一番難しいと思われる。全問正解のチームが２つあるので，それほど難しくないのかもしれないが。自分がプログラムを書いていないので，コメントはここまで。

2002年金沢大会

A: Exploring Caves ★: シミュレーションをして最大を求める問題。同じ距離のときの処理について，きちんと問題を読んでいれば，前年のＡより簡単。
B: Pile Up! ★★: オンラインジャッジの101番をもっと簡単にしたような問題。データ構造とその操作をきちんと書ければ大丈夫。
C: Kanglish : Analysis on Artificial Language ★★: 面倒くさいところはあるが，問題に書かれたとおりにプログラムを書けばよい。
D: What is the Number in my Mind ?
E: Enclosing Circles ★★★★★: この問題の解説はこちらにある（情報処理学会誌解説）。

2003年会津大会

A: When Can We Meet? ★: 基本的にはGenerate and Testで最大を調べる問題だが，配列にデータを入れるといった操作が必要な分だけ，前年までよりは難しい。
B: Get Many Persimmon Trees ★: 函館のA問題とほぼ同じで，大きさが可変。大きさをもう少し大きくして，計算量を考えさせるというくらいにした方が，問題の難易度としては適切だったのでは？
C: The Secret Number ★★★★(3.5): ついに国内予選にも動的計画法の問題が出現。バックトラックを使用せずに，動的計画法を使うことがわかるかどうかが勝負。
D: Building a Space Station ★★★★(3.5): グラフの最小木を作る問題。アルゴリズムを知っているかが勝負になっている。
E: Square Carpets ★★★★: この問題は1チームしかできていないので難しかったようだ。たしかに，バックトラックを使ってコーディングをすると時間がかかってだめである。色々と試行錯誤したあげくにできたプログラムは，むしろC，Dより簡単だと思われる。CやDはアルゴリズムがわかれば簡単に書けるのに対して，この問題はアルゴリズムを考えなければならない分，3時間のコンテストでは厄介だと考えられる。

2004年愛媛大会

出題言語：英語と日本語，時間：3時間（印刷トラブルがあったため，実際には15分延長されて3時間15分）。

2問目をやるために，ついにバックトラック(B)をやらなければならないことになった(C, D, E, FはBより明らかに難しい）。それでも，前年同様，A,Bがやさしすぎるため，AとBのスピード競争となってしまった。前年の経験が活きて，1チームがスピード競争に勝つことができた。Bをもうちょっと難しくするとか，Cをもう少しやさしくするかする必要があると考える。

A: Hanafuda Shuffle ★: やさしい問題だが，配列の添え字計算が面倒なように作ってある。
B: Red and Black ★★: バックトラックの中でもやさしい部類。塗りつぶす一方なので，再帰呼び出しから戻る処理がいらないのが，簡単な原因か。
C: Unit Fraction Partition ★★★(2.5): Bに続いてバックトラックの問題。3問以上の正解チームがそれほど多くないところを見ると，Bよりはかなり難しいかと思ったが，やったみたところではBよりはコードとしては短く書ける。
D: Circle and Points ★★★★(3.5): 基本的には総当り法だが，どのように総当りすべきか判断するところが難しい。あとは，お決まりだが，誤差の取り扱いに慣れていないといけない。
E: Water Tank ★★★★: いわゆるイベントシミュレーションをする（時間軸に沿って事象発生時刻を調べてシミュレーションを進めていく）問題。過去問では出てこなかったタイプだけに，苦労することが予想される。
F: Name the Crossing

2005年東京大会

出題言語：英語と日本語，時間：3時間。

AとCは，アルゴリズムを考えることはやさしいが，ちょっとしたコーディング能力が必要になっている。予選突破に必要となる3番目にやさしい問題(B)も，アルゴリズムの知識というよりはコーディング能力が試されている。D, Fはアルゴリズムを知っていれば，という問題だが，これも一工夫必要なので，アルゴリズムにそのままあてはめれば良い，というわけでもない。

A: Ohgas' Fortune ★: やさしいのだけど，基本的なコーディング能力が問われている。
B: Polygonal Line Search★★★(2.5): 線が複数から構成されている図形が同じかどうかを判定する問題。基準形を決めて，平行移動，回転をして比較するとよい。
C: Numeral System ★: やさしいのだけど，文字列に関する基本的なコーディング能力が問われている。
D: Traveling by Stagecoach★★★★: 都市間の距離が与えられて，ある都市と別の都市の最短移動時間を求める問題。旅行者には馬車券が与えられていて，馬車券に記されている馬車の頭数が複数あると，頭数分の１の移動時間で移動できる。馬車券がなければグラフの最短経路問題になる。
E: Earth Observation with a Mobile Robot Team
F: Cleaning Robot★★★★(3.5): 2次元上の迷路に置いてある，複数の「汚れたタイル」すべてをロボットが掃除するための，最短移動距離を求める問題。ダイクストラ法とバックトラックを組み合わせて，効率をよくする必要がありそうだ。

2006年横浜大会

出題言語：英語と日本語，時間：3時間。

3問正解しないと国内予選を通過しないが，A, B, DとC, E, Fの難易度があまりに違うので，A, B, D（特にDのバックトラック）ができなければ国内予選通過はままならない。C, E, Fは，アジア地区予選で戦える能力があるのか判定する，かなりタフな問題。これをアジア地区予選までに解けるレベルにしておけ，ということか。

A: Dirichlet's Theorem on Arithmetic Progressions ★(1.5): 素数のアルゴリズムを知らないといけないことだけが障害。このくらいの数の設定だと，下手くそな方法でも大丈夫そうだ。（当然だが，エラトステネスの篩を使えば良い）
B: Organize Your Train part II ★(1.5): 文字列を任意の箇所で2つに分割して，それぞれ反転するかしないか，そしてその結果を逆につなぐかどうかで計8通りの文字列を生成し，それが全部でいくつ組み合わせがあるか求める問題。C++ STLやJavaのように集合クラスが用意されているととてもやさしい。C言語しか使えないプログラマーは参加するな，ということか？
C: Hexerpents of Hexwamp
D: Curling 2.0 ★★(2.5): スタートからゴールまでの最短を求める問題。横型探索を使うのかと思いきや，10回より多くなったら無限大だと思え，ということなので，バックトラックを使って全探索（最大で4の10乗なので，およそ100万ノードを調べればよい）でも構わない。もちろん，過去の最短を超えれば枝刈りできるので，運が良ければかなり速い。実際には枝刈りしなくても問題ない。
E: The Genome Database of All Space Life ★★★★: 繰り返し数を使って圧縮してある文字列に対して，何文字目かを指定してその文字を出力する問題。括弧が使えるので，再帰的に調べていかなければならない。CやFよりはやさしいと思われるが，それでも慣れていないとかなり面倒な問題。
F: Secrets in Shadows

2007年東京大会

出題言語：英語と日本語，時間：3時間。

今回はアジア地区予選進出チームが40チームとしたため，3問正解チームを増やすことを狙ってか，A～Ｄの問題が易化。

A: ICPC Score Totalizer Software ★(0.5): 最大，最小，合計がわかれば解けてしまう，国内予選史上最もやさしい問題（練習セッション並）。3分台で正解が出るのもうなずける。
B: Analyzing Login/Logout Records ★(1.5): ある日の中で，学生たちが複数のPCをログイン，ログアウトした時刻のログが与えられたとき，ある学生が時間半以内に何分ログインしたかという質問に答える問題。学生と分ごとに，ログインしているPC数をカウントしていく配列を使えばよい。データ表現を考えることができればできる問題。
C: Cut the Cake ★★: 四角形のケーキを，カットしていき，最後に上から見た面積を小さい順に出現する問題。ケーキの番号付けを管理しやすくするためにリストデータ構造が必要。
D: Cliff Climbing ★★★★(3.5): 問題設定に工夫はされているが，結局は，複数出発点がある最短経路問題。典型的な問題だけに，アルゴリズムを知っていれば易しい。
E: Twirl Around
F: Dr. Podboq or: How We Became Asymmetric