ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

Codeforces Round #623 (Div. 1) D. Tourism

Problem - D - Codeforces

計算量がキツキツなので想定解じゃないような気もするのですが、通せたので私の解法を書きます。

問題概要

 n 頂点の有向完全グラフが与えられ、各辺にコストが設定されている。

頂点1からスタートしてちょうど  k 辺を通って頂点1に戻る経路であって、奇閉路を含まないものの最小コストを求めよ。頂点、辺は同じものを何度でも通って良い。

制約

  •  2 \le n \le 80
  •  2 \le k \le 10 であって  k は偶数

解法

 k が最も大きい  k=10 のケースにおいて、経路は以下のようになっています。(実際には頂点や辺が重複していることがあります)

f:id:betrue12:20200224145146p:plain

この図で青く塗っている、始点/終点以外の偶数ステップ目で訪れる頂点は高々4個です。これを  n^{4} のループで全探索しましょう。 80^{4} = 40960000 なのでこの時点で危険な香りがしますね。

そうすると奇閉路を含まないようにコストを最小化するには、奇数ステップ目で踏む頂点を「偶数ステップ目で踏む頂点以外から」なるべくコストが小さくなるようにそれぞれ選べば良い、ということになります。

これはそれぞれ  n 個の頂点を全部調べれば求められますが、ちょっと時間が厳しいので前計算します。全ての頂点ペア  (i, j) について、全ての  k に対する  i \to k \to j の移動コストを求めて短い順にソートしたものを持っておきます(実装上は、さらに最後にINFを入れておくと楽です)。そうすれば頂点  (i, j) の間にある奇数ステップ目の頂点を探すときには、このリストを前から見ていけば最長でも  6 位で使えるものが見つかります。

外側のループが  n^{4} で、 \frac{k}{2}-1 個の奇数ステップ頂点として使えるものをそれぞれ最悪  \frac{k}{2}+1 位まで探すので、一応計算量評価をすると  O(n^{4}k^{2}) になります。ここまで  k が小さいと定数倍を無視する表記法を使うのもどうなんだろうという気もしますが、実際にランダムな最大ケースで試すと一番内側のループが2億回くらい回っていました。通って良かったですね。

ACコード

Submission #71722559 - Codeforces