ひらめの日常

日常のメモをつらつらと

AtCoder: 第二回日本最強プログラマー学生選手権-予選- D Shortest Path on a Line (600)

問題はこちら

atcoder.jp

 N個の点がある。その点に対して、以下のように M回の操作を行い、辺を追加する。

  •  L_i \le s \lt t \le R_i となる頂点 sと頂点 t の間にコスト C_iの辺を追加する。

最終的な頂点 1から Nまでの最短距離を求めよ。

以降は0-indexとして話を進める。

解法1 - seg木でdp

 L_i , R_i が与えられた時に、 R_i までの最小コストは、「 R_i」と「 L_i, L _ i +1, ..., R _ i -1に到達する最小コスト +  C_i」の小さい方 である。

なので、与えられた辺のクエリを、 L_i で昇順にして辺を張りながら上記を実装すれば正しい答えは得られそう。

しかし愚直に計算すると、一つのクエリに対して全ての頂点の組み合わせの最小コストを見なければならないので、  O(NM) となり間に合わない。

ここでのボトルネックは、「 L_i, L _ i +1, ..., R _ i -1に到達する最小コスト」を計算するところで、ここを毎回線形探索すると間に合わない。そこで、seg木を使うことで高速に区間の最小値を求め、それを用いて  R_iまでの最小コストを更新すれば、 O(Mlog(N)) となり間に合う。(なお、区間クエリ、点更新なので遅延セグ木である必要はない。)

  • dp[i] := 頂点iに到達するための最小コスト
  • segtree := 区間ごとの最小コストを管理する
  • dp[R_i] = min(dp[R_i], segtree.query(L_i, R_i) + c (頂点rに到達できる最小コストは、区間[l, r]に到達する最小コスト + c)
  • segtree[R_i] = dp[R_i] (新しい最小値でseg木自体を更新)

解答

Submission #8393394 - NIKKEI Programming Contest 2019-2

以下はその抜粋部分。

struct edge {
    ll from, to, cost;

    edge(ll from, ll to, ll cost) : from(from), to(to), cost(cost) {};
};

typedef vector<edge> ve;
void solve() {
    ll n, m;
    cin >> n >> m;

    auto fm = [](ll a, ll b) { return min(a, b); };
    SegmentTree<ll, ll> tree(n + 1, fm, ll_inf);

    ve es;
    rep(i, m) {
        ll l, r, c;
        cin >> l >> r >> c;
        l--, r--;
        es.eb(edge(l, r, c));
    }
    sort(all(es), [](edge &a, edge &b) {
        if (a.from == b.from) return a.to < b.to;
        return a.from < b.from;
    });

    vl dp(n, ll_inf);
    tree.update(0, 0);
    dp[0] = 0;
    rep(i, m) {
        ll l = es[i].from, r = es[i].to, c = es[i].cost;
        ll t = tree.query(l, r);
        dp[r] = min(dp[r], t + c);
        tree.update(r, dp[r]);
    }
    ll ans = dp[n - 1];
    if (ans == ll_inf) {
        cout << -1 << '\n';
        return;
    }
    cout << ans << '\n';
}

解法2 - 工夫してダイクストラ

これがeditorialの解法。 今回の問題における辺の張り方の本質は、 L_i から  R_i まで、 全ての  s \lt t となるような頂点の組 (s, t) の距離が等しい という点。なので、 L_i から  R_i に辺を張り、その間の点は全てどちらかと同じ点のように扱えると楽である。(ここまでは考えたけどどうやって実現するのかわからなかった。)

そこで、まず全ての頂点  (i, i-1) にコスト0の有向辺を張ってあるグラフを考える。このグラフに対して L_i から  R_i に有向辺を張ると、コスト C_i で、その間にある全ての頂点に移動可能になる。コスト0の辺を貼ることによって最短距離が変わることはないので、答えはこのグラフに対してダイクストラを行えば求まる。

計算量は  O ( ( N + M ) log(N) ) で間に合う。

解答

Submission #8392845 - NIKKEI Programming Contest 2019-2

以下はその抜粋部分。

void solve() {
    ll n, m;
    cin >> n >> m;
    Graph g(n);
    rep(i, n - 1) g.add(i + 1, i, 0);
    rep(i, m) {
        ll l, r, c;
        cin >> l >> r >> c;
        g.add(--l, --r, c);
    }
    ll ans = g.dijkstra(0).back();
    cout << (ans == ll_inf ? -1 : ans) << '\n';
}

関連