ドラゴンファンタジー
永遠に続くと思われていた平和は突然終わりを告げた。 はるか昔に封印されていた魔王がついに復活を遂げたのである。だが、今まさに世界が闇に覆われようとしているとき、1 人の勇者が現れた。そしてその勇者は、世界各地に散らばっている伝説のクリスタルを集める旅に出た。伝説によると、全てのクリスタルを集めることができたならば、どのような願いでもかなえられるという伝説の龍神を呼び出すことができると伝えられている。その龍神の力を借りれば魔王を倒すことも可能なはずだ。
（以下略）
要するに
『魔王の瘴気に触れないようにして、全部のクリスタルを集めれるか？』
という問題。
図だと下みたいになる。
こないだの掃除ロボットの問題みたくとにかく力押しで解く問題なんだが、クリスタルの数が最大で20個！
20！＝ 2432902008000000000くらいなので、普通にやったら終わらない。
しかし！この問題では魔王が瘴気をだしてくれているおかげ（？）で結構ガンガン枝刈りが出来ます。なので、20個くらいなら現実的な時間で十分出来ます。
『今現在いる座標から、未回収のクリスタルのうち、どれかひとつでも取れなければ処理をやめる』
という条件をつければ、うちのヘボパソコンでもあ～ら不思議！解けちゃうんだよねぇ～
普通にやっても解けなかっただろうなぁ～。
解説見ながら作ってやっと出来たって感じだったからなぁ～。
因みに上の図だと、4つのクリスタルを集める事が出来ません！残念！
っつーかICPC系の問題文ってふざけてるの多いのよね（笑）
これで安眠できます！
上のページにある『タキオンピロー』を使えば、ぐっすり安眠できます！
上のページから抜粋すると
マテリア・タキオン社とデンマークのオルソ・コンセプト社が一緒に開発したタキオン枕です。
首に負担がかからないようにデザインされています。寝ている間にタキオン・エネルギーを受信し、自然治癒力をリカバーしてくれます。
どんな周波数も、安定したものに変えてくれるので、快適な睡眠をとることができます。タキオンヒーリングにも効果的です。
これは本当に凄いです！タキオンの恩恵にあずかりましょう！！
さらに、他にもあります！
＜ジオテックス＞
有害な磁気や周波数から、あなたを守ります。部屋の4隅に置けば、空気が浄化＆調和され、そこは癒しの空間に。
＜ハイドロリックス＞
この『ハイドロリックス』を水道管やタンクにつけておけば、水が調和・活性されます。水本来のエネルギーがよみがえるので、お風呂に入れれば肌にも良いですよ！
＜ハーモニクス＞
電話やテレビ、スピーカーなどに貼り付ければ、音が驚くほど柔らかくなります。心地よい、癒しの音色をお楽しみいただけます。
＜エレクトリックス＞
有害な電波や電磁波から、あなたを守ります。パソコンや電化製品につけると効果的なので、現代のオフィスや部屋では必需品といえるでしょう。
これさえあれば、貴方の生活はより良いものになりますよ！！
ばっかじゃねえの（ ﾟДﾟ）ﾊｧ？
巡回セールスマン問題
床を綺麗にしてくれるお掃除ロボットの作成依頼がきた。
手当たり次第に床を磨き続けていれば、そのうち汚れた床にたどり着き、綺麗に出来る。
しかし、エコだ！エコだ！と叫ばれる世の中、ロボットを動かしっぱなしにするわけにもいかない。そこで、あなたには、汚れた床を最小限の移動で綺麗にするアルゴリズムを考えてもらおう。
☆印はロボットの初期位置、×印は汚れた床、塗りつぶされた所には家具がおいてあり、通る事が出来ない。
こんな問題があって、ずっと解けなかったわけですが、『距離行列＆TSPで解けるよそれ』と言われ、あぁ、「なんだ解けるじゃないか、巡回セールスマン問題なんてたいしたこと無いのかも」と思った訳です。
まず最初に、距離行列を作る。
上みたいに各場所までの距離を、おのおの求めて距離行列を作る。
もうそしたら、とにかく無理やり！ゴリ押し！力押し！
んで、解けたわけですが
『TSP（巡回セールスマン問題）など恐るるにたらんわ！フハハハハ！！』
みたいに調子に乗って、
『もっと汚れた床増やしちゃえ☆』
と、沢山汚れた床を増やした訳ですが・・・・・・・・・
終わらねぇ・・・・・・・・・・・・・どんだけ待っても終わらねぇ・・・・・・・・
よくよく考えてみると、
１！ ＝ １
２！ ＝ ２
３！ ＝ ６
４！ ＝ ２４
５！ ＝ １２０
６！ ＝ ７２０
７！ ＝ ５０４０
８！ ＝ ４０３２０
９！ ＝ ３６２８８０
１０！ ＝ ３６２８８００
１１！ ＝ ３９９１２８００
１２！ ＝ ４７９００１６００
１３！ ＝ ６２２７０２０８００
なので、汚れた床の数が10を超えたあたりで厳しくなってくるね。
どおりで問題でも『汚れた場所は10個以内』って書いてあるわけだ
そりゃあ、お偉方が頑張って研究してるだけあるわ、TSP
TSPはNP困難問題に入るはずなので、時間がかかって解けないよってことね
ちなみに下の画像のように、30回の移動で全て回れます
○は地球を救う
○に入るのは金かそれとも愛か
金
↓
お金は使うとなくなる
↓
さらに、自分が生きるためにもお金が必要です
↓
募金する余裕はない
↓
（'A｀）ﾀﾞﾒｼﾞｬﾝ
愛
↓
愛は無償のもの
↓
ですが、少なくとも地球は救われていません
↓
無償の愛ですら足りていない
↓
（'A｀）ﾔｯﾊﾟﾘ､ﾀﾞﾒｼﾞｬﾝ
愛が無償だとするからいけないんだな。
金の切れ目が縁の切れ目って言うしね。
とりあえず、自分の身の回りが平和ならば良かったりするNEヽ（'∀｀ ）ﾉ
海で食べたいもの！
ブログネタ：【夏休み企画！ 夏満喫ネタ 第三弾】海で食べたいものは？
参加中