表題の問題を解きました。
問題はこちらから。
＜さらっと概要＞
有向グラフがあり、そこを2人で1からNまで行く。
途中に少なくともどちらか一方が通らなければ行けない場所があり、それらを全て通ったときの2人の移動経路の合計の最短は？
・まず、ここの文に注目します。
JOI 高校は，混乱を避けるため，オリエンテーリングの間，それぞれの道を，高度が低い方の地点から 高度が高い方の地点への一方通行とする．高度が等しい 2 つの地点は存在しない．スタートである地点 1 は最も高度の低い地点であり，ゴールである地点 N は最も高度の高い地点であるが，地点の番号は必ずしも高度の低い地点から順につけられているわけではないことに注意せよ．
ここから、高度が低い方から見ていけば答えに近づきそう。
「番号は高度が低い方から振られているとは限らない」→もう一度高度が低い方からつけ直せば良いです。
これをするためのアルゴリズムがトポロジカルソートです。閉路のない有向グラフに適用することができます。
トポロジカルソートされたあとの順序はトポロジカル順序と呼ばれ、トポロジカル順序がそれ以下の頂点には移動できなくなります。つまり、iからjへ移動できるできることはi<jであることの同値十分条件となります。
トポロジカルソートとDPは非常に相性が良いです。なぜなら、トポロジカル順序に沿ってたどっていけばその地点における更新に必要な情報をすでに計算してあるからです。
今回も最小値を求める訳なのでDPをすることを思いつきます。ここで、DPの更新に必要な要素は2人のそれまでの移動距離とそのとき相方がどこにいるか、です。
二人の人をA,Bとします。ただし、区別をつけるため最初のチェックポイントにいった方をAとします。
dp[i][j][k]:k(0:A、1:B)がトポロジカル順序でのi番目の頂点にいて、相方がj(最初に与えられたインデックスのままでいいです)にいるときの2人の移動距離の最小値
と言う風になります。
N<=1000と制約が緩いので更新にある程度の時間を割くことができます。ここでは、i番目のチェックポイントにAがいく時の更新を考えます。Bのときも同じようにできます。
i→jの最小コストをf(i,j)とします。
・i-1番目もAが訪問しているときからの更新
Bは動かないので、Bが最後に訪れた場所は変わりません。
iはトポロジカル順序でi番目という意味なので、それに当たる頂点の番号をpとします。(これ以降この前提で話をします。)また、トポロジカル順序でi-1番目に当たる頂点をtとします。
よって、jが1からnまでの場合を考えて、dp[i][j][0]=min(dp[i][j][0],dp[i-1][j][0]+f(t,p))とすればいいです。
・i-1番目をBが訪問しているときからの更新
この場合は、Aが最後に訪れた場所の候補が1～nまで考えられます。また、相方が最後に訪問した場所はトポロジカル順序でi-1番目の場所(=t)です。
すると、jが1からnまでの場合を考えて、dp[i][t][0]=min(dp[i][t][0],dp[i-1][j][1]+f(j,p))となります。
これで全体でO(N^2)で解けるようになりました。と言いたいところですがf(i,j)の更新を考えていませんでしたね。
グラフ上の最短経路なのでdijkstra法でpから各頂点までの最短経路をO(NlogM)で求めることができるので全体の計算量はO(N^2 log M)です。N<=1000,M<=10000なのでこれで問題ありません。
ただし、グラフにそのままdijkstra法を適用してしまうと、pよりトポロジカル順序が後の頂点までの最短経路までしか出せません。(トポロジカル順序の定義より、トポロジカル順序が前の頂点へ移動する辺がないので)
実際には更新に使う頂点はトポロジカル順序が前のものだけなので、逆辺でdijkstra法を適用するとうまくいきます。
自分の提出を貼っておきます。汚いコードですが良かったらどうぞ。
ありがとうございました。
