国内予選講評

審判長 田中哲朗(東京大学)

2014年度の審判委員会 は 組織 Organizationのように,昨年度の委員15名のうち10名が留任し,新任4名,再任3名の計17名で組織されている. 新たに加わったメンバーを中心に,昨年度までと 傾向の異なる問題も提案された.

2014年度の国内予選では7問を出題した.表1に正解した問題数の分布を示す.今 年は,2チームが全問正解したが,そのうち1チームは3時間の競技時間のうち1 時間15分以上残し,一度も不正解を出さずに終了した.その一方で1問も正解で きないチームが全体の約1/3あり,問題セットの難易度調整の難しさを再確認させ られた.

表1: 正解した問題数
正解数76543210
チーム数271615337369111

問題ごとの提出チーム数・正解チーム数・最初の正解時間を表2に,正解した問題の組み合わせごとのチーム数を表3に示す.国内予 選では難易度を意識して出題順を決めているが,正解チーム数が出題順と一致 しているのは,前から順に解きたくなるという参加者の心理も関連しているか もしれない.

表2: 問題ごとの結果(全 326チーム)
問題分野提出チーム数正解チーム数最初の正解時間(秒)
A列挙240201314
Bシミュレーション178157659
C幾何72581466
D探索62491132
Eグラフ37341569
F貪欲法872355
G幾何646158

表3: 正解した問題の組み合わせごとのチーム数
解いた問題の組み合わせチーム数
ABCDEFG 2
ABCDEF 5
ABCDEG 2
ABCDE 16
ABCD 9
ABCE 3
ABDE 3
ABC 18
ABD 12
ABE 2
ACE 1
AB 72
AC 1
A 55
B 13
C 1

問題A. Tax Rate Changed / 税率変更

審判委員会は,ICPCに参加する意欲のあるチームのほとんどが時間内で 1問以上を解くことを期待して問題セットを作成する.単純にこの条件を満たす だけなら,リハーサルで使うような自明な問題を問題Aとして出題すれば良いこ とになるが,それでは問題を解いた時の楽しさを味わってもらうこともできな いし,問題Aだけ早く解けてしまい残りの時間に何もできずに終わってしまう チームばかりになってしまうおそれがあるので,そういうわけにもいかない. 毎年,問題Aの難易度は特に時間をかけて調整している.

その点でいうと,約1/3の参加者が解けなかった今年度の問題Aは難易度調整に失敗 したと言えるかもしれない. 

この問題の想定解法は古い税率で合計金額が整数sとなる商品の税抜価格の組を 列挙して,新しい税率での税込金額の和を求め,その最大値を答えるというも のである.sが1000未満なので,2重の繰り返しで列挙しても良いし,税込価格 から税抜価格を求めるためのテーブルを作ると1重の繰り返しで書ける.問題文 を正確に読む必要があるだけで,プログラミング自体としては,例年の問題Aと 比較しても難しくはなかったと思う.

しかし,税抜価格から税込価格を正しく計算する部分でつまずいたチームが多 かった.税込価格を p + (int)(p * 0.01 * x) ではなく (int)(p * (100 + x) / 100)と定義したことの意図を見抜けずに,誤差により結果が変わってしま うような式の変形をしてしまい,一部の入力に対して誤った出力を出すプログラムを作成してしまったというものだ.浮動小数点数の計算で誤差が出る計 算があることは講義で教わっているはずなので, 今回この問題を正解できなかった参加者は勉強し直していただきたい.

問題B. Chain Disappearance Puzzle / 連鎖消滅パズル

仕様通りに石を消すプログラムを正しく作成するだけで,特に悩むところはな いだろう.2次元配列で状態を正しく管理する以上のことは求めていない.提 出されたプログラムでの誤りは,配列の初期化忘れが目立った.Sample Inputでは初期化忘れがあっても,たまたま同じ結果になったものと思われる.

類似のパズルゲームがあるが,ルールは一部簡略化されている.難易度を落とす という目的もあったが,特定のゲームのルールを事前に知っていることで有利に なることを避けたかったのも理由になっている.

問題C. Vampire / バンパイア

日本語で問題文を読んだ大部分の参加者には,「ICPC」を「Immortal and Corpse Programmers Circle(不死者と死人のプログラマー同好会)」と読ませる 出題者の苦労に気づいてもらえなかったと思う.

想定解法は,建物のデータを元に同じ高さの区間に分解して,それぞれの区間 の上に太陽が出る時刻を求め,その最小値を答えるというものである.区間の 中ではx座標の絶対値が最小の点で最も早く太陽が出るので,その時刻を計算 すれば良い. 建物のx座標も太陽の半径rも整数なので,x座標が[-r,-r+1],[-r+1,-r+2],..,[r-1,r]のそれぞれ幅1の区間に分けて考えると,それぞれの区間での建物の高さは簡単に得られる.

時刻tでの太陽の中心を求め,中学数学で学んだとおりに距離がrになる時刻を2次方程式を解いて求めても良いし,同じく中学数学で学ぶピタゴラスの 定理に従って,区間から太陽が出るときの中心の位置を求め,それを時刻に換算 しても良い.

もちろん,区間の上に太陽が出る時刻を求めるよりも,ある 時刻で区間の上に太陽が出ているかの判定の方が易しいと考える場合は, 時刻による二分法で求めても良い.許容誤差を 0.001 と大きめに取ったため, 二分法ですらなく時刻を0.001ずつ増やしながら太陽の光が出るまで繰り返すプ ログラムを提出して通っているチームもあった.

問題D. Encryption System / 暗号化システム

