カードに特定の操作を繰り返して、一番上に来るものを求める問題。 処理を実装するだけだし、その処理も簡単…なはずだけど、 緊張のあまり配列の添え字に頭が混乱してしまってデバッグに手間取り。 さらにSubmitにも手間取って 結局最初問題が見えるまでかかった5分ほどを含めて20分弱かかった。 緊張している時にこういう問題は要注意である。
マップが与えられて、スタート地点から到達できるマスの数を求める。 塗りつぶすだけ。ものすごい簡単。混乱するタイプの問題でもなかったので 開始から30分目ほどでAccept。ノーデバッグ。
与えられた分数を分子が1の分数で表現する方法の数を求める。 普通の深さ優先探索でOK。時間も十分間に合う。 分数の個数と分母の積に制限があるので、それで枝狩りできる。 普通に書いて普通に速いプログラムが作れた。 開始1時間ほどでAccept。
私が問題ABCを解いている間にK氏に考えてもらっていた問題。 実装を任せて残りの問題を考えに。
問題Fは見た目よりも難しそう。 苦手な幾何問題の問題Dと一緒に見比べながらうんうん唸っていると、 問題Dの方の解き方をひらめいた。問題Cを解いてから30分ほど。 まだまだかかりそうだった問題Eを中断してもらって問題Dの実装。 ちなみに、「情報処理」という雑誌に載っていたプログラムプロムナードという 連載の"丸い紙ふぶき"の回の解法を思い出してこれの解法を思いついた。 そちらも参照してもらえれば参考になるかもしれない。
問題Dは、二次元平面上に複数の点が与えられ、 それらをもっとも多く囲む半径1の円を求める問題。
最初、x,y座標が0から10まで、点は0.0001刻みにしか存在しないということなので、
100000*100000の点を調べてやろうかとも思ったが、さらに最大300個の点との距離比較を
しないといけないので、絶対に間に合いそうに無かった。
2,3の点を含む外接円の中点のいずれかに求める円の中心が存在するとの
M氏の指摘であったが、その中に本当に求める点があるのかどうかの簡潔な
証明が得られなかったので、他の手を考えることにした。
(計算量もO(n^4)なのでn=300に対しては遅すぎるかもしれない)
私が思いついたのは、求める点は与えられた各点を中心とする
半径1の円によって分割される領域の中のひとつに求める点があるということ。
上図にて、0個とかかれたところを中心とする半径1の円には点が0個、 1個なら1個、2個なら2個含まれることが容易に分かると思う。 また、問題の定義から円周上の点も含むので、境界上の点はその境界が接する 領域の中でもっとも多くの数となる。 上のことから、100000*100000の座標全部調べなくても、 点を中心とする半径1の円により分割される各領域の中の点を ひとつづつ調べればそれですべてが尽くされることが分かる。
Fig.1 各点を中心とする半径1の円が平面を分割する
そうと分かればその領域の算出方法である。 最初 "丸い紙ふぶき" で使われている方法をそのまま使った。
まず、円同士の交点と円の上端、下端のy座標をすべて求める(黒点)。 そこを通る水平線を引き(黒線)、隣り合う水平線の中間の線を求める(赤線)。 それぞれの赤線について、円との交点を求める(赤点)。 隣り合う赤点と赤点の中点(緑点)をすべて求めると、 この緑点が全領域を含む。
Fig.2 領域中の点
しかしなんと、遅すぎる。ここまで実装して気づいたが、 オーダはO(n^4)かもしれない。 上誌によると円100個まで解けるらしかったのですっかり安心していた。 (それに、上図で緑点は領域をすべて尽くしてはいるが、重複が多すぎて無駄が多い) 数分考え込んでしまったが、とっさに円の交点だけでOKということに気づく。 この問題は紙ふぶきと違って領域の境界上の点でも正しく答えが求まるのである。 なんというか、紙ふぶきを知っていたがゆえに遠回りをしてしまった感もあるが、 知らなかったらスパッとした解法を思いついていたかどうかは怪しい。 なんともいえないが。
そこまで考えて、急遽アルゴリズムを単純化。 交点を調べるだけのプログラムを作成。オーダーはO(n^3)である。 速度は問題ないレベルに。 ところが答えが合わない。0個とか出力されるケースがある。 0個などありえないわけだが、 問題を見てみると、交点が存在しない場合である。なるほど、確かにおかしくなる。 それを回避するために交点のほかに円の中心自身も調べる候補に追加した。 (これは後で考えると、交点が無いときは1個とするだけで良かった) ということでAccept。途中結構手間取った。最初から交点でよいということに気づいていれば もっともっと速かったはずなのに。 ついでに円の交点ルーチンを求めるルーチンを紙から移すときに 大量のタイプミスをしてしまったせいでそれでも結構かかってしまった。 この時点で2時間半。延長が15分あったので残り45分。 問題Eができることを祈りつつK氏とM氏に残りの実装を任せる。
ついでに問題D解法のまとめ。散文的になってしまったので。
- 与えられた点を中心とする半径1の円同士の交点をすべて求める。
- 交点があればそれらの交点を中心とする半径1の円に含まれる点の数を各々計算し、 その最大値を解とする。
- 交点が無ければ、解は1である。
残り45分間、どうせ実装はできないだろうなぁと思いながら適当に考える。
考えれば考えるほど面倒な問題に思えてくる。これは解いちゃいかん問題だった。
縦と横の通りのグルーピング、
方向つきグラフを基にしたランクによるグルーピングとかを行う必要がありそう。
前者はそれほどでないにしても後者がさっと思いつきそうに無い。
適当に全部調べて大丈夫なオーダだろうか?
しかし、どう転んでも45分で実装、デバッグまで完了するのは不可能そうである。
最後に残して正解。
今年は5問がトップだろうなぁと思いつつ。
正直6問解いてるチームがあったら今の私には敵う気がしないと思った。
問題Fが特に難しくないのでは?というK氏の指摘があった。 交差点における強さの関係に同水準関係を追加したグラフを探索すればいいだけという話。 同水準関係は何か再帰的に処理しないといけないと勘違いしていた。 特定の二つの通りの間に何か通りが挟まっているかどうか調べるだけなのな…。 方向が異なるかどうかは、グラフ中でのノード間の距離から判別できると。 なんかよく分からないが、自分でどんどん難しいほうに考えてしまっていたらしい。 というか、問題が全然読めてなかった。本格的に駄目ですな…。 というわけで、Sample Outputと一致するものができた。 探索は最初適当に深さ優先で書いてみたけど、First Inputが全然間に合わなかったので、 距離をテーブルに書き込むダイクストラっぽいものに変更。
任せたきりほとんど何も言及しなかった問題Eであるが、 ようやく気力が回復してきたので解いてみた。 方針はすでに立っていたので実装するだけだったのだが。
Fig.3 容器例
まず、容器を仕切り情報を元に上図のように長方形に分解し、 さらに各長方形をつないでツリーにする。これで準備は完了である。
Fig.4 ツリーへの構成
各ノードは、左端のX座標、右端のX座標、深さ、現在の水量などのパラメタ及び 子ノードへのポインタ、親ノードへのポインタを持つ。 これにより、ノードへ水を注ぐという動作を帰納的に記述することができる。 まず、最初に蛇口のX座標に対応するリーフノードに全水量が流れ込むとする。 リーフノードへの注水は、水がそのノードへ入りきればそれで終了、 入りきらなければ親ノードへ残りの水を注水することになる。 リーフノードではないノードへの注水の場合、まず子ノードを調べる。 子ノードのいずれかが満水で無い場合、そのノードへ注水を丸投げする。 両方満水で無い場合いずれかに投げることになるが、 ここでどちらに注水すればよいか決めることはできない。
このような場合にどちらへ流すか決定できるように、 あらかじめどちらか方向へ伝って流れているという情報を 受け取ることにする。この情報を付加するのは子ノードのどちらか片方だけが 満水になっている場合に、満水で無いノードに丸投げする場合だけであるが、 逆にそれ以外のケースで必要になることは無い。 子ノードが二つとも満水だった場合、リーフノードと同じ処理を行う。
Fig.5 壁伝いにながれるときの例
上記操作を実装すれば、注水作業はノードを上り下りしながら 最終的に全体の水位が決定できる。 蛇口は複数あるが、これは別個に注水している。 注水順が水位に影響を及ぼすことは無いと思われる。 (実は本当かどうかは確かめていない…。直感的にはそう思うのだが) 上記操作で水があふれるけど親ノードが無い。というときは水槽自体から水があふれている ということになるので、特に何もする必要はないだろう。