国内予選講評
2016/07/01 ACM ICPC 2016 つくば大会 審判長 近山 隆
2016 年度の国内予選は前年度と同様 8 問を出題した。予選通過を競う最後の 1 問の選択にある程度の自由度を与えるには、この程度の問題数が必要と考えている。
表 1 に正解した問題数ごとのチーム数を示す。
「内訳」は、正解した問題の組み合わせごとのチーム数をまとめたものである。
表 2 には、問題ごとの提出チーム数、正解チーム数、最初の正解時間を示す。
| 表1: 正解した問題数 | 表2: 問題ごとの結果(全 384チーム) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
作題にあたっては、予選通過ラインが出題数の半分の 4 問正解程度となることを狙って難易度を調整したが、これはほぼうまくいったようだ。
昨年と同様に問題 A をやさしくすることに努め、その結果多くのチームが少なくとも 1 問は正解できた。一方、これも昨年と同様、全問正解したチームはなく、トップのチームが 7 問正解だった。計算幾何と見て着手をためらったチームが多かったのか、問題 E の正解が 19 にとどまったのはやや残念だった。問題 G の正解がなかったのは、解法の方針までは立っても、その実装が容易でなかったからだろうか。 問題 F も実装の手間がやや大きく、そこで時間を使い果たしたチームが多かったかもしれない。
以下、個別の問題について論じる。
問題 A. Selection of Participants of an Experiment / 被験者の選定
この問題は、プログラミングの初歩を学べば誰でも解けるレベルをねらって作題した。
成績リストの中でもっとも近いものを見つければ良いので、単純に 2 学生の成績のすべての組合せ n×(n-1)/2 通りについて、差の絶対値が最小になるものを見つける二重ループを使えば解ける。この方法だと計算量は O(n2) と非効率だが、学生数が1000以下なら問題ない。
全体をソートしてから隣り合うふたつの差の最小値を見つける方が、計算量を O(n log n) と小さくできる。標準ライブラリのソート機能を使えれば、むしろこちらの方が簡潔に書けるだろう。
誤答の多くは最小値を保持する変数の初期値の問題 (初期化忘れや小さすぎる初期値)や、繰り返しの範囲の間違いだったようだ。標準ライブラリを使わずに自前のソートを書こうとして苦労していたチームもあった。ソーティングの方法を学んだのはよかったが、再利用がソフトウェア生産性向上の鍵であることも知るべきだ。
また、解答を 1 回しか送らない、解答出力ではなくコンパイル結果のバイナリプログラムを送るなど、国内予選システムの使い方の理解不足も例年通り少なくない。せっかくエントリし、正解を出す実力もありながら、そんなところでひっかかるのはもったいない。特に初参加者は、当日昼休み時間帯に実施しているリハーサルに参加して、予選システムの使い方に習熟しておきたい。
問題 B. Look for the Winner! / 当選者を探せ!
開票中のある時点で、残る未開票分がすべて得票数 2 位の候補に投じられても、その時点でのトップの候補者に及ばないのなら、トップの得票者の当選が決まる。このことさえ理解できれば、トップと 2 位の開票済得票数の差と、未開票の票数を比較すればよいことがわかるだろう。
各候補の得票数の表を作って 1 票開票するごとに足しこんでいき、1 位と 2 位の候補をおぼえておいて、開票ごとに逆転が起きていないか調べて行けば、計算量は O(n) で済む。1 位と 2 位だけでなく、2 位と 3 位の逆転も考えねばならないが、得票数が減ることはないのだから、票が入った候補者が単独 2 位になるかだけに気をつければよく、3 位が誰なのかをおぼえておく必要はない。
投票数は最大 100 と小さいので、1 票開票するごとに全候補者の得票数を調べ、1 位と 2 位の候補の得票数を知る、という計算量 O(n2) の方法でも、計算時間がかかりすぎることはあるまい。さらに、毎回ソートしてしまう O(n2 log n) の方法でも十分で、この方がライブラリを使いやすいかもしれない。
データ量の上界がわかっているのなら、必要以上の高速化に手間をかけないのも重要な技倆である。将来大きなデータ量を扱うだろうことを予想できなかったのではないか、という疑念を抱かせる商用ソフトウェアも少なくないのだが。
この問題については途中までなかなか正解数が増えず、審判団をやきもきさせたが、結局正解が 200 を越えてほっとした。当選が決まる条件に気付くのが意外に難しかったのかもしれない。
問題 C. Bamboo Blossoms / 竹の花
素数の概念を拡張し「自分自身以外に m 以上の約数を持たない m 以上の自然数」を m-素数と呼ぶことにする。普通の素数は 2-素数である。この問題は n+1 番目の m-素数を求めよ、と言い換えることができる。
m 以上の自然数 k について、 k 未満のすべての m-素数で割り切れるかを試し、どれでも割り切れなければ m-素数である。しかしこの方法では、 n+1 個目の m-素数 u までの数を、最大 n 個の m-素数で割ってみることになる。Output for the Sample Input にも示したように、n = 500,000 では この u は 7 × 106 を超え、この単純な方法でコンテスト時間内に計算を終えるのは難しい。
素数を数え上げる効率的方法にエラトステネスのふるいがある。これに倣って、 u の最大値を超える論理値の配列を用意し、 m-素数の倍数をマークしていく方法が考えられる。107 ビット程度の配列なら十分メモリに収まるだろう。時間計算量も O(u log log u) と、u に対してほぼ線形で済む。
問題セット全体を通しての難易度調整の結果、この問題では u の最大値を問題中に示すことにした。これがなくても対処するのはさほど難しくもない。その定義から m-素数は m 以上の普通の意味の素数をすべて含む。だから m 以上の普通の意味の素数のうちの n+1 番目のものよりも、 n+1 番目の m-素数の方が小さい。 m 未満の素数はもちろん m よりも数少ないから、n+1 番目の m-素数は n+m+1 番目の普通の意味の素数より小さいはずである。x 以下の素数の個数を x / ln x で近似できる、という素数定理から、 u をおおよそ見積ることができる。もちろん近似に過ぎないので、途中で足りないことがわかるかもしれないが、そのときはたとえば倍に拡張するなどしてやり直せば良い。
既知の m-素数の倍数かを調べるために、 m-素数の倍数をあらかじめ求めておく方法も考えられる。ある自然数 k 未満の m-素数の集合 Pm, k は有限集合である。その要素 p の倍数の集合は無限だが、 k が j × p より大きくなるまで、 (j + 1) × p と等しくはならない。だから、 Pm, k の要素の倍数のうち k 以上になる最小のものだけ考えればよい。その個数は Pm, k の要素数と同じである。
既知の m-素数と次に調べるべきその倍数との組を優先度付きキューに蓄える。倍数の方が小さいほど高優先度とする。 k がキューの先頭と一致しなければ、 k は m-素数であるとわかり、キューにこの k と 2 × k の組を挿入する。キューの先頭の j × p と一致するなら、 k は m-素数ではない。この場合はキューの先頭は取り出して、代わりに ( j + 1) × p つまり j × p + p を追加しておく。先頭から複数が一致する可能性があるのに注意。優先度付きキューをヒープ構造で実装すれば、この方法の時間計算量は O(log n × u log log u) で抑えられ、空間計算量は O(n) で済む。
この問題の正解数の伸びは、審判団の予想よりも早かった。通常の素数の場合と同様にエラトステネスのふるいを使えばよい、ということに気付くのは、さほど難しくなかったようだ。
問題 D. Daruma Otoshi / ダルマ落とし
叩き出せる隣り合ったブロックを片っ端から除いていくのでは、もちろん最適にならない。問題中の図に示した重さ 1, 2, 3, 1 の場合でも、1-2 の組を落としてしまうと、後には 3 と 1 が残ってしまう。図に示したように 2-3 を先に除けば、全部取り除くことができる。
解法としては、どういう取り除き方ができるかをボトムアップに数え上げ、その中からどういう組合せを使うのが一番よいかを求める、という 2 フェーズに分けることが考えられる。
ブロックに一連番号を振って「i 番から j 番まで取り除ける」といったことを記録する。 i 番から j 番まで取り除けるとき、 i -1 番と j +1 番の重さの差が1以内なら、 i -1番から j +1番まで取り除ける。また、i 番から j 番までと j +1 番から k 番までが取り除けるのなら、 i 番から k 番まで取り除けることになる。取り除き方の総数は O(n2) である。新たに連続ブロックが取り除けることがわかるたびに、その範囲を拡張できないか調べる。つまり、連続ブロックを取り除いた跡に隣り合うことになるふたつのブロックが一緒に叩き落とせる重量差ではないか、あるいは連続ブロックに隣接する既知の取り除ける連続ブロックと連結できないか、を調べる。この単純な方法でも計算量は O(n3) におさまり、 n ≤ 300 ならまったく問題ない。取り除ける連続するブロックの並びを 2 個、4 個、6個、… とダイナミックプログラミングの手法で広げていってもよい。こうして取り除ける範囲を調べあげた上で、それらをどう組合せれば最も多く落とせるかを調べれば良い。
この問題の正解数がほぼ想定通りになったことによって、予選通過ボーダーラインも想定通りになったわけである。
問題 E. 3D Printing / 3Dプリント
どの立方体も高々 2 個の立方体としか共通部分を持たないのだから、立方体の連鎖や連環はいくつかできても、枝分かれするような形状になることはない。立方体の連鎖や連環のうちの k 個からなる部分列について、表面積が最小になるものを求めれば良い。立方体の列あるいは環のどこかから始めて k 個をつないだものの表面積を求め、あとはひとつずつずらして表面積の増減を計算していけば良いので、この部分は計算量 O(k×n) でできる。
計算がたいへんなのは、多数の立方体がどのように共通部分を持つかを知ることである。総当りで調べると O(n2) の計算が必要になる。この問題では幸いにして n は最大 2000 にしかならないのだから、総当りで計算するのでも大丈夫だ。
なお、立方体の総数がもっと多い場合には、 O(n2) の計算は無理になるが、そのような場合でも対処する方法はある。空間を立方体と同じ１辺 s の格子状のセルに区切って、各立方体がどのセルに重なるかをハッシュ表に登録していく。連結する立方体は、同じセルに重なっているはずであり、ひとつの立方体が重なるセルは、最大 8 個である。立方体がセルと重なる場合、セルの 8 隅の少なくともひとつを含むはずだ。3 個以上の立方体が共通部分を持つことはないのだから、ひと隅を共有できる立方体は高々 2 個、したがってひとつのセルにかかる立方体の総数は高々 16 個である。高々 8n 個の空でないセルについて、高々 16×15 回の総当り検査をすればよい。係数は少し大きくなったが O(n) の計算量である。
このように空間を格子分割する手法は計算幾何アルゴリズムの常套手段のひとつだが、思いつくのがそう簡単でなかろうと考え、ここでは n の上界を小さめに設定した。他に幾何の問題特有の面倒な点もないので、さほど難しくはなかったはずである。それでも正解数が伸びなかったのは、一見して計算幾何が主題の問題と錯覚したチームが多かったからだろう。
誤答は、立方体が環状に連鎖する場合の扱いに関するものが多かったが、すぐ問題点に気付いて修正し、正答に至ったチームが多かったようだ。
問題 F. Deciphering Characters / 文字解読
ふたつの二値画像について、4 近傍でつながる白ピクセルの領域と、8 近傍でつながる黒ピクセル領域の包含関係が同じであるかを問う問題である。画像を平面連続体の表現と考えるなら、両者が位相同型であるかを問うことになる。最外側は白なのだから、この包含関係は最外側の白領域を根とする木構造になっている。木の枝の順序に意味はない。この木構造を抽出し、ふたつの画像の木構造が同じになっているかを判定する、という 2 段階で解くことになろう。
領域の木構造を作る前に、まずどのピクセルが同じ領域に属すのかを決める必要がある。これには、どこかのピクセルから始めて 4 近傍（白）あるいは 8 近傍（黒）の隣接ピクセルを追いかけていけば良い。領域未決定のピクセルのリストを保持するなどすれば、これは O(h×w) の手間でできる。
次に、領域の隣接関係を決める。これは各領域内のピクセルが他のどの領域のピクセルと隣接するかを探せば良いだけで、やはり O(h×w) の手間である。
最後に、階層関係を明らかにする。まず画像の外側の白とつながっている領域から始める。それと隣接する黒領域はすべて、最外側白領域の部分木の根である。部分木の根である黒領域と隣接し、まだ階層が決まっていない白領域は、その黒領域の部分木の根である。これを再帰的に適用していけば、領域の総数に比例する手間で階層関係を決められる。
木構造が抽出できれば、残る仕事はふたつの木構造の同値性の判定である。適宜半順序を定義して、どちらが大きいともいえないふたつの木は同値である。たとえば、子ノード数の大小、それが等しい場合はここで定義する半順序で最大である子ノードの大小、それも等しければその次に大きい子ノードの大小、…といった具合に再帰的に定義すればよい。計算に時間がかかり過ぎることもない。
木構造の同値判定には、木構造を整数に関連付けるハッシュを行う方法もある。ただし、異なる木構造が同じハッシュ値にならないよう注意が必要である。一般に衝突しにくいハッシュ関数の設計はそれほど容易ではない。ここに問題がある誤答もあった。
問題 G. Warp Drive / ワープ航法
コスト関数を飛行時間の二乗平均の平方根としているが、これは「平均」の気分を出しているだけで、要は飛行時間の二乗和を最小化すればよいわけだ。
まずは、ワープ場がひとつだけで、すべての航空便がワープを使う場合を考えてみる。ちょっとした数式の変形で、巡航速度の逆数の二乗を重みとした各便の出発地の重心が、ワープ場の最適地であることがわかる。この計算は便数 m に対して O(m) でできる。
ワープ場の位置が決まれば、それを使うか否かは、行先空港とワープ場のどちらが近いかで決まる。出発地を中心に到着地までの距離を半径とする円の中にワープ場が入るならそれを使う、さもなくば使わないのが良い。すべての便についてこのような円を描くと、平面は最大 m2 個の領域に分割される。同じ領域内なら、そのどこにワープ場があっても、各便のワープの適否は同じになる。各領域について、ワープ場を使う便についてだけ上記の重心をとれば、それがその領域内にワープ場を置く場合の最適位置である。重心と最小コストの計算は O(m)、これを最大 m2 個の領域について行えばよいので、計算量は O(m3) である。
さて、この問題ではふたつのワープ場を設置できるので、各便がどちらのワープ場を使うかも決めねばならない。ワープ場がふたつあるとき、（もし使うのなら）近いワープ場の方がよい。だから、どちらのワープ場を使うかは、出発地が両ワープ場を結ぶ線分の垂直二等分線のどちら側にあるかで決まる。逆にいうと、空港地点の点集合を直線で二分する方法を尽くせば、ふたつのワープ場の使い方を網羅できる。
平面上のn点を直線で二分割するやり方の数は O(n2) である。このすべてに対して前述の O(m3) の計算を行うとすれば、全体の計算量は O(m3n2) になる。この問題の m, n の範囲なら、計算は十分短時間で済むだろう。
こうした解法の考え方に行き着くだけでもそう容易ではないが、さらにその実装も簡単ではない。みっつ以上の空港が直線上に並ぶ場合など、注意が必要な点も少なくない。7 問に正答した後にある程度の時間的余裕があったと思われるチームもあったのに、解答の提出がひとつもなかったのは、こうした難しさが障壁となったのだろう。
問題 H. Gift Exchange Party / プレゼント交換会
親友間でプレゼントする向きを適当に決めた状態から、プレゼント受け取り数の最大と最小の差を縮めていくことを考える。すぐ思いつくのは、貰う数が最大/最小の生徒が貰う/贈る向きを逆にすること（以下、「反転」と呼ぶ）だが、単純な反転は新たな最大や最小を作ってしまうかもしれない。かといって、新たな最大・最小を生じる反転をまったく行わないと解に到達しない。
そこで、生徒の列 P0, P1, …, Ps に対して、生徒 P0 の受け取り数を減らし、生徒 Ps の受け取り数を増やすが、他の生徒 P1, …, Ps−1 の受け取り数は変えないような複数操作をひとまとめに考える。このためには、P0 ← P1 というプレゼントの向きを反転して P0 → P1 に、これで増えてしまう P1 の受け取り数を元に戻すために P1 ← P2 を P1 → P2 に、…という反転の連鎖が Ps までつながればよい。プレゼントの最大数を減らす方向の連鎖（最大の生徒から、最大−2以下の生徒に至る連鎖）、あるいは最小数を増やす方向の連鎖（最小+2以上の生徒から最小の生徒に至る連鎖）がある限り、この反転連鎖操作を繰り返す。
実は、この貪欲アルゴリズムによって最適解が求まることが証明できる（証明は省略）。ある生徒から始まる/で終わる連鎖を探すのは、深さ優先探索などで O(m) で行える。連鎖の適用による最大・最小受け取り数差の変化が単調であることに注意すれば、連鎖の適用回数は高々 O(n2) であり、全体として O(n2 m) の計算量である。
正答はいずれも、ネットワークの最大流問題に置き換えて解いていた。貪欲アルゴリズムのような効率は望めないが、データサイズはさほど大きくないので、効率的実装なら計算時間が掛り過ぎることはないだろう。誤答にはヒューリスティクスに基いて最適とは限らない解を求めるプログラムが多かった。もちろん判定データは、簡単なヒューリスティクスではうまくいかないように工夫してある。