PKU

未だ14人しか解いていない問題が解けたのでとってもハッピー☆

で、その問題はこちら。

http://acm.pku.edu.cn/JudgeOnline/problem?id=3679

ま簡単に説明すると…問題のページにあるような、

何個かの町(ブロック)と、それらを結ぶstreetが与えられます。

んで、各ブロックごとに、そこを手に入れたときの利益が与えられてます。

Tomは自転車で好きなところをグルッと回ってきて、

図の赤線みたいな閉路を作ることが許されています。

で、閉路の中のブロックをTomは手に入れることができるので、

そのときのTomの最大の利益はいくらですかーって問題です。

あとTomは20秒以内に帰ってこないといけない、とかいう制約があって、

(ブロックの1辺がちょうど1秒で走れる距離)これによって問題が

だいぶ簡単に(といっても大変だけど)なっています。


解法の説明もしようかと思ったけど、

この日記を見て挑戦する人もいると思うのでやめておきます。


ちょうどこの3日ほどスノボ行ってて、

PCが手元になかったので、今まで解けなかった問題をいっぱい考えてたら、

ちょうどこの問題の解法がひらめいて、実装してみたら通ったっていう。

バグを出すことなく一発でAcceptされたのですごく嬉しいです☆

ちなみに今769位で286問正解だそーです。