月別アーカイブ: 2017年5月

ICPC 2005 Domestic D Traveling by Stagecoach

最近,なんやかんやあってICPCの問題を解いている.せっかく解いたのでD問題について解説してみる.もっといい方法もあるのだろうけど,とりあえず基本方針だけでも.

問題:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1138&lang=jp

考え方

この問題は馬車券によって馬の数が変わるため,それによりグラフの重みが変化する.したがって,ダイクストラ法のような経路探索アルゴリズムは使用できない(厳密には嘘.馬車券の状態まで含めてノードにすれば使える).かと言って,深さ優先探索や,幅優先探索するにもグラフが大きすぎるため厳しいものがある.一見手も足も出ない用に見えるけれど,こういう場合は動的計画法でどうにか出来ないか考えてみるといい.

この問題はよくよく考えてみると,今まで進んできた経路はどうでもいいことに気がつく.大切なのは,今どこのノードにいて,そこにたどり着くまでにどれだけのコストと馬車券を使用したかということだけ.そのためにどういう道順できたのかは,わからなくたって問題ない.これを使って漸化式を建てられれば,解けそうな予感がするので,実際にやってみる.

立式

式に落とすために変数を定義しよう.まず都市の集合を\(A\)とする.このとき,ある都市\(a \in A\)から直接道路でつながっている都市の集合を\(P(a)\)と表記しよう.また都市\(a\)から隣の都市\(b\)への距離を関数\(C(a,b)=C(b,a)\)で表す.次にすべての馬車券の集合を\(B\)と表し,今までに使用した馬車券の集合を\(Q_n\)とする.このとき\(n\)は移動した回数のこと.以上の変数を用いてある都市までの最小の総移動時間(コスト)\(f\)について次のような漸化式が成り立ちそうなことがわかる.

$$f(Q_n, a)=\min_{q\in (Q_n – Q_{n-1}), b\in P(a)} \left( f(Q_{n-1}, b) + \frac{C(a,b)}{q} \right) $$

ここで注意しなくちゃいけないのは,あくまで左辺が与えられたときに右辺を計算するということ.何が言いたいかというと,都市\(a\)にたどり着くために使用する馬車券は決まっていて,それでどれだけコストが抑えられるか計算するのが上の式が表していることの意味.だから\(Q_n\)が与えられたときの\(Q_{n-1}\)を計算することになる.おんなじように\(b\)もaからアクセスできる都市を手当たり次第試す必要がある.あとは上の式を実際に適用して解けばいい.

プログラミング

次が実際に僕が書いたプログラム.中身は上の式をただ落とし込んだだけなんで説明は省略.

 

内容についてどう思いますか?
  • いいね (2)
  • だめ (1)