2005/Contest/国内予選

Problem D : Traveling by Stagecoach

問題概要

解法

普通に思いつく分には、

  • n! 通りの全ての馬車券の使い方について、変形した Dijkstra 法を実行
  • 1 つの都市を 2^n 個に増やしたグラフを作って、その上で Dijkstra 法

の二通りくらい。

前者は経路途中でのチケット使用状態を保存する工夫が必要。後者は (も) 試してないのだけど、計算量が大丈夫かなあ、というのがちょっと不安。 (最大で頂点数 30 * 256 = 7680 か。...どうにかなるかなあ)

こっちの解き方なら、ハマらなければ 30 〜 40 分が目標かなあ。多分、ハマりやすいコードになりそうだけど。

もう一つには Memorization 付き TSP という荒業でも解ける模様。動的計画法っぽく行けないかなあ、と考えてての思いつき。書いてみれば実にシンプル (Memorization 付きってのは自分は実は普段やらないんだが...。普段は泉が書くコードだw) なのだけど、本番中に、実はこれで行ける、と思い至るのは難しいんじゃないかなあ、自分は思考に二時間半費やしました。ただ単に自分の頭が固くなってるだけかも...。 oTL

こちらは、正確に考えられさえすれば 20 分で書けると思います。 (三廻部; Jul 4, 2005)


ちなみに、上に書いた「動的計画法」も不可能ではないはず。本質的には、表の更新コストは Memorization TSP と変わらず。 (軽く指摘があったので。コードは書きたくないので諦めましたが)

一方に都市、もう一方に「どの馬車券を持っているか」を表す状態 (2^n 通り) という軸を持つ表を作って埋めていく。表の中には「その都市にその馬車券を持って存在している時、目的の都市にたどり着くためのコスト (時間) 」が入る。

また、縦軸の状態は、それぞれの馬車券をビットで表して 0 〜 255 までの整数に落としてしまうと、そのまま表の座標になるのでラクかな。 (これは上の TSP でも変わらず)

以下、表の例。

券集合都市1都市2 = b都市3 = a...
0 = φ0.0
1 = {t1}?0.0?
2 = {t2}?0.0?
3 = {t1. t2}?0.0?
4 = {t3}?0.0?
5 = {t1. t3}?0.0?
...?0.0?
2^n - 1 = {t1. t2. .... tn}?0.0? = 解

ただ、この表の更新順序が問題。単純に左から or 上から更新、というわけには行かないので、ちょっとやりたくない感じがして諦めました。要はこれを解消しようとしたら Memorization になったんだけど。なんか DP のままやるいい方法無いかね? (三廻部; Jul 5, 2005)


馬車券集合の方向については半順序関係を定義できるが,都市の方向については順序関係を定義できないため,単純な動的計画法は無理.都市方向について 2 重ループを回せば可能かもしれないが(cf. Warshall-Floyd 法),memorization と比較してメリットがあるとは思えない.[泉,5 Jul 2005]

議論・その他

  • 下の三廻部のコードは、上記の TSP のコードです。素の TSP からちくちく拡張して書いたせいで Memorization のやりかたが汚い...。 (三廻部; Jul 4, 2005)

追記。

田中君 @ combat : http://d.hatena.ne.jp/tanakh/20050702

こっちのが俺のよりよっぽどきれいだよ...。書くの早いし。 oTL (三廻部; Jul 4, 2005)

本番で思いついていたけれども、Dijkstraで解けると分かってしまったからそれでいっちゃったな。自分としては計算に5-15分くらいかかると見積もっていたけれどもそうではなかったのか。気づいてたら節約した時間でE解けてたかもなぁ。野田はあれから20分で書けたって言ってたし。(たにぐち)

256個分割の方法について、よくよく頂点数を計算してみると、 30*256よりかなり少ないことが分かりました。 スタート都市は馬券を使っていないので1個、 2番目に到達する都市では8C1で8個、 以降n番目(0<=n<=8)に到達する都市は8Cn個しか頂点を使いません。 よって、完全グラフでも無い限りこの方法で十分解けると思います。 それにしても自分のコードは汚い・・・。(野田 05/07/06)


ファイルを添付する

fileD2.out 742件 [詳細] fileD1.out 908件 [詳細] filemikurube_d.cpp 1106件 [詳細] fileusaP_D.cpp 772件 [詳細] filedoorgod_D.fixed.cpp 817件 [詳細]
[添付ファイル一覧] [全ページの添付ファイル一覧]
アップロード可能最大ファイルサイズは 10,240KB です。

管理者パスワード:

添付ファイル: fileD2.out 742件 [詳細] fileD1.out 908件 [詳細] filemikurube_d.cpp 1106件 [詳細] fileusaP_D.cpp 772件 [詳細] filedoorgod_D.fixed.cpp 817件 [詳細]

Last-modified: 2009-11-06 (金) 13:26:36 (4343d)