復号で1通りにならないので「暗号化ではない」という意見もあったが当初の タイトルのままで押し切った.

i文字目は置換された文字(この時の文字は1通り)か,置換されていない文字かの2種類で文字列の長さ の最大値が20なので,元の文字列の候補は220を超えない. この最大220通りについて,問題の暗号化に従っているかどうか を判定するというのが想定解法になっている.

現在通常使われる計算機環境で,長さ20の文字列を220個保持する のは十分可能だが,文字列は最小の5個と最大の5個だけを残して,後は個数を数 えるだけでも構わない.

問題E. Bridge Removal / 橋の撤去

この問題は,島をノード,橋をエッジとする木で表すことができる.橋の長さは エッジの重みになる.

少し考えると,最小コストを実現する場合

のような行動をおこなえば良いことが分かる.この制約のもとでコストが最小となる 訪問パターンは動的計画法を用いれば実用的な時間で解けるが,もっと良い方法 がある.

最小コストは,「内部ノードとリーフを結ぶエッジの重みの和 + 内部ノードを結ぶエッジの重みの和 * 3 - 始点と終点を結ぶパス上のエッジの重みの和」なので, コストを最小化する問題は,始点と終点を結ぶパスの重みを最大化することになる. これは,木の直径を求める問題として知られていて,線形時間で求めることができるが, 開始ノードを決めて,他のすべてのノードへの距離を求める O(n2)の解法で解いても問題ない.

大部分の解答チームは,この解法で解いていた.

問題F. A Die Maker / サイコロ職人

この問題は元の設定ではなく,t1, t2, ... , t6 と 印された面からなるサイコロから初めて,回転するごとに数が1減るという設定で考えると分かりやすい.すべての面が0となる状態(以下,「ゴール」と書く)になることを「解ける」とする.このとき,手詰まり状態(それ以降どのような操作をおこなっても,解けない状態)かどうかを高速に判定することが必要になる.

サイコロの面で,A0とA1, B0とB1, C0とC1が対面とすると,操作列は,下に来るサイコロの面の列(以下では「面列」と書く)に変換できる.「面列」 は,ある面の次には対面以外の4つの面のいずれかが来るという性質がある.

ある状態から,ゴールに至る面列の中にA0とA1が現れる時,A0の 一つとA1の一つを取り替えても面列として成り立っていて,同様に ゴールに至ることが言える.

このため,ある状態が解けるかどうかは,A0とA1の数字を合わせたNA, B0とB1の数字を合わせたNB, C0とC1の数字を合わせ たNCと下に来ている面が,A, B, Cのいずれかで決まることが分かる.

このための必要条件の一つは容易に求まる.

今,Ai(i = 0 or 1)が下の面にある時,次はBかCであり,Aは続けて現れることはないので,

NA ≤ NB + NC
となる.同様に,BやCも続けて現れることはない(ただし,次がBで最後がBでも良い)ので,
NB ≤ 1 + NC + NA
NC ≤ 1 + NA + NB
が必要条件となる.

都合が良いことに,これは手詰まりでないことの十分条件にもなっている(証明は容易なので省略する).

この問題は,辞書順で最も前になる操作列を求める問題なので,手詰まり状態に ならない範囲でアルファベット順で最も前に来る操作を加えていけば目的の操作列が 得られる.初期配置が 6! = 720 通りあるので,それぞれに対応する操作列の最小値が答えになる. 

この条件に気が付かずに,手詰まりでない時だけ最大フローが想定する値にな るような最大フロー問題に変換して,手詰まり条件をチェックするプログラム を作成して正解したチームもいた.

問題G. Don't Cross the Circles! / 円を横切るな!

問題文を流し読みすると「円弧による平面の分割」を真面目に計算しなくては いけないと思うかもしれないが,良く読むと「3 つ以上の円が共通領域もしくは共通点を もつことはない」という条件があるので,それよりは易しい問題であることが わかる.

PQがいずれかの円に含まれている時は,それぞれを含む円(高々2個)の集合が 等しいことが,円弧と交差しないパスを持つための必要条件になる.更に, 「3 つ以上の円が共通領域もしくは共通点をもつことはない」ので,この条件 を満たした時に2点を結ぶパスがさえぎられることはなく,十分条件にもなって いるので,この条件だけで判定できる.

一方,円に含まれていない場所は,円弧によっていくつかの連結でな い領域に分けられるので,PQがどの円にも含まれていない場合は,同じ領 域に含まれるかを考える必要がある.

「円弧によって分けられた領域」を求めるのは面倒だが,「3 つ以上 の円が共通領域もしくは共通点をもつことはない」という前提があるので, 代わりに,交差する円の中心と中心を線分で結んでできる,線分の集合で 分けられた領域を考えて良いことがわかる.

線分で平面を領域分割する問題は,過去に2003年会津大会の問題H「Monster Trap」で 出題された.この解法については情報処理学会誌の2005年2月号で, プログラムプロムナード:怪物を閉じ込めるで解説されているが,領域の境界を左手法でなぞって 一周する操作を繰り返して領域を求めることができる.あとは, P, Qがどの領域に含まれているかどうか判定すれば良い. 図1のように領域が入れ子になっている場合もあるので,慎重に判定す る必要がある.


図1: 領域が入れ子になっている例

2003年会津大会で問題Hを解いたチームはいなかったので,この問題は難しすぎるのではないかという危惧もあったが,今回は国内予選の限られた時間内に4チームが正解してくれた. ICPC参加者のレベルが年々あがっていることを再確認させられる結果になった.