300問目！

もう毎日がpku一色になってます(笑

今日は久しぶりにバイトに行って、帰ってきてから鍋を作りつつpku。笑"

んでー、記念すべき300問を突破しました。はっぴーw

300問めはこちら。

500個の点が2次元平面上にあることを考えてみてください。

んで、各点と各点の位置関係、つまり"AはBの真北にある"とか、

"AはBの南西にある"とかいうのが10,000個与えられたとき、

その制約を満たすような500個の点の配置は存在するかどうか、という問題です。

さてうちのチームの人には解法を考えてもらいましょうか。

初めて"続きを読む"をつかってみるテスト。

さて解法。

んで、落ち着いて考えたら分かるんだけど、

南北方向と東西方向を独立にとけば良いわけですよ。

南北方向の制約が成立して、かつ東西方向も成立したときのみ、

問題全体として解が存在することが分かります。

なので、まず南北方向に考えてみます。

南北方向を数直線だと思って、点Aの場所をXa,点BをXbとかいう風に置くと、

Xa<Xb Xa==Xb Xa>Xbという3つの位置関係になって。

さらにXa<XbとXb>Xaは同じなので、"<"と"=="だけを考えたらいいことになります。

もし==がなければ普通にトポロジカルソートしたらいいのだけど、

(トポロジカルソートは以前このブログに書いたので分からない人は検索してみてw)

==があるからちょっと面倒くさくて。

自分は==の部分を全部1つの点に縮約した上でトポロジカルソートしたけど、

はたしてこれが想定解なのかどうかw

以上300問目の説明終わり、、301問目を解き始めることにしますw