図1: 領域が入れ子になっている例
審判長 田中哲朗(東京大学)
2014年度の審判委員会 は 組織 Organizationのように，昨年度の委員15名のうち10名が留任し，新任4名，再任3名の計17名で組織されている． 新たに加わったメンバーを中心に，昨年度までと 傾向の異なる問題も提案された．2014年度の国内予選では7問を出題した．表1に正解した問題数の分布を示す．今 年は，2チームが全問正解したが，そのうち1チームは3時間の競技時間のうち1 時間15分以上残し，一度も不正解を出さずに終了した．その一方で1問も正解で きないチームが全体の約1/3あり，問題セットの難易度調整の難しさを再確認させ られた．
表1: 正解した問題数
| 正解数 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|
| チーム数 | 2 | 7 | 16 | 15 | 33 | 73 | 69 | 111 |
表2: 問題ごとの結果(全 326チーム)
| 問題 | 分野 | 提出チーム数 | 正解チーム数 | 最初の正解時間(秒) |
|---|---|---|---|---|
| A | 列挙 | 240 | 201 | 314 |
| B | シミュレーション | 178 | 157 | 659 |
| C | 幾何 | 72 | 58 | 1466 |
| D | 探索 | 62 | 49 | 1132 |
| E | グラフ | 37 | 34 | 1569 |
| F | 貪欲法 | 8 | 7 | 2355 |
| G | 幾何 | 6 | 4 | 6158 |
表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 |
その点でいうと，約1/3の参加者が解けなかった今年度の問題Aは難易度調整に失敗 したと言えるかもしれない．
この問題の想定解法は古い税率で合計金額が整数sとなる商品の税抜価格の組を 列挙して，新しい税率での税込金額の和を求め，その最大値を答えるというも のである．sが1000未満なので，2重の繰り返しで列挙しても良いし，税込価格 から税抜価格を求めるためのテーブルを作ると1重の繰り返しで書ける．問題文 を正確に読む必要があるだけで，プログラミング自体としては，例年の問題Aと 比較しても難しくはなかったと思う．
しかし，税抜価格から税込価格を正しく計算する部分でつまずいたチームが多 かった．税込価格を p + (int)(p * 0.01 * x) ではなく (int)(p * (100 + x) / 100)と定義したことの意図を見抜けずに，誤差により結果が変わってしま うような式の変形をしてしまい，一部の入力に対して誤った出力を出すプログラムを作成してしまったというものだ．浮動小数点数の計算で誤差が出る計 算があることは講義で教わっているはずなので， 今回この問題を正解できなかった参加者は勉強し直していただきたい．
類似のパズルゲームがあるが，ルールは一部簡略化されている．難易度を落とす という目的もあったが，特定のゲームのルールを事前に知っていることで有利に なることを避けたかったのも理由になっている．
想定解法は，建物のデータを元に同じ高さの区間に分解して，それぞれの区間 の上に太陽が出る時刻を求め，その最小値を答えるというものである．区間の 中ではx座標の絶対値が最小の点で最も早く太陽が出るので，その時刻を計算 すれば良い． 建物のx座標も太陽の半径rも整数なので，x座標が[-r,-r+1],[-r+1,-r+2],..,[r-1,r]のそれぞれ幅1の区間に分けて考えると，それぞれの区間での建物の高さは簡単に得られる．
時刻tでの太陽の中心を求め，中学数学で学んだとおりに距離がrになる時刻を2次方程式を解いて求めても良いし，同じく中学数学で学ぶピタゴラスの 定理に従って，区間から太陽が出るときの中心の位置を求め，それを時刻に換算 しても良い．
もちろん，区間の上に太陽が出る時刻を求めるよりも，ある 時刻で区間の上に太陽が出ているかの判定の方が易しいと考える場合は， 時刻による二分法で求めても良い．許容誤差を 0.001 と大きめに取ったため， 二分法ですらなく時刻を0.001ずつ増やしながら太陽の光が出るまで繰り返すプ ログラムを提出して通っているチームもあった．
i文字目は置換された文字(この時の文字は1通り)か，置換されていない文字かの2種類で文字列の長さ の最大値が20なので，元の文字列の候補は220を超えない． この最大220通りについて，問題の暗号化に従っているかどうか を判定するというのが想定解法になっている．
現在通常使われる計算機環境で，長さ20の文字列を220個保持する のは十分可能だが，文字列は最小の5個と最大の5個だけを残して，後は個数を数 えるだけでも構わない．
少し考えると，最小コストを実現する場合
最小コストは，「内部ノードとリーフを結ぶエッジの重みの和 + 内部ノードを結ぶエッジの重みの和 * 3 - 始点と終点を結ぶパス上のエッジの重みの和」なので， コストを最小化する問題は，始点と終点を結ぶパスの重みを最大化することになる． これは，木の直径を求める問題として知られていて，線形時間で求めることができるが， 開始ノードを決めて，他のすべてのノードへの距離を求める O(n2)の解法で解いても問題ない．
大部分の解答チームは，この解法で解いていた．
サイコロの面で，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 通りあるので，それぞれに対応する操作列の最小値が答えになる．
この条件に気が付かずに，手詰まりでない時だけ最大フローが想定する値にな るような最大フロー問題に変換して，手詰まり条件をチェックするプログラム を作成して正解したチームもいた．
PとQがいずれかの円に含まれている時は，それぞれを含む円(高々2個)の集合が 等しいことが，円弧と交差しないパスを持つための必要条件になる．更に， 「3 つ以上の円が共通領域もしくは共通点をもつことはない」ので，この条件 を満たした時に2点を結ぶパスがさえぎられることはなく，十分条件にもなって いるので，この条件だけで判定できる．
一方，円に含まれていない場所は，円弧によっていくつかの連結でな い領域に分けられるので，PとQがどの円にも含まれていない場合は，同じ領 域に含まれるかを考える必要がある．
「円弧によって分けられた領域」を求めるのは面倒だが，「3 つ以上 の円が共通領域もしくは共通点をもつことはない」という前提があるので， 代わりに，交差する円の中心と中心を線分で結んでできる，線分の集合で 分けられた領域を考えて良いことがわかる．
線分で平面を領域分割する問題は，過去に2003年会津大会の問題H「Monster Trap」で 出題された．この解法については情報処理学会誌の2005年2月号で， プログラムプロムナード:怪物を閉じ込めるで解説されているが，領域の境界を左手法でなぞって 一周する操作を繰り返して領域を求めることができる．あとは， P, Qがどの領域に含まれているかどうか判定すれば良い． 図1のように領域が入れ子になっている場合もあるので，慎重に判定す る必要がある．
図1: 領域が入れ子になっている例
2003年会津大会で問題Hを解いたチームはいなかったので，この問題は難しすぎるのではないかという危惧もあったが，今回は国内予選の限られた時間内に4チームが正解してくれた． ICPC参加者のレベルが年々あがっていることを再確認させられる結果になった．