審判長 石畑 清（明治大学）
昨年までの国内予選の問題数は 7 だったが，2015 年度は 8 問に増やした。 国内予選に参加するチームのレベルが上がってきて， 7 問では全問正解される恐れが大きいということが理由の一つだが， ほかに，予選通過を競うレベルのチームが得意な分野の問題を選べるように， 選択の幅を広げるということも考えていた。 去年までの出題数では， それを解ければ予選通過となるというボーダーラインの問題が一つに限られ， その分野を不得意とするチームが不利になる可能性が小さくなかった。
表 1 に正解した問題数ごとのチーム数を示す。 「解いた問題の内訳」は， 正解した問題の組み合わせごとのチーム数をまとめたものである。 表 2 には，問題ごとの提出チーム数，正解チーム数，最初の正解時間を示す。
表1: 正解した問題数
| 正解数 | チーム数 | 解いた問題の内訳 |
|---|---|---|
| 8 | 0 | |
| 7 | 1 | ABCDEFG : 1 |
| 6 | 1 | ABCDEF : 1 |
| 5 | 10 | ABCDE : 7 ABCDF : 3 |
| 4 | 16 | ABCD : 12 ABCE : 2 ABCF : 1 ABCH : 1 |
| 3 | 105 | ABC : 105 |
| 2 | 124 | AB : 122 AC : 1 AD : 1 |
| 1 | 59 | A : 57 B : 2 |
| 0 | 56 |
表2: 問題ごとの結果(全 372チーム)
| 問題 | 提出チーム数 | 正解チーム数 | 最初の正解時間(秒) |
|---|---|---|---|
| A | 342 | 314 | 325 |
| B | 270 | 257 | 648 |
| C | 147 | 134 | 1108 |
| D | 46 | 25 | 3681 |
| E | 18 | 11 | 2882 |
| F | 7 | 6 | 5786 |
| G | 1 | 1 | 9788 |
| H | 1 | 1 | 9991 |
今年は，全問正解したチームがなく，トップのチームが 7 問正解だった。 これは，審判団の目論見どおりである。 また，A〜H の全問題をそれぞれ 1 チーム以上が解いたことも， 審判団としてうれしい結果であった。
昨年と一昨年は，問題 A の正解数が 200 を少し上回る程度にとどまり， 全チームのおよそ 1/3 が 1 問も解けなかった。 アジアからの世界大会出場枠を各国に配分する計算では， 参加チーム数が重要なパラメーターになるのだが， 1 問も解けなかったチームは，不参加と区別ができないので， 勘定に入れないことになっている。 1 問も解けないチームが多いと，日本にとって損になるので， なるべく少なくすることが望ましい。 今年は，このことを意識して，問題 A を極力やさしくすることに努めた。 結果は，ほぼ想定どおりだったと言える。
問題 B と C の正解数は，審判団が想定していたよりもかなり多かった。 好結果だったと考えている。 一方，問題 D の正解数が 25 にとどまったのは想定外だった。 もう少しやさしい問題のつもりだったが， 解法の設計もプログラミングも実は難しかったということだろう。 審判団にとっても，問題の難易度を正確に判定することは難しい。 問題 E 以降も，想定したよりは正解数が少なかった。 問題 D で足止めされたチームが多かったからではないかと考えている。
上に述べたように，この問題は， プログラミングをしたことのある人なら誰でも解けるレベルをねらって作題した。 得点がソートして与えられているので， 隣の値との差の最大値を求めるだけでよい。 必要なのは一重のループだけであり， 初歩的プログラミングの演習問題レベルの問題だと言えよう。 解けなかったチームは，コンテスト独特の問題文の書き方に慣れず， 解読に苦労したのではないかと想像している。
この問題を解けなかったのは 58 チームだが， そのうち 30 チームは 1 回も解答を送ってきていない。 残る 28 チームのうち，18 チームは誤答ばかりだったが， 10 チームは少なくとも一度は Correct answer の結果を得ている。 二つ目のデータに同じプログラムで正解しなければならないというルールを正しく理解していないチームが相当数あるようだ。
単語列の初めから順に短句の先頭位置を動かしていき， その場所から始まる単語列が短句の規則を満たしているかどうか判定するだけでよい。 短句の規則を満たすかどうかの判定のループの書き方に少しだけ工夫が必要だが， 難易度の点で問題 A と大きく違うわけではない。
例年の問題 B と比べれば，かなりやさしかったようだ。 解けたチームの数が全チーム数の 2/3 を超えている。 これは，国内予選の問題 B としては近年なかったことである。
この問題の解法は，さまざまな考え方のものが可能である。 普通に思いつくのは，再帰下降法などの構文解析の技法を適用することだろう。 この場合は，式の計算を行う関数（メソッド）を用意して， 演算子を検出するたびに，この関数を再帰呼び出しすることになる。 ピリオドの個数の少ない行が現れたら，関数から戻るようにすればよい。
もっと簡単な解法も可能である。 初めに，式を表すデータセット全体を読み込んでおいて， 下から上に逆向きに調べていけばよい。 全部の行の読み込みが済んでいれば， 被演算子それぞれにどの演算子が適用されるかは簡単に調べられる。 被演算子を計算した結果の値を演算子の所に集めて， 加算または乗算の計算をする。 この操作を下から上に順次適用していけば解ける。
およそ 4 割のチームがこの問題を解いた。 これも近年にない好成績で，審判団の予想を越えていた。
それぞれの店で買うか買わないかの選択は， 全部で 2n とおりある。 n が最大 100 になるので， これだけの組み合わせをすべて調べるような解法は時間がかかりすぎて無理である。 動的計画法（以下 DP と略す）を適用すべき問題であることはすぐに分かると思う。 問題は，DP の表のインデックスを何にするか， また表の要素としてどんな値を記録するかである。 記録する値の選び方の巧拙で，計算量が大きく変わる。
問題文には，無駄な小銭の使い方をしてもよいと書いてある。 店に渡す金額を決めたら，どんな小銭を何枚出すかは考えなくてよい。 したがって，小銭の総額だけが問題で， 1 円玉の枚数，5 円玉の枚数，... のように細かく把握する必要はない。 この事実に気づくことがこの問題を解くための第一歩である。 さらに，もう少し考えれば， DP のインデックスは手持ちの小銭の総額とすればよいことが分かるだろう。 店での行動を決める鍵は，手持ちの小銭の額だからである。 たとえば 700 円の土産物を買うときに 500 円玉が得られるかどうかは手持ちの小銭が 200 円以上かどうかで決まることを思い出してほしい。
比較的簡単に思いつくのは，DP のインデックスとして， 手持ちの小銭の総額のほかに，得た 500 円玉の枚数をとり， 2 次元のインデックスとする解法である。 表の要素には，その額の小銭を残し， その枚数の 500 円玉を入手するのに必要な消費金額の最小値を入れる。 この表を店を一つずつ進みながら更新していけばよい。 金額を 1000 で割った余りが 1 以上 500 以下なら， 1000 円札だけ出して 500 円玉 1 枚と小銭を得るのが常に最善である。 それ以外の金額の場合は，(1) その店では買わない選択， (2) 小銭を出して 500 円玉を得る選択， (3) 500 円玉の入手を諦め 1000 円札だけ出して小銭を得る選択，の三つがある。 これらの選択それぞれに合わせて DP の表を更新する。 この方法の計算量は， x = 500 として O(n3x) である。 n = 100 なので，これでも十分に間に合う。 ただし，判定用データ 1 組の処理に 1 分前後の時間がかかるようだ。 実は，選択 (2) が可能なら選択 (3) を考える必要はないのだが， このことに気づかなくても計算時間が大きく変わることはない。
より高速な解法は，表の要素を 500 円玉の枚数と消費金額のペアとすることである。 インデックスは小銭の総額だけの 1 次元とする。 500 円玉が多いほどよく， 500 円玉の枚数が同じときは消費金額が少ないほどよいのだから， 二つの方策の優劣は， 500 円玉の枚数と消費金額のペアを辞書式比較（枚数と金額で大小の向きが逆）すれば判定できる。 この意味での最善の方策の結果だけを常に残すようにすればよい。 この方法なら O(n2x) の計算量で済む。
s をロックの集合，t をロックとする。 s に属するロックすべてを保持していて t を獲得しようとするスレッド（またはスレッド群）が存在する可能性があることを P(s, t) と表記することにする。 たとえば，命令列が 012u であれば， P({ }, 0)，P({ 0 }, 1)， P({ 0, 1 }, 2) が成り立つ。 P(s, t) を表現するデータ構造を作り， すべての可能性を尽くすまで順次更新していく。 こうして完成したデータ構造の上で， デッドロックの可能性があるかどうか調べるのが基本的な解法である。 このような考え方を採れば， 計算にそれほどの時間はかからないようだ。 計算量の見積もりは容易でないが， 命令列の長さ n にほとんど依存しない点がポイントである。
P(s1, t1) と P(s2, t2) が成立しているとする。 s1 ∩ s2 = ∅， t1 ∈ s2 が成立している場合， 二つのスレッドをあわせて考えれば P(s1 ∪ s2, t2) が成立していると考えることができる。 この規則を繰り返し適用して， P(s, t) を満たす s と t の組み合わせをすべて見つける。 デッドロックの可能性の有無は， s1 ∩ s2 = ∅， t1 ∈ s2， t2 ∈ s1 がすべて成立するような P(s1, t1) と P(s2, t2) が存在するかどうかで判定できる。 存在すればデッドロックの可能性がある。
想定解法は次のとおりである。 ある定数 a を定めて，A 社の橋の費用をすべて a だけ増やす。 こうして作られたグラフの上で最小全域木（以下 MST と呼ぶ）を求める。 求まった MST に A 社の橋がちょうど k 本含まれていたら， その MST が元の問題の解になっている。 元の木に対して改めてコスト計算を行えばよい。 求まった MST の中の A 社の橋が少なすぎれば a を小さくし， 多すぎれば a を大きくする。 二分探索の要領で a を動かしていけば解ける。
ほかに，次のような解法も可能である。 与えられたグラフの MST を求める。 A 社の橋が少なすぎたら， MST に含まれている B 社の橋と MST に含まれていない A 社の橋を交換する （B 社の橋を除いて A 社の橋を加える）。 A 社の橋が多すぎる場合は，逆向きの交換をする。 当然ながら，そうしたやり方の中で， グラフの連結性を保ちつつコストを最小にする組を選んで交換しなければならない。 この操作を A 社の橋の本数がちょうど k になるまで続ければよい。
いずれの解法も，そのような方法で解けることを理解するだけでも大変な難問である。 ただし，二つめの解法なら， 本当に解けるかどうか自信がないままプログラムを書いてみたら通ってしまったというチームがあるかも知れない。 ほかに DP による解法も可能だが，単純にプログラムを書くと計算量が O(m4) になって遅すぎる。 O(m3) の計算量でおさまるように工夫してプログラムを書くことが必要である。
与えられた図形の二つの頂点を重ねるように折るのだから， その二つの点を結ぶ線分の垂直二等分線で図形を切って， 片方をもう片方の上に重ねることになる。 二つの図形はそれぞれ凸だから， 凸図形と凸図形の union を求めることができればよい。
幾何の問題である。 コンテストでは幾何の問題が 1 問は必ず出るが， それを短時間で解くにはそれなりの準備が必要である。 図形の基本的な操作，たとえば直線と直線の交点を求める操作を， コンテストが始まってから考えてプログラミングするのでは時間がかかりすぎる。 事前に考えた数式なりプログラム片なりをノートしたものを手元に置くようにするとよいだろう。
このような準備ができていれば， 凸図形と凸図形の union を求める操作の実現はそれほど難しくない。 辺と辺の交点をすべて求めておいて，二つの図形の頂点とあわせて考えることにする。 折れ目の上の点から出発して， これらの点の中で union 図形の一番外側になるものを順にたどっていけばよい。 ただし，難しくないと言ったのは， 計算誤差が絶対に生じないという理想的環境での話である。 実際には，計算誤差があるため，本来なら辺に頂点がちょうど乗るケースを， ほんの少し辺の内側や外側だと判断することがある。 この違いが出来上がりの図形の頂点数に影響するため， 不正確な判断のまま進めると間違った答になってしまう。 このように考えていくと， 頂点数最大を条件とする問題が意地悪であることに気づくだろう。 周長最大だけが条件なら，誤差に関するこのような心配は不要であった。
誤差に関する心配を一掃するには， すべての計算を実数ではなく有理数を使って行うようにすればよい。 審判が書いたプログラムにも，この方針を採ったものがいくつかある。 しかし，実際のコンテストの場では， プログラミングが面倒になりすぎるかも知れない。 実数計算で正しく解くには，結局のところ， さまざまなケースを想定して注意深くプログラミングするしかないようだ。 問題中の図 4(b) などが最も注意を要するケースである。
問題には，union をとった後の出来上がりの図形に関する制約条件が与えられている。 頂点間の距離が 0.00001 以上であること， 三つの連続する頂点 P，Q，R に関して Q と PR の距離が 0.00001 以上であること， の二つである。 この制約条件を利用して，誤差対策を部分的に簡単にすることはできる。 一方の図形の頂点がもう一方の図形の辺よりほんの少しだけ外に出ているという計算結果になったら， 誤差によるものだと判断して，頂点が辺に乗っていると判断して差し支えない。 しかし，制約を利用しても， 図 4(b) などのケースを考慮する必要がなくなるわけではない。
日本の ICPC の幾何問題では， 誤差の心配が生じるような微妙なケースは起こらないように制約を与えるのが普通である。 この問題の制約は，これと同じ方針のように見えるが，実は少し違っている。 微妙なケースが起こったときに，一方の解釈に決めてよいと言っているだけで， 微妙なケースが起こる可能性自体を排除してはいないのである。
(1) それぞれのロボットを最上階まで到達させる操作と， (2) 最上階で全ロボットを 1 箇所に集める操作， の二つに分けて考えることができる。 いずれの操作も，最善となる可能性のある位置のリストを作り， ひたすらエネルギー消費量の計算を繰り返すだけだが， 下手なやり方では候補として考えるべき位置が多くなって，時間がかかりすぎる。 候補位置をいかに少なくおさえるかがポイントである。
まず，各ロボットを最上階に到達させる操作から考えよう。 p 階でロボットの位置として考える価値のあるもののリストを Ap とする。 最初にロボットがいる階 z での Az は， 初期位置 (x, y) だけからなる。 それより上の階では， Ap−1 に含まれるそれぞれの位置 Q に対して， p 階の穴それぞれの中で Q に最も近い位置を Ap に加えていけばよい。 最も近い位置は，穴の四隅になる場合が多いが， Q から真っ直ぐに移動するだけで穴にぶつかる場合はぶつかった位置だし， Q が穴の真下にある場合は Q の位置そのものである。 この操作を繰り返して最上階まで達すると， 候補位置の数が穴の数を指数とする指数関数のオーダーになりそうだが， そうはならない。 候補位置の x 座標と y 座標は，出発点の座標か， どれかの穴の上下左右の端の座標かのいずれかである。 したがって，候補位置が 101×101 個より多くなることはない。
この方法で十分だが，さらに候補の数を減らすことが可能である。 Ap を作った後で， それに含まれる二つの候補位置 Q と R を比較する。 Q のエネルギー消費量が ( R のエネルギー消費量 ＋ Q-R のマンハッタン距離 ) 以上であれば， Q を候補に残す価値はない。 このような位置を切り捨てることによって，候補のリストが大幅に圧縮される。
最上階では，ロボットの集合場所として考える必要のある位置のリストが決まれば， それらの位置に各ロボットを到達させてみて， エネルギー消費量の合計を計算するだけで問題が解ける。 集合場所としてどんな位置を考える必要があるか， 図形的推論で判断しようとすると， 穴と穴が隣接する可能性があるので難しいが， x 座標と y 座標のそれぞれについて意味のあるものを残し， それらすべての x と y を組み合わせたものを考えれば間違いがない。 x 座標として考える必要があるのは，最大限に見積もっても， それぞれのロボットの初期位置，すべての階の穴の左右の端， 最上階の穴の左端の一つ左，最上階の穴の右端の一つ右だけであり， 300 個以下である。 y も同様であり， x と y を組み合わせても 90000 個でおさえられる。