拡大グラフ上のダイクストラ

ACM-ICPC に Traveling by Stagecoach Traveling by Stagecoach という問題がある. 大雑把に言うと, 入力として道路網のグラフが与えられるので, 最短路を求めよ, という問題なのだが, 一捻りして馬車券という要素が加えられている. 要するに最短路を求めるべきは, 入力の道路網のグラフそのものではなく, 各馬車券の使用状況の分を含めて n 次元増やした拡大グラフ上なのである. ノードとして持つべき集合を数式で書くと次のようになる.

{都市} × 2^|馬車券|

区別すべき状態が何なのか見分けようとする, ある程度以上のレベルの人には, 適切なグラフを作って普通にダイクストラをするだけなのだが, 体系的に教えられていない初心者にはこれはかなりの曲者である. 2 つのグラフを混同してしまって, 何とかして元のグラフ上で最短路を求めようとして, 意味の分からないコードを書き連ねてしまう. ACM-ICPC の国内予選では最短路問題は必ずこの手の一捻りを入れてあるので, 多くの初心者がせっかくダイクストラを覚えたのに活用できずに去っていくということになる.

これに限らず, いろいろな問題クラスについて, 押さえるべきポイントというのはあるわけで, 練習あるのみとか言わずに, 教えていくべきように思う. また, こういったことを習得することで, 量産型素人と違う, 情報科学系を修めたプログラマとして胸を張って言えるのではないかとも思う. (さすがにちょっと言いすぎかも)