https://atcoder.jp/contests/abc338/tasks/abc338_d
一歩ずつ進みます。例1だとまず1から3ですが、封鎖した橋が1か2なら長さ1、3なら長さ2です。次に3から2ですが、封鎖した橋が1か3なら長さ1、2なら長さ2です。このように同じ長さが続くので、セグメント木を作って、ある範囲に同じ長さを足します。
// Island Tour #![allow(non_snake_case)] use std::cmp::{min, max}; //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::io::stdin().read_line(&mut line).ok(); line.trim().parse().ok().unwrap() } fn read_vec<T: std::str::FromStr>() -> Vec<T> { read::<String>().split_whitespace() .map(|e| e.parse().ok().unwrap()).collect() } //////////////////// Segment Tree //////////////////// const INF: i64 = 10_i64.pow(18); struct SegmentTree { n: usize, v: Vec<i64>, } impl SegmentTree { fn ceil_two_pow(n: usize) -> usize { if n == 1 { 1 } else { SegmentTree::ceil_two_pow((n+1)/2) * 2 } } fn create(m: usize) -> SegmentTree { let n = SegmentTree::ceil_two_pow(m); let mut v: Vec<i64> = vec![0; n*2-1]; for i in n+m-1..n*2-1 { v[i] = INF } SegmentTree { n, v } } fn add_range(&mut self, i: usize, j: usize, v_: usize) { let v: i64 = v_ as i64; self.add(j, v); self.sub(i-1, v) } // add v to [1, right] fn add(&mut self, right: usize, v: i64) { let mut i = right + self.n; if right == self.n { self.v[0] += v } while i > 1 { if (i & 1) == 1 { self.v[i-2] += v } i >>= 1 } } // subtract v to [1, right] fn sub(&mut self, right: usize, v: i64) { let mut i = right + self.n; if right == self.n { self.v[0] -= v } while i > 1 { if (i & 1) == 1 { self.v[i-2] -= v } i >>= 1 } } fn min(&self) -> i64 { self.min_core(0) } fn min_core(&self, i: usize) -> i64 { if i >= self.n - 1 { self.v[i] } else { self.v[i] + min(self.min_core(i*2+1), self.min_core(i*2+2)) } } } //////////////////// process //////////////////// fn read_input() -> (usize, Vec<usize>) { let v = read_vec(); let N = v[0]; let X = read_vec(); (N, X) } fn F(N: usize, X: Vec<usize>) -> i64 { let mut raq = SegmentTree::create(N); for i in 0..X.len()-1 { let u = min(X[i], X[i+1]); let v = max(X[i], X[i+1]); if u == 1 { raq.add_range(1, v-1, N-v+1); raq.add_range(v, N, v-1); } else if v == N { raq.add_range(1, u-1, N-u); raq.add_range(u, N-1, u); raq.add_range(N, N, N-u) } else { raq.add_range(1, u-1, v-u); raq.add_range(u, v-1, N-v+u); raq.add_range(v, N, v-u) } } raq.min() } fn main() { let (N, X) = read_input(); println!("{}", F(N, X)) }