C++
codeiq

電脳体キュラゲタムを討伐せよ

More than 3 years have passed since last update.

https://codeiq.jp/q/2574

激ムズのため協力可とのこと。結局解説の事前公開はしませんでしたが。


概要

左上のマスからスタートし、マップ上の一番高い地点をすべて回って戻ってきたい。隣接するマスの移動コストは


  • 高低差+1 : 11

  • 高低差0 : 3

  • 高低差-1 : 2

である。移動コストの合計の最小値を求めよ。

マップの縦横は250以下、一番高い地点は15個以下。


解法


地点間の距離


  • マップを走査し、回る地点を列挙する。

  • 隣接するマスをグラフに変換し、地点間の距離を(地点数分) ダイクストラ を回して求める。


    • マップの距離についてはAtCoderに類題がある

    • 今回、 地点はスタート地点を含めて最大16個 なので、最大16回ダイクストラを回すことになる。

    • マス数の上限は250**2=62500なので、ワーシャルフロイドだとTLEする。



  • なお、移動コストが非対称なので、dist[i][j]=dist[j][i]=...といった代入はできないことに注意する。


距離の合計


  • 地点を1回ずつ回って帰ってくる。といえば、 巡回セールスマン問題 である。

  • 巡回セールスマン問題のナイーブな解法は、順列を全列挙する方法だが、これではO(n!)となり、nの最大が16だとTLEである。

  • これには、bitDPを用いてO(n^2 2^n)とする解法が知られている。詳しくはSpaghetti Sourceを参照されたい。

  • この解法がとっつきにくい場合は、yukicoderで練習することができる。


解答例

http://ideone.com/lEW6vG

(ideoneのC++14、実行くんのC++11ともに0.3秒なので、スクリプト言語で1秒切るのは厳しいかもしれないですね)


まとめ

というわけで、実はダイクストラ+巡回セールスマン問題という典型問題でした。でもまあ、典型という結論に至るには考察が必要なので、良問であったと思います。