全国統一プログラミング王決定戦本戦 F - Flights (他人の解法を見た)

20位以内に入りたければ、A問題からE問題は自明問題として高速に処理し、この問題かG問題のどちらかを解く必要があった。
F - Flights

問題

XY平面上にN個の点がある。i番目の点の座標は(X[i], Y[i])であり、どの2点の座標も異なる。この点たちの間に、以下の規則で無向辺を設ける:

  • X[i] <= X[j], Y[i] <= Y[j]のとき、頂点iと頂点jの間にコストC[j]の無向辺を設ける。

頂点Sから頂点Tへ移動するときの最短距離を求めよ。

制約

  • 2 <= N <= 10^5
  • 0 <= 座標 <= 10^9
  • 1 <= C[i] <= 10^9

解法

最短経路がどのような形をしているか考察してみよう。X[i] <= X[j], Y[i] <= Y[j]のとき、頂点jは頂点iの右上にあるということにする。明らかに、頂点jが頂点iの右上にあり頂点kが頂点jの右上にあるときはi -> j -> kという道を通る意味はない。このことから、最短経路はジグザグになっている、つまりS -> a_1 -> a_2 -> ... -> Tを最短経路としたときにa_1はSとa_2の右上にあり、a_3はa_2とa_4の右上にあり、…ということが成り立つ。(最初に他の頂点の右上になるのがa_1ではなくSの場合もある。)
a_1, a_2, ...として選ぶ意味がある頂点はどのような頂点だろうか? a_kがa_{k-1}の右上にあると仮定すると、一般性を失わず元の点集合にa_{k-1}の左下にある点はないと仮定してよい。なぜなら、そのような点があれば、それを代わりにa_{k-1}とすればよいからである。これを使うと、最適戦略においては以下の2種類の辺しか使われないことがわかる:

  • 各点vについて、vの左下にある頂点wであって、それより左下の点が存在しないような点wへの辺(v, w)
  • SまたはTの右上か左下にある点vへの辺(S, v)あるいは(T, v)

後者の辺はO(N)本しかないのでよい。前者について、もともと頂点集合を座標の辞書順にソートしておけば、辺を伸ばすべき頂点の列はならしO(1)で管理できる。しかし、頂点集合の大きさはO(N)程度であるため、このままではO(N^2)本の辺ができてしまう。これは以下のようにして解決できる。
一般性を失わず(Sの座標) < (Tの座標)とする。最適戦略はジグザグに右に進んでいく戦略である。このとき、辺を伸ばすべき頂点の列をKとして、各点vに対してKのどの点へ辺を伸ばせるかを考える。Kは左上から右下へと進んでいく点列で、座標でソートしている以上Kにはv以下のX座標を持つ点しか登場しないので、vから辺を伸ばせる頂点はY座標がvのY座標以下の点たち、つまりKの途中から最後まで、あるいは空列である。この列の先頭と最後をそれぞれst, enと呼ぶことにし、有向辺st -> v, v -> en を張り、enからstへ向かってKの頂点の間に逆向きに大きさ0の有向辺を張ることにする。(座標空間内では右下から左上に辺が伸びる。) こうすると、上で考慮した辺を張るのと同等であることがわかる。大きさ0の有向辺は別のvに対しても共有できるので、合計で張られる辺の総数はO(N)である。
こうしてできたグラフの上でダイクストラ法をすれば答えが計算できる。計算量はO(N log N)である。

登場する典型

  • 最適戦略の形を考える

実装上の注意点

  • 問題のグラフは無向グラフだが、長さ0の有向辺を追加するのでSとTの順番には気をつける必要がある。

提出: Submission #4316925 - 全国統一プログラミング王決定戦本戦 (Rust)

// Dijkstra省略

fn calc(xyc: &[(i64, i64, i64)],
        pool: &[(i64, i64, i64, usize)], s: usize, t: usize)
        -> i64 {
    let n = pool.len();
    let mut edges = vec![];
    let mut dedges = vec![];
    let mut st: Vec<(i64, usize)> = vec![];
    for &(_x, y, cost, curi) in pool {
        let mut added = true;
        if let Some(&(top, _idx)) = st.last() {
            if top <= y {
                added = false;
            }
        }
        if added {
            st.push((y, curi));
            if st.len() >= 2 {
                let other = st[st.len() - 2].1;
                dedges.push((curi, other, 0)); // reverse edge
            }
        } else {
            let mut fail = -1;
            let mut pass = st.len() as i64 - 1;
            while pass - fail > 1 {
                let mid = ((pass + fail) / 2) as usize;
                let (ym, _idxm) = st[mid];
                if ym <= y {
                    pass = mid as i64;
                } else {
                    fail = mid as i64;
                }
            }
            let pass = pass as usize;
            dedges.push((st[pass].1, curi, cost));
            dedges.push((curi, st[st.len() - 1].1, cost));
        }
    }
    for &v in &[s, t] {
        for i in 0..n {
            if i == v { continue; }
            if xyc[i].0 <= xyc[v].0 && xyc[i].1 <= xyc[v].1 {
                edges.push((i, v, xyc[v].2));
            }
            if xyc[i].0 >= xyc[v].0 && xyc[i].1 >= xyc[v].1 {
                edges.push((i, v, xyc[i].2));
            }
        }
    }
    let mut dijk = Dijkstra::new(n);
    for (u, v, x) in edges {
        dijk.add_edge(u, v, x);
        dijk.add_edge(v, u, x);
    }
    for (u, v, x) in dedges {
        dijk.add_edge(u, v, x);
    }
    let ans = dijk.solve(s, t, 1 << 57);
    ans
}
 
fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        n: usize,
        s: usize1,
        t: usize1,
        xyc: [(i64, i64, i64); n]
    }
    let mut s = s;
    let mut t = t;
    // s comes before t in the lexicographical order
    if xyc[t] < xyc[s] {
        std::mem::swap(&mut s, &mut t);
    }
    let mut pool = vec![];
    for i in 0..n {
        let (x, y, c) = xyc[i];
        pool.push((x, y, c, i));
    }
    pool.sort();
    let ans = calc(&xyc, &pool, s, t);
    puts!("{}\n", ans);
}

まとめ

本番重み0の辺を張ればよさそうなことまでは気付けたが、逆向きの有向辺にすることを思いつかず爆死した。kanasii
この解法はcatupperさんのツイートを参考にして書いた。