Power Calculusのダイクストラ解法のダメ出し
http://d.hatena.ne.jp/deq/20061108/1162956585
あたりで取り上げた2006年度のアジア地区予選横浜大会の問題F Power Calculus*1ですが，echizen.comのoxyさんから「そのノードへの最短ステップ数が最小でないパスは排除しているけれども，そういうような排除されたパスから他のノードへの最短経路が見つかるような場合もあるのではないか？」という主旨のつっこみを受けました。ごもっとも。ちょっと考えただけではその存在を否定することが証明できません。
直感的には，そのような経路が，ある最短経路への部分経路とはあんまりならなさそうなことが，次のように説明できます（ここで最短経路といっているのは，ダイクストラ的解法で残ったままの経路が導く最短経路のステップ数と同じステップ数ではないもの，つまり残ったままの経路群よりも1ステップは短くなるような最短経路です）。ダイクストラ的解法で残る「最短っぽい」経路は，比較的大きな数字の要素を多く持つ "long strider" といえます。彼ら long strider は大きな数字を持っているので，原点（xの1乗）から離れた未開の空間により早く到達できそうです。それに対して，ダイクストラ的解法で弾かれるような，遅くしてそのノードにやってきたものは，たいていどこかから戻ってきたり，小さなステップでそこに辿りついたような，小さな数字の要素を多く含む "short strider" といえます。彼ら short strider は小さな数字を多く持っているので小回りは効くのですが，あまり一度で遠くへいくことはできません。そして，結局のところ short strider が未開の地へ辿りついたころには，すでにそのような空間は一足先にその周囲に辿りついた long strider によって全て空間が開拓されていた，という悲劇が起こっているわけです。long strider によって未踏の探索空間が全て充填されるというのは証明しづらいのですが，「小さなステップ」という道具を多く持つよりも「大きなステップ」という道具を多く持つ方が，早く到達可能な範囲が広がる戦略を取ることであって short strider よりは遅くならない，と。
まぁ，こんな説明，だからどうしたってもの以上ではありませんが。。。
# ちょっと遠回りしてると先に先にと進んでた人には追いつけないってか。人生はそんなこと...ないよね？
