人材獲得作戦・４ 試験問題ほか: 人生を書き換える者すらいた。を見てしまった。
これはpaizaのランクSの問題の1つではないか。
なお、可能な全経路を列挙した上で最短を求める、というアルゴリズムは、マップのほとんどがスペースである場合に現実的な時間で終わらなくなってしまうのでLv3扱いです。
という観点ではまさにそれをやったのでLv3扱いである。最悪の探索時間になるのもSとG以外が空白のパターンだろうし、再帰的に計算する箇所でスタックがまずそうなのも分かるのだが、制限時間があったので、焦ってそういうのしかできなかった。
A* - Wikipediaってのでいけるらしいが、ぱっと見てもよく分からないな。計算機科学をちゃんとやってると当たり前なのかもしれないが。
\begin{equation} \left|\int_{-\infty}^{\infty} f(x) \delta_{n}(x)dx - f(0) \right| \le \left|\int (f(x) - f(0)) \delta_{n}(x) dx \right| \le {\rm sup}|f(x) - f(0)| \int \delta_{n}(x) dx \le \varepsilon \end{equation}
みたいなのも、初見ではほゎゎー！？だったしなぁ。慣れたら脊髄反射として。
まさに、ええええ積分に組み込んで括り出したら一発じゃないという勢いになる。
知ってしまうと知らなかった頃に戻れない不可逆なものなんで、何が難しいのか分からないということになるが(というより呼吸をする程度の感覚で使えないとお話にならなくなる)、初心にかえると案外こんなものも難しかったものだ。
考えてみると二分探索レベル程度を超えるアルゴリズムなんてまともに勉強したこともないし、なんだか実際に使ったこともないな。
いつか使うことになるのかも知らないけど。知ってるとタメになることもあるし、頭の体操も兼ねてスキルチェック系のサイトで遊ぶってのは案外悪くないのかもしれない。
