激ムズのため協力可とのこと。結局解説の事前公開はしませんでしたが。
概要
左上のマスからスタートし、マップ上の一番高い地点をすべて回って戻ってきたい。隣接するマスの移動コストは
- 高低差+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秒切るのは厳しいかもしれないですね)
まとめ
というわけで、実はダイクストラ+巡回セールスマン問題という典型問題でした。でもまあ、典型という結論に至るには考察が必要なので、良問であったと思います。