ABC334 F - Christmas Present 2 双対セグ木または遅延セグ木による別解

atcoder.jp

問題の要約

2次元平面上に自分の家と順番に行かなければならないN個の家があり、自分の家を介さずに連続で行ける家はK個までである。このとき、自分の家を出て時々家に戻りつつN個の家に順番に行った後に家に戻るまでの最短距離を求めよ。

解法

家に順番に行きながら、DPテーブルの値を書き換えていくことを考える。
\mathrm{DP}[i]を、今からi人目までは家に戻らずにそのまま行けるときの最短距離と定義する。
まず、まだ家に戻る必要がない場合はそのまま行く方法のみが最短の候補となるため、家に戻る必要がない区間のテーブルにその距離を加算したい。
また、(i-1)人目の家まで自分の家に戻らずに行ける場合は、i人目の家にいくときに自分の家に戻ってから行く場合が最短となることがある。
したがって、(i-1)人目の家とi人目の家の間に自分の家に戻った場合そのまま行ける区間のテーブルをその距離でchminしたい。
この2つの処理はともに区間変更であるが、両方の操作は1つの双対セグ木または遅延セグ木で行える。

演算

作用をF(x;a,b)=\min\{x+a,b\}で定義する。f(x)=F(x;a_f,b_f),\ g(x)=F(x;a_g,b_g)とおくと
\begin{align*}f(g(x))&=\min\{\min\{x+a_g,b_g\}+a_f,b_f\}\\&=\min\{x+a_f+a_g,\min\{a_f+b_g,b_f\}\}\\&=F(x;a_f+a_g,\min\{a_f+b_g,b_f\})\end{align*}
となる。
適当な最大元Mを用意しておき、恒等写像はF(x;0,M)とする。

遅延セグ木で実装する際のモノイドは必須ではないが、たとえば\min\{x,y\}とすればよい。

実装

Rustでac-library-rsのLazySegtreeを使用。

use ac_library::{Monoid, MapMonoid, LazySegtree};

fn main() {
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
        };
    }

    input!(n:usize,k:usize,mut xy:[(f64,f64);n+1]);
    let mut dp=LazySegtree::<MinAndAdd>::new(n+1);
    dp.set(0, 0.);
    for i in 1..=n {
        dp.apply_range(i..=n, (hypot(xy[i-1], xy[i]), 1e18));
        let have_nothing=dp.get(i-1);
        dp.apply_range(i..=min(n, i-1+k), (0., have_nothing+hypot(xy[i-1], xy[0])+hypot(xy[i], xy[0])));
    }
    println!("{}", dp.get(n)+hypot(xy[n], xy[0]));
}

fn min<T>(a: T, b: T) -> T where T: PartialOrd {
    if a<b {
        a
    } else {
        b
    }
}

fn hypot(a: (f64, f64), b: (f64, f64)) -> f64 {
    ((a.0-b.0).powi(2)+(a.1-b.1).powi(2)).sqrt()
}

struct Min;

impl Monoid for Min {
    type S = f64;
    fn identity() -> Self::S {
        1e18
    }
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        min(*a, *b)
    }
}

struct MinAndAdd;

impl MapMonoid for MinAndAdd {
    type M = Min;
    type F = (f64, f64);
    fn identity_map() -> Self::F {
        (0., 1e18)
    }
    fn mapping(f: &Self::F, x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S {
        min(x+f.0, f.1)
    }
    fn composition(f: &Self::F, g: &Self::F) -> Self::F {
        (f.0+g.0, min(f.0+g.1, f.1))
    }
}

atcoder.jp

独り言

作用はトロピカル半環におけるアフィン変換である。
線形変換ではないにせよ、トロピカル線形代数による最短経路問題の求解と関係があるのかもしれない。