ICPCというプログラミングコンテストの予選が今日(といってももう日付変わりましたが)の夕方にありました。50チーム程度が選抜されるようです。
これまでこの大会の準備側の記録はほとんどなかったように思いますが、準備に興味を持つ人を増やす意図もややあり個人的な記録を残します。 今年は C, F 問題の原案を作成していたのでそれについて記そうと思います。
C 問題原案
教室でNxNの席が並べられている。 席替えを行い、以前前後または左右で隣り合っていた生徒同士は、 席替え後には少なくともマンハッタン距離が floor(N/2) 以上になるようにしたい。 そのような席替え案を求めよ。2 ≤ N ≤ 50
中～序盤向けの問題を作ることを念頭において作題していました。最初は2次元ではなく1次元のものを考えていました。問題を思いついてすぐには答えは分からなかったのですが少し考えて、半分くらいのステップ幅で行ったり来たりを繰り返すと大体距離 N/2 が達成できる事がわかりました。 しかしこれを問題にすると、1次元だと実装もほとんどなくてあまりに味気ないため、2次元に拡張してみたのがこの問題になります。2次元でも1次元の考え方が適用できます。
予選だと1次元のバージョンを介さずいきなり2次元のものを解くことになるので結構面食らった選手の方は多かったかもしれません。実際自分が選手だったらどう手を付けるといいか分からず結構途方に暮れたのでは？という気がします。N/2というのはなんだかマジックナンバーっぽくてよくわからないし、偶奇の場合分けでハマりそうな点があります。
ちなみに提案時には気づかなかったのですが、次のようにしても解くことができます。NxNの席を市松模様に塗り、片方の色で塗られた生徒の位置は変えず、もう片方の色で塗られた生徒は前後と左右方向に N/2 だけずらすと、距離として大体 N-(小さい定数) が達成でき、問題で要求されているよりも良い結果が得られます。こちらで解いたチームもいくらかいたのかもしれません。
F 問題原案
2次元上の非凸多角形で、内側を塗りつぶされたものを考える。 この多角形の有限個のコピーを、拡大縮小や回転を行わずにいくつか張り合わせて、 凸集合を作りたい。そのようなことは可能か判定せよ。
年始頃だったか、風呂に入っているときにミンコフスキー和についてぼんやりと考えていました。
ミンコフスキー和の引数となる点集合のうち片方は入力で与えられ、もう片方は自由自在に構成して良いとしたとき、これらのミンコフスキー和がなにか”いい性質”を持つようにできるだろうか？といった問いから確かスタートしました。 ”いい性質”というのはなんでもよかったのですが、とりあえずは定番的な性質である非空な凸集合ということで探索を始めました。 これはある意味で自明に解けてしまいます。もし入力で与えられる集合が連結ならば、もう片方を適当なサイズの凸集合にすればミンコフスキー和も凸になります。つまり任意の入力に対して可能であるというのが答えです。 これでは面白くないので、自分で構成する方の集合に何か制約を課した方がいいのではないだろうかと至ります。 例えば凸集合は面積を持つので、面積を持たないような集合に制限するとどうだろうかと考えたのですがこれも適当なサイズの円周を取れば良いということになってやはり自明な問題になってします。 それなら有限集合、つまり点列に限定するとどうだろうかと考えてみたところ、なんだかいい感じに複雑な必要十分条件が得られたので、問題として完成させたものがこちらになります。 考えていた証明は公式解説とほぼ同じです。
問題文自体はシンプルで、実装はそれほど複雑になりきらないながらも幾何に対する実装の慣れはある程度必要で、考察の過程が面白いので個人的に気に入っています。
おわりに
準備サイドは自分で創作したアイデアを多くの人、それも適当な群衆に対してではなく志の高い強豪達を含む選手たちに対して披露できる貴重な場であると思っています。 自分は準備中もコンテスト中も楽しめたので満足しました。地区予選に出られる方はお会いしましょう (問題文とかジャッジシステム上で。。)
