PC Koshien Warm Up

無事終了しました。皆様の御参加ありがとうございました。
23日(Sun) 13:00 より、参加できなかった人のための延長戦が行われます。以下に解法の概要を解説しますが、この延長戦に出場される方にとってはネタバレとなりますのでご注意ください。

Problem 01: Kyudo: A Japanese Art of Archery

入力値の総和を求めるだけです。簡単です。

Problem 02: Yes, I have a number

原案を担当しました。
引っ掛け問題ですが、引っ掛けどころは親切にも問題文に丁寧に書いてあります。連続した空白文字を含むケースや先頭・末尾の文字が空白文字であるケースについて入念にテストすれば、難無く正解できます。
原案の時点では、引っ掛けどころを丁寧に書かないイジメ問題でした。

Problem 03: Selecting Teams Advanced to Regional

各チームの順位を求めて、問題文の通りに進出判定を行います。
ソートのライブラリ関数ぐらいは使えるようになっておくと便利でしょう。

Problem 04: CamelCase

原案を担当しました。
まさかいないとは思いますが、3 * 3 = 9通りの変換コードを書いた人は反省してください。3通りの入力と3通りの出力(lowerCamelとUpperCamelはほぼ同じなので、実質2通り)を書けば十分です。
もしもC++のSTLを使いこなせるのなら、アンダースコア記法の入力は直接単語に分解するよりもlowerCamelに書き換えるほうが簡単です('_'の直後の文字を大文字にし、std::removeで'_'を消去する)。この工夫により、もしかしたらコーディング時間を短縮できるかもしれません。30秒ぐらい。
これまでの4問は、純粋な実装力が問われる問題です。速く正確に実装することを目指したいものです。

Problem 05: Split Up!

原案を担当しました。
これ以降の問題では実装力と同時にアルゴリズム力が問われることになります。が、この問題ではそれほど難しいことは問われません。
n は最大20なので、可能なパーティ分けは 2^20 = 1,048,576 通りしかありません。よって、全通り試して最小値を取れば十分です。バックトラック + 枝狩りや、1人目所属パーティをAに固定するといった高速化が考えられますが、特に何もしなくてもAcceptされます。
計算量の見積もりは、コンテストにおいて必須のスキルです。是非とも身に着けましょう。

Problem 06: Ghost Buster!

原案と問題文を担当しました。

解法 1

幽霊の行動が周期的であることを考えると、(少女の位置, 幽霊の位置, 幽霊が pattern 中の何番目の行動を次に行うか) という組み合わせに対して、それが最初に発生しうる時刻を求めていけばいいことが分かります。つまり、これら3つの組み合わせをノードとするグラフにおいて、(少女の初期位置, 幽霊の初期位置, 0番目の命令を次に行う) というノードから、少女の位置と幽霊の位置が等しいような任意のノードへの、最短経路を求めればいいのです。
この最短経路はBFSで求められます。計算量は O((HW)^2 * |pattern|) となります。

解法 2

まず、全てのマスについて、少女の初期位置からたどり着くのにかかる時間を求めておきます。
次に、時刻を1分ずつ進めながら、幽霊の動きをシミュレートしていき、次の判定を行います。幽霊が t 分後にいるマスに少女が t 分以下でたどり着けるのならば、t が求めたい最初の時刻となります。なぜならば、t分以下でそこにたどり着けないのならば明らかにt分後に遭遇するのは不可能ですし、逆にt分以下でたどり着けるのならばそのマスで待機していればいいからです。
これに加えて、「絶対に遭遇できない」判定を行う必要がありますが、これは「十分長い時間経っても遭遇できないならば、絶対に遭遇できないと判断する」という方法で行えます。「十分長い時間」というのは、以下のようにして計算できます。
簡単のため、少女が(絶対にたどり着けないマスを除いて)どのマスにもたどり着けるほど長い時間が既に経っていると仮定します。幽霊が今後どのように動くかは、(幽霊の位置, 幽霊が pattern 中の何番目の行動を次に行うか)の組み合わせが決まれば一意に定まります。したがって、シミュレーションの過程でかつて経験した組み合わせに再びなったならば、同じ組み合わせに将来三度なる――つまり、幽霊の動き(※行動パタンとは別物であることに注意)は以降周期的になることが分かります。
ここで、幽霊の1周期目の動きのに少女と幽霊が遭遇しなかったならば、仮定により2周期目以降でも絶対に遭遇しないことは明らかです。よって、かつて経験した組み合わせに再びなったならば、「少女と幽霊は絶対に遭遇できない」と保障できます。
さて、この組み合わせは H * W * |pattern| 通りしかありませんので、 H * W * |pattern| + 1 分だけシミュレートしたならば、いずれかの組み合わせが必ず2回以上登場していることになります(see also: 鳩ノ巣原理)。
また、「少女が(絶対にたどり着けないマスを除いて)どのマスにもたどり着ける」ためには H * W 分あれば十分です。あるマスからあるマスへ移動するのに、同じマスを二度通る必要は無いからです。
よって、(H * W) + (H * W * |pattern| + 1)分だけシミュレートして遭遇できなければ、絶対に遭遇できないと言えます。
理屈は複雑ですが、プログラムは比較的単純なBFS + シミュレーションとなります。計算量は O((H * W) + ((H * W) + (H * W * |pattern| + 1))) = O(H * W * |pattern|) となり、解法1よりも高速です。

今にして思えば、もっと配点を高くして、解法2でないと解けないようなサイズにしたほうが面白かったのかもしれません。解法1は典型的なので。

Problem 07: Crop Circle

原案を担当しました。
方針としては、それぞれの円について、他の円によって消されずに残る円弧の部分の長さを求めて足し合わせることになります。円 C について、この残る円弧の部分は、次のようにして求められます。
まず、Cを他の円との交点で切断していきます。これはCと他の円との交点を全列挙し、Cの中心を通るx軸に平行な直線と作る角度でこれらの点をソートすることで実現できます。切断されたそれぞれの円弧は、どの他の円にも含まれないか他のただ一つの円に含まれるかのどちらかです。よって円弧上の適当な点(ただし両端点は避ける)をとって、それが他のどの円にも含まれていなければ、その円弧は他の円によって消されずに残ることになります。
計算量は O(n^3) ですが、n <= 100なのでこれで十分です。また、このアルゴリズムを比較的簡単に O(n^2) まで改良できます。
出題者はあまり難しい問題だと思っていなかったのですが、時間が足りなかったためか、正解者どころかSubmitした人もいませんでした。
よく言われることですが、幾何学はライブラリが命です。この問題では2円の交点のライブラリがあれば十分ですが、他にもいろいろと用意しておくといいでしょう。

Problem 08: Provident Housewife

解法 1

(買った商品の集合, 現在地)に対して最小コスト(コスト = (消費金額, 移動距離))を求めていく動的計画法により、O(2^q * n^2 * q)ぐらいで解くことが出来るはずです。私は実装していませんが、これが第一の想定解法です。

解法 2

消費金額を最小にしなければいけないということは、つまりどの商品も最も安い店で買わなければいけないということです。なので、全ての商品について、それを買ってもよい店(一番安い店)のリストを作ることが出来ます。
ある店の部分集合 S を考えたとき、このリストからSで全ての商品も買い揃えられるかどうか簡単に判定できます。買い揃えられる全ての S について、Sの店を全て巡回して帰ってくる最短距離を求め、それらの最小値をとればいいのです。最短距離を求めるには、よく知られている巡回セールスマン問題の動的計画法による解法が使えます。

解法 3

時間内にこの問題を解いた参加者は2人いましたが、2人ともnext_permutationを使っていたようです。n件の店の訪問順序を先に決めてしまえば、店を順に訪問しながら買える所で買っていき、全商品が揃った時点で帰ればいいわけです。C++のstd::next_permutationを使えばこの訪問順序の全列挙が簡単に行えます。
店は最大9件なので、この解法でも十分間に合ってしまいます。これを想定していなかった審判は迂闊と言うしかないでしょう。反省します。

Problem 09: Building Houses

原案を担当しました。
next_permutationで並べ方を全列挙していては間に合いません。バックトラックと枝狩りが必要です。
枝狩りとしては、「既に見つかった最適解を超えてしまったら打ち切る」だけで十分です。と言うよりも、審判が他に効果的な枝狩りを思いつかなかっただけなのですが。反省します。
90点にという高配点にもかかわらず6 - 7番目ぐらいには簡単ですが、パソコン甲子園には得てしてそういう問題が出てくるものです。気をつけましょう。

Problem 10: The Last Dungeon

原案を担当しました。
与えられた点を使ってボロノイ図(wikipedia: ボロノイ図)を描き、このボロノイ境界の上だけを通って西から東へ移動する最短経路をDijkstraで求めます。
あるボロノイ母点 p のボロノイ領域は、まずpを含む十分大きな領域を用意し、これをpから他の母点へ引いた線分の垂直二等分線で切断してはpの側を残していくことで求められます。ボロノイ図はこうして O(n^3) で構成できます。O(n * log(n)) で構成することもできます(動的計画法またはFortune走査, うちの大学の講義資料[pdf])が、そこまでする必要はありません。
実装量が多く、3時間という制限時間を考えると、この問題を解くことは簡単ではありません。いわゆる最終防衛問題です。

勝者

上位入賞者は以下のとおりです。おめでとうございます。

Rank	ID	AC	Point	Time
1	Hirano	8	340	381
2	japlj	7	270	300
3	s1150092	7	270	406
4	sillte	7	270	645
5	Ben	7	250	318

その他諸々

問題の作り込みが十分でない箇所がいくつかあって、申し訳ありませんでした。
私が原案を担当したのは7問ですが、忙しかったので問題文の作成は1問を除いて他の人にお任せしました。その1問も、コンテストの始まる5時間前に書き上げてコーチに送り付けるという有様でした。ごめんなさい。そういうわけで、Problem 06だけ問題文が怪しいオーラを放っています。
結果はyukの独走でした。実装速ぇ。すげぇ。
高校生の上位は Top3はJAPLJさん、natriumさん、pineさんでしょうか。最近の高校生の強さは異常だと思います。

重ね重ね、皆様の御参加ありがとうございました。