Battle Conference U30 - Programming Battle F - 数列と計算
コード
use std::ops::*; const MOD: usize = 1e9 as usize + 7; fn main() { let mut sc = Scanner::new(); let n = sc.read(); let a: Vec<usize> = sc.read_vec(n); let mut pow2 = vec![ModInt::new(1); n + 1]; for i in 1..(n + 1) { pow2[i] = pow2[i - 1] * 2; } let mut dp = vec![ModInt::new(0); n + 1]; let mut sum = ModInt::new(0); let mut mul = ModInt::new(a[0]); for i in 0..n { dp[i + 1] = sum + mul; sum += dp[i + 1]; if i < n - 1 { mul = (mul + pow2[i]) * a[i + 1]; } } println!("{}", dp[n].value); } #[derive(Copy)] pub struct ModInt<T> { value: T, modulo: T, } impl<T> Clone for ModInt<T> where T: Copy, { fn clone(&self) -> Self { ModInt { value: self.value, modulo: self.modulo, } } fn clone_from(&mut self, source: &ModInt<T>) { self.value = source.value; self.modulo = source.modulo; } } impl<T> Add<ModInt<T>> for ModInt<T> where T: Add<Output = T> + Sub<Output = T> + Copy + PartialOrd, { type Output = ModInt<T>; fn add(self, rhs: ModInt<T>) -> ModInt<T> { self + rhs.value } } impl<T> Add<T> for ModInt<T> where T: Add<Output = T> + Sub<Output = T> + Copy + PartialOrd, { type Output = ModInt<T>; fn add(self, rhs: T) -> ModInt<T> { let m = self.modulo; let mut t = rhs + self.value; if t >= m { t = t - m; } ModInt { value: t, modulo: self.modulo, } } } impl<T> Sub<T> for ModInt<T> where T: PartialOrd + Copy + Add<Output = T> + Sub<Output = T> + Rem<Output = T>, { type Output = ModInt<T>; fn sub(self, rhs: T) -> ModInt<T> { let rhs = if rhs >= self.modulo { rhs % self.modulo } else { rhs }; let value = if self.value < rhs { self.value + self.modulo } else { self.value }; ModInt { value: value - rhs, modulo: self.modulo, } } } impl<T> Sub<ModInt<T>> for ModInt<T> where T: PartialOrd + Copy + Add<Output = T> + Sub<Output = T> + Rem<Output = T>, { type Output = ModInt<T>; fn sub(self, rhs: ModInt<T>) -> ModInt<T> { self - rhs.value } } impl<T> AddAssign<T> for ModInt<T> where T: Add<Output = T> + Sub<Output = T> + Copy + PartialOrd, { fn add_assign(&mut self, other: T) { *self = *self + other; } } impl<T> AddAssign<ModInt<T>> for ModInt<T> where T: Add<Output = T> + Sub<Output = T> + Copy + PartialOrd, { fn add_assign(&mut self, other: ModInt<T>) { *self = *self + other; } } impl<T> Mul<ModInt<T>> for ModInt<T> where T: Mul<Output = T> + Rem<Output = T> + Copy, { type Output = ModInt<T>; fn mul(self, rhs: ModInt<T>) -> ModInt<T> { self * rhs.value } } impl<T> Mul<T> for ModInt<T> where T: Mul<Output = T> + Rem<Output = T> + Copy, { type Output = ModInt<T>; fn mul(self, rhs: T) -> ModInt<T> { let t = (self.value * rhs) % self.modulo; ModInt { value: t, modulo: self.modulo, } } } impl<T> MulAssign<T> for ModInt<T> where T: Mul<Output = T> + Rem<Output = T> + Copy, { fn mul_assign(&mut self, rhs: T) { *self = *self * rhs; } } impl<T> MulAssign<ModInt<T>> for ModInt<T> where T: Mul<Output = T> + Rem<Output = T> + Copy, { fn mul_assign(&mut self, rhs: ModInt<T>) { *self = *self * rhs; } } impl ModInt<usize> { fn new(x: usize) -> Self { ModInt { value: x, modulo: MOD, } } } struct Scanner { ptr: usize, length: usize, buf: Vec<u8>, small_cache: Vec<u8>, } #[allow(dead_code)] impl Scanner { fn new() -> Scanner { Scanner { ptr: 0, length: 0, buf: vec![0; 1024], small_cache: vec![0; 1024], } } fn load(&mut self) { use std::io::Read; let mut s = std::io::stdin(); self.length = s.read(&mut self.buf).unwrap(); } fn byte(&mut self) -> u8 { if self.ptr >= self.length { self.ptr = 0; self.load(); if self.length == 0 { self.buf[0] = b'\n'; self.length = 1; } } self.ptr += 1; return self.buf[self.ptr - 1]; } fn is_space(b: u8) -> bool { b == b'\n' || b == b'\r' || b == b'\t' || b == b' ' } fn read_vec<T>(&mut self, n: usize) -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug, { (0..n).map(|_| self.read()).collect() } fn usize_read(&mut self) -> usize { self.read() } fn read<T>(&mut self) -> T where T: std::str::FromStr, T::Err: std::fmt::Debug, { let mut b = self.byte(); while Scanner::is_space(b) { b = self.byte(); } for pos in 0..self.small_cache.len() { self.small_cache[pos] = b; b = self.byte(); if Scanner::is_space(b) { return String::from_utf8_lossy(&self.small_cache[0..(pos + 1)]) .parse() .unwrap(); } } let mut v = self.small_cache.clone(); while !Scanner::is_space(b) { v.push(b); b = self.byte(); } return String::from_utf8_lossy(&v).parse().unwrap(); } }
AtCoder Regular Contest 081 F - Flip and Rectangles
コード
use std::cmp; use std::collections::VecDeque; trait TopQueue<T> { fn top(&self) -> &T; } impl<T> TopQueue<T> for VecDeque<T> { fn top(&self) -> &T { self.iter().next().unwrap() } } fn calc_area(height: usize, width: usize) -> usize { (height + 1) * (width + 1) } fn calc_max_rectangle(hist: &Vec<usize>) -> usize { let n = hist.len(); let mut ans = 0; let mut stack: VecDeque<(usize, usize)> = VecDeque::new(); for i in 0..n { let mut reachable_min = i; while !stack.is_empty() && stack.top().1 > hist[i] { let (pos, height) = stack.pop_front().unwrap(); reachable_min = pos; let area = calc_area(height, i - reachable_min); ans = cmp::max(ans, area); } if stack.is_empty() || stack.top().1 < hist[i] { stack.push_front((reachable_min, hist[i])); } } while !stack.is_empty() { let (pos, height) = stack.pop_front().unwrap(); let area = calc_area(n - pos, height); ans = cmp::max(ans, area); } ans } fn main() { let mut sc = Scanner::new(); let h = sc.read(); let w: usize = sc.read(); let a: Vec<Vec<usize>> = (0..h) .map(|_| { sc.read::<String>() .chars() .map(|c| if c == '#' { 1 } else { 0 }) .collect() }).collect(); let w = w - 1; let h = h - 1; let mut map = vec![vec![false; w]; h]; for i in 0..h { for j in 0..w { let s = a[i][j] + a[i][j + 1] + a[i + 1][j] + a[i + 1][j + 1]; map[i][j] = s % 2 == 0; } } let mut hist = vec![vec![0; w]; h]; for i in 0..h { for j in 0..w { if !map[i][j] { continue; } if i == 0 { hist[i][j] = 1; } else { hist[i][j] = hist[i - 1][j] + 1; } } } let mut ans = cmp::max(w + 1, h + 1); for i in 0..h { ans = cmp::max(ans, calc_max_rectangle(&hist[i])); } println!("{}", ans); } trait CppDeque<S> { fn top(&mut self) -> S; } struct Scanner { ptr: usize, length: usize, buf: Vec<u8>, small_cache: Vec<u8>, } #[allow(dead_code)] impl Scanner { fn new() -> Scanner { Scanner { ptr: 0, length: 0, buf: vec![0; 1024], small_cache: vec![0; 1024], } } fn load(&mut self) { use std::io::Read; let mut s = std::io::stdin(); self.length = s.read(&mut self.buf).unwrap(); } fn byte(&mut self) -> u8 { if self.ptr >= self.length { self.ptr = 0; self.load(); if self.length == 0 { self.buf[0] = b'\n'; self.length = 1; } } self.ptr += 1; return self.buf[self.ptr - 1]; } fn is_space(b: u8) -> bool { b == b'\n' || b == b'\r' || b == b'\t' || b == b' ' } fn read_vec<T>(&mut self, n: usize) -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug, { (0..n).map(|_| self.read()).collect() } fn usize_read(&mut self) -> usize { self.read() } fn read<T>(&mut self) -> T where T: std::str::FromStr, T::Err: std::fmt::Debug, { let mut b = self.byte(); while Scanner::is_space(b) { b = self.byte(); } for pos in 0..self.small_cache.len() { self.small_cache[pos] = b; b = self.byte(); if Scanner::is_space(b) { return String::from_utf8_lossy(&self.small_cache[0..(pos + 1)]) .parse() .unwrap(); } } let mut v = self.small_cache.clone(); while !Scanner::is_space(b) { v.push(b); b = self.byte(); } return String::from_utf8_lossy(&v).parse().unwrap(); } }
AOJ Largest Rectangle
解法
各列についてヒストグラムに内接する最大長方形を求める。
コード
use std::cmp; use std::collections::VecDeque; trait TopQueue<T> { fn top(&self) -> &T; } impl<T> TopQueue<T> for VecDeque<T> { fn top(&self) -> &T { assert!(!self.is_empty()); self.iter().next().unwrap() } } fn f(hist: &Vec<usize>) -> usize { let n = hist.len(); let mut ans = 0; let mut q: VecDeque<(usize, usize)> = VecDeque::new(); for i in 0..n { let mut reachable_min = i; while !q.is_empty() && q.top().1 > hist[i] { let (pos, height) = q.pop_front().unwrap(); reachable_min = pos; ans = cmp::max(ans, (i - reachable_min) * height); } if q.is_empty() || q.top().1 < hist[i] { q.push_front((reachable_min, hist[i])); } } while !q.is_empty() { let (pos, height) = q.pop_front().unwrap(); ans = cmp::max(ans, (n - pos) * height); } ans } fn main() { let mut sc = Scanner::new(); let h = sc.read(); let w = sc.read(); let mut c = vec![vec![false; w]; h]; for i in 0..h { for j in 0..w { c[i][j] = sc.read::<usize>() == 0; } } let mut hist = vec![vec![0; w]; h]; for i in 0..h { for j in 0..w { if !c[i][j] { continue; } if i == 0 { hist[i][j] = 1; } else { hist[i][j] = hist[i - 1][j] + 1; } } } let mut ans = 0; for i in 0..h { ans = cmp::max(ans, f(&hist[i])); } println!("{}", ans); } struct Scanner { ptr: usize, length: usize, buf: Vec<u8>, small_cache: Vec<u8>, } #[allow(dead_code)] impl Scanner { fn new() -> Scanner { Scanner { ptr: 0, length: 0, buf: vec![0; 1024], small_cache: vec![0; 1024], } } fn load(&mut self) { use std::io::Read; let mut s = std::io::stdin(); self.length = s.read(&mut self.buf).unwrap(); } fn byte(&mut self) -> u8 { if self.ptr >= self.length { self.ptr = 0; self.load(); if self.length == 0 { self.buf[0] = b'\n'; self.length = 1; } } self.ptr += 1; return self.buf[self.ptr - 1]; } fn is_space(b: u8) -> bool { b == b'\n' || b == b'\r' || b == b'\t' || b == b' ' } fn read_vec<T>(&mut self, n: usize) -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug, { (0..n).map(|_| self.read()).collect() } fn usize_read(&mut self) -> usize { self.read() } fn read<T>(&mut self) -> T where T: std::str::FromStr, T::Err: std::fmt::Debug, { let mut b = self.byte(); while Scanner::is_space(b) { b = self.byte(); } for pos in 0..self.small_cache.len() { self.small_cache[pos] = b; b = self.byte(); if Scanner::is_space(b) { return String::from_utf8_lossy(&self.small_cache[0..(pos + 1)]) .parse() .unwrap(); } } let mut v = self.small_cache.clone(); while !Scanner::is_space(b) { v.push(b); b = self.byte(); } return String::from_utf8_lossy(&v).parse().unwrap(); } }
AtCoder Regular Contest 073 E - Ball Coloring
解法
解説のとおりだが、個人的には理解が難しかった。(分かると簡単シリーズ)
最小のボールが青、最大のボールが赤のとき
最小のボールを持つ青は、残りのボールをできるだけ小さくしたい。最大のボールを持つ赤は残りのボールをできるだけ大きくしたい。なので、各ペアの小さいボールを青に、大きいボールを赤に塗れば良い。
最小のボールも最大のボールも赤に塗られているとき
まずは各ペアの小さい方のボールを青に塗る。青側の最小値を大きく、最大値を小さくしたいお気持ちだが、最大値は小さくはならない(大きくなることはある)。なので、最小値を大きくすることだけを考える。
各ペアを、小さい方のボールの昇順にソートしたとき、 i 番目のペアでは小さいほうが青に、大きい方が赤に塗られているが、これを入れ替えることを検討する。 k 番目のペアの小さい方を青にしたままの場合、 k+1 番目以降のペアをいくら入れ替えても青側の最小値は大きくならないので、i 番目のペアを入れ替えることを検討している時は、それより前のペアは全て入れ替わっていると考えて良い。
i 番目のペアを入れ替えた場合、青側のボールは {1〜i 番目のペアの大きい方のボール}
+ {i+1〜n 番目のペアの小さい方のボール} になる。これらの最大値・最小値を求めれば、「i 番目まで入れ替えたときの求める値」が計算できるのでこれを 1 〜 n 番目まで計算すれば良い。
コード
use std::cmp; fn main() { let mut sc = Scanner::new(); let n = sc.read(); let mut x: Vec<usize> = vec![0; n]; let mut y: Vec<usize> = vec![0; n]; for i in 0..n { x[i] = sc.read(); y[i] = sc.read(); } let mut small = vec![]; let mut large = vec![]; for i in 0..n { small.push(cmp::min(x[i], y[i])); large.push(cmp::max(x[i], y[i])); } let &small_min = small.iter().min().unwrap(); let &small_max = small.iter().max().unwrap(); let &large_min = large.iter().min().unwrap(); let &large_max = large.iter().max().unwrap(); let mut ans = (small_max - small_min) * (large_max - large_min); let worst_side = large_max - small_min; let mut max = small_max; let mut min = 1e15 as usize; let mut v = vec![]; for i in 0..n { v.push((small[i], large[i])); } v.sort(); for i in 0..(n - 1) { let (_, large) = v[i]; let (next_small, _) = v[i + 1]; min = cmp::min(min, large); max = cmp::max(max, large); let tmp_min = cmp::min(min, next_small); ans = cmp::min(ans, (max - tmp_min) * worst_side); } println!("{}", ans); } struct Scanner { ptr: usize, length: usize, buf: Vec<u8>, small_cache: Vec<u8>, } #[allow(dead_code)] impl Scanner { fn new() -> Scanner { Scanner { ptr: 0, length: 0, buf: vec![0; 1024], small_cache: vec![0; 1024], } } fn load(&mut self) { use std::io::Read; let mut s = std::io::stdin(); self.length = s.read(&mut self.buf).unwrap(); } fn byte(&mut self) -> u8 { if self.ptr >= self.length { self.ptr = 0; self.load(); if self.length == 0 { self.buf[0] = b'\n'; self.length = 1; } } self.ptr += 1; return self.buf[self.ptr - 1]; } fn is_space(b: u8) -> bool { b == b'\n' || b == b'\r' || b == b'\t' || b == b' ' } fn read_vec<T>(&mut self, n: usize) -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug, { (0..n).map(|_| self.read()).collect() } fn usize_read(&mut self) -> usize { self.read() } fn read<T>(&mut self) -> T where T: std::str::FromStr, T::Err: std::fmt::Debug, { let mut b = self.byte(); while Scanner::is_space(b) { b = self.byte(); } for pos in 0..self.small_cache.len() { self.small_cache[pos] = b; b = self.byte(); if Scanner::is_space(b) { return String::from_utf8_lossy(&self.small_cache[0..(pos + 1)]) .parse() .unwrap(); } } let mut v = self.small_cache.clone(); while !Scanner::is_space(b) { v.push(b); b = self.byte(); } return String::from_utf8_lossy(&v).parse().unwrap(); } }
AtCoder Regular Contest 077 E - guruguru
コード
use std::cmp; use std::collections::BinaryHeap; #[derive(Copy, Clone, Eq, PartialEq, Debug)] struct Seg { head: usize, tail: usize, } impl Ord for Seg { fn cmp(&self, other: &Seg) -> cmp::Ordering { other.tail.cmp(&self.tail) } } impl PartialOrd for Seg { fn partial_cmp(&self, other: &Seg) -> Option<cmp::Ordering> { Some(self.cmp(other)) } } fn main() { let mut sc = Scanner::new(); let n = sc.read(); let m = sc.read(); let a: Vec<usize> = sc.read_vec(n); let mut tails: Vec<Vec<usize>> = vec![vec![]; m]; let mut total_distance = 0; let mut current_decrease = 0; let mut decreased_segments = BinaryHeap::new(); for i in 1..n { let from = a[i - 1] - 1; let to = a[i] - 1; let distance = (to + m - from) % m; total_distance += distance; if from > to { let warped = m - from - 1; current_decrease += warped; decreased_segments.push(Seg { head: from, tail: to, }); tails[from].push(to + m); } else { tails[from].push(to); } } let mut ans = total_distance - current_decrease; for x in 1..m { while let Some(Seg { head, tail }) = decreased_segments.pop() { if tail < x { assert!(tail == x - 1); current_decrease -= (tail + m - head) % m - 1; } else { decreased_segments.push(Seg { head: head, tail: tail, }); break; } } current_decrease += decreased_segments.len(); ans = cmp::min(ans, total_distance - current_decrease); for &tail in tails[x - 1].iter() { decreased_segments.push(Seg { head: x - 1, tail: tail, }); } } println!("{}", ans); } struct Scanner { ptr: usize, length: usize, buf: Vec<u8>, small_cache: Vec<u8>, } #[allow(dead_code)] impl Scanner { fn new() -> Scanner { Scanner { ptr: 0, length: 0, buf: vec![0; 1024], small_cache: vec![0; 1024], } } fn load(&mut self) { use std::io::Read; let mut s = std::io::stdin(); self.length = s.read(&mut self.buf).unwrap(); } fn byte(&mut self) -> u8 { if self.ptr >= self.length { self.ptr = 0; self.load(); if self.length == 0 { self.buf[0] = b'\n'; self.length = 1; } } self.ptr += 1; return self.buf[self.ptr - 1]; } fn is_space(b: u8) -> bool { b == b'\n' || b == b'\r' || b == b'\t' || b == b' ' } fn read_vec<T>(&mut self, n: usize) -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug, { (0..n).map(|_| self.read()).collect() } fn usize_read(&mut self) -> usize { self.read() } fn read<T>(&mut self) -> T where T: std::str::FromStr, T::Err: std::fmt::Debug, { let mut b = self.byte(); while Scanner::is_space(b) { b = self.byte(); } for pos in 0..self.small_cache.len() { self.small_cache[pos] = b; b = self.byte(); if Scanner::is_space(b) { return String::from_utf8_lossy(&self.small_cache[0..(pos + 1)]) .parse() .unwrap(); } } let mut v = self.small_cache.clone(); while !Scanner::is_space(b) { v.push(b); b = self.byte(); } return String::from_utf8_lossy(&v).parse().unwrap(); } }
C - Not Too Close SoundHound Programming Contest 2018 Masters Tournament 本戦 (Open)
解法
解説が全く理解できなかったので下記ブログを参考にした。ありがとうございます。
http://fluffyowl.hatenablog.com/entry/2018/07/31/000800
dp[d][i][j] := 頂点 1 からの距離が d となる頂点までグラフを構築したとき、グラフの頂点数が i で、その中で頂点 1 からの距離が d となる頂点の個数が j であるグラフの組み合わせ
を考える。
距離 d-1 まで構築し終えたとして、グラフ全体の頂点数が used 個、頂点 1 からの距離が d-1 の頂点の数が last 個だとする。
このとき使われていない頂点の数 u は
と表される。(距離が D 以下なら使われていない頂点2は使われていないが、そうでない場合は使われているため。)
また、距離 d の頂点として新たにグラフに使用する頂点の数を using 個とすると、新たにグラフに使用する頂点を選ぶ組み合わせ C は
と表される。 (d=D のときは 2 を必ずグラフに使わなければならないため。)
新たにグラフに使用される using 個の頂点は距離 d となるので、 last 個の頂点のいずれかから辺が張られているはずである。よって using 個の各頂点について、 last 個の頂点への辺の貼り方はそれぞれ 通りあるはずである。 (last 個の頂点のどれに辺を張っても良いが、必ず 1 本は張らなければならないため。)なので last 個の頂点と using この頂点のみからなるサブグラフの組み合わせ E は 通りになる。
新たに追加される using この頂点の間では好きなだけ辺を張って良い。(これら using 個の頂点への頂点 1 からの最短距離は d で変わらないので。)貼りうる辺の本数は なので、組み合わせは 通りになる。
よって dp の更新式は
みたいな感じになる。(雰囲気で式を書いているので数学的な表記じゃないのは許してください)
コード
use std::ops::{Add, AddAssign, Mul, MulAssign, Rem, Sub}; const MOD: usize = 1e9 as usize + 7; fn main() { let mut sc = Scanner::new(); let n: usize = sc.read(); let d: usize = sc.read(); let combination = Combination::new(n, MOD); let mut dp = vec![vec![vec![ModInt::new(0); n + 1]; n + 1]; n]; dp[0][1][1] = ModInt::new(1); for distance in 1..n { for using in 1..(n + 1) { for used in 1..(n + 1) { if using + used > n { continue; } for last in 1..(n + 1) { let unused = if distance <= d { n - used - 1 } else { n - used }; let using_not_2 = if distance == d { using - 1 } else { using }; if unused < using_not_2 { continue; } let combination = combination.get(unused, using_not_2); let edges_from_last_to_using = mod_pow((1 << last) - 1, using); let possible_edge_num_in_using_sub_graph = using * (using - 1) / 2; let sub_graphs_of_using = mod_pow(2, possible_edge_num_in_using_sub_graph); dp[distance][using + used][using] += dp[distance - 1][used][last] * combination * edges_from_last_to_using * sub_graphs_of_using; } } } } let mut ans = ModInt::new(0); for distance in d..n { for used in (distance + 1)..(n + 1) { for last in 0..(n + 1) { let unconnected_sub_graph = if used + 1 >= n { ModInt::new(1) } else { mod_pow(2, (n - used) * (n - used - 1) / 2) }; ans += dp[distance][used][last] * unconnected_sub_graph; } } } println!("{}", ans.value); } fn mod_pow(x: usize, e: usize) -> ModInt<usize> { let mut result = ModInt::new(1); let mut cur = ModInt::new(x); let mut e = e; while e > 0 { if e & 1 != 0 { result = result * cur; } e /= 2; cur = cur * cur; } result } #[derive(Copy)] pub struct ModInt<T> { value: T, modulo: T, } impl<T> Clone for ModInt<T> where T: Copy, { fn clone(&self) -> Self { ModInt { value: self.value, modulo: self.modulo, } } fn clone_from(&mut self, source: &ModInt<T>) { self.value = source.value; self.modulo = source.modulo; } } impl<T> Add<ModInt<T>> for ModInt<T> where T: Add<Output = T> + Sub<Output = T> + Copy + PartialOrd, { type Output = ModInt<T>; fn add(self, rhs: ModInt<T>) -> ModInt<T> { self + rhs.value } } impl<T> Add<T> for ModInt<T> where T: Add<Output = T> + Sub<Output = T> + Copy + PartialOrd, { type Output = ModInt<T>; fn add(self, rhs: T) -> ModInt<T> { let m = self.modulo; let mut t = rhs + self.value; if t > m { t = t - m; } ModInt { value: t, modulo: self.modulo, } } } impl<T> Sub<T> for ModInt<T> where T: PartialOrd + Copy + Add<Output = T> + Sub<Output = T> + Rem<Output = T>, { type Output = ModInt<T>; fn sub(self, rhs: T) -> ModInt<T> { let rhs = if rhs >= self.modulo { rhs % self.modulo } else { rhs }; let value = if self.value < rhs { self.value + self.modulo } else { self.value }; ModInt { value: value - rhs, modulo: self.modulo, } } } impl<T> Sub<ModInt<T>> for ModInt<T> where T: PartialOrd + Copy + Add<Output = T> + Sub<Output = T> + Rem<Output = T>, { type Output = ModInt<T>; fn sub(self, rhs: ModInt<T>) -> ModInt<T> { self - rhs.value } } impl<T> AddAssign<T> for ModInt<T> where T: Add<Output = T> + Sub<Output = T> + Copy + PartialOrd, { fn add_assign(&mut self, other: T) { *self = *self + other; } } impl<T> AddAssign<ModInt<T>> for ModInt<T> where T: Add<Output = T> + Sub<Output = T> + Copy + PartialOrd, { fn add_assign(&mut self, other: ModInt<T>) { *self = *self + other; } } impl<T> Mul<ModInt<T>> for ModInt<T> where T: Mul<Output = T> + Rem<Output = T> + Copy, { type Output = ModInt<T>; fn mul(self, rhs: ModInt<T>) -> ModInt<T> { self * rhs.value } } impl<T> Mul<T> for ModInt<T> where T: Mul<Output = T> + Rem<Output = T> + Copy, { type Output = ModInt<T>; fn mul(self, rhs: T) -> ModInt<T> { let t = (self.value * rhs) % self.modulo; ModInt { value: t, modulo: self.modulo, } } } impl<T> MulAssign<T> for ModInt<T> where T: Mul<Output = T> + Rem<Output = T> + Copy, { fn mul_assign(&mut self, rhs: T) { *self = *self * rhs; } } impl<T> MulAssign<ModInt<T>> for ModInt<T> where T: Mul<Output = T> + Rem<Output = T> + Copy, { fn mul_assign(&mut self, rhs: ModInt<T>) { *self = *self * rhs; } } impl ModInt<usize> { pub fn new(value: usize) -> ModInt<usize> { ModInt { value: value, modulo: MOD, } } } pub struct Combination { fact: Vec<usize>, inv_fact: Vec<usize>, modulo: usize, } impl Combination { pub fn new(max: usize, modulo: usize) -> Combination { let mut inv = vec![0; max + 1]; let mut fact = vec![0; max + 1]; let mut inv_fact = vec![0; max + 1]; inv[1] = 1; for i in 2..(max + 1) { inv[i] = inv[modulo % i] * (modulo - modulo / i) % modulo; } fact[0] = 1; inv_fact[0] = 1; for i in 0..max { fact[i + 1] = fact[i] * (i + 1) % modulo; } for i in 0..max { inv_fact[i + 1] = inv_fact[i] * inv[i + 1] % modulo; } Combination { fact: fact, inv_fact: inv_fact, modulo: modulo, } } pub fn get(&self, x: usize, y: usize) -> ModInt<usize> { assert!(x >= y); ModInt::new( self.fact[x] * self.inv_fact[y] % self.modulo * self.inv_fact[x - y] % self.modulo, ) } } struct Scanner { ptr: usize, length: usize, buf: Vec<u8>, small_cache: Vec<u8>, } #[allow(dead_code)] impl Scanner { fn new() -> Scanner { Scanner { ptr: 0, length: 0, buf: vec![0; 1024], small_cache: vec![0; 1024], } } fn load(&mut self) { use std::io::Read; let mut s = std::io::stdin(); self.length = s.read(&mut self.buf).unwrap(); } fn byte(&mut self) -> u8 { if self.ptr >= self.length { self.ptr = 0; self.load(); if self.length == 0 { self.buf[0] = b'\n'; self.length = 1; } } self.ptr += 1; return self.buf[self.ptr - 1]; } fn is_space(b: u8) -> bool { b == b'\n' || b == b'\r' || b == b'\t' || b == b' ' } fn read_vec<T>(&mut self, n: usize) -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug, { (0..n).map(|_| self.read()).collect() } fn usize_read(&mut self) -> usize { self.read() } fn read<T>(&mut self) -> T where T: std::str::FromStr, T::Err: std::fmt::Debug, { let mut b = self.byte(); while Scanner::is_space(b) { b = self.byte(); } for pos in 0..self.small_cache.len() { self.small_cache[pos] = b; b = self.byte(); if Scanner::is_space(b) { return String::from_utf8_lossy(&self.small_cache[0..(pos + 1)]) .parse() .unwrap(); } } let mut v = self.small_cache.clone(); while !Scanner::is_space(b) { v.push(b); b = self.byte(); } return String::from_utf8_lossy(&v).parse().unwrap(); } }
CS Academy: Growing Segment
問題
https://csacademy.com/contest/archive/task/growing-segment/
解法
- 削除しても大丈夫な辺を下から見ていく
- x[i] -> x[i+1] を削除するときことを考える
- x[i+1] は削除して問題ないので消す。
- x[i+2] は消せるか? (x[i] をカバーしたときに自動的に x[i-2] もカバーされるか?)
- x[i+2] を消せるとき
- x[i+2] を消す
- x[i] -> x[i+3] に辺を張る
- x[i+2] が消せないとき
- x[i] を消す
- x[i-1] -> x[i+2] に辺を張る
コード
use std::collections::BTreeSet; fn main() { let mut sc = Scanner::new(); let n = sc.read(); let q = sc.read(); let mut x: Vec<i64> = vec![0]; for _ in 0..n { let t = sc.read::<i64>(); if x[x.len() - 1] == t { continue; } if x.len() >= 2 && (x[x.len() - 2] < x[x.len() - 1]) == (x[x.len() - 1] < t) { x.pop(); } x.push(t); } let mut current_difference = 0; if x.len() >= 2 && x[1] < 0 { current_difference -= x[1]; x.remove(0); for x in x.iter_mut() { *x += current_difference; } } // x[even] < x[odd] > x[even] < x[odd] ... let mut index_set = (0..x.len()).collect::<BTreeSet<_>>(); let mut edges = BTreeSet::new(); let mut distance = vec![0; x.len() - 1]; for i in 1..x.len() { distance[i - 1] = (x[i] - x[i - 1]).abs(); current_difference += distance[i - 1]; edges.insert((distance[i - 1], i - 1)); } let mut queries = vec![]; for i in 0..q { queries.push((sc.read::<i64>(), i)); } queries.sort(); let mut prev_query = 0; let mut ans = vec![0; q]; for &(query, ans_index) in queries.iter() { while let Some(&(_, edge_idx)) = edges.first() { let edge_length = distance[edge_idx]; if edge_length > query { break; } edges.remove(&(edge_length, edge_idx)); current_difference -= distance[edge_idx] - prev_query; let &next_idx = index_set.range((edge_idx + 1)..).next().unwrap(); if next_idx < *index_set.last().unwrap() { edges.remove(&(distance[next_idx], next_idx)); current_difference -= distance[next_idx] - prev_query; } index_set.remove(&next_idx); let it = index_set.range((edge_idx + 1)..).next().cloned(); if it.is_none() { continue; } let next_next_idx = it.unwrap(); assert!(edge_idx % 2 == next_next_idx % 2); if (edge_idx % 2 == 0 && x[next_next_idx] >= x[edge_idx]) || (edge_idx % 2 == 1 && x[next_next_idx] <= x[edge_idx]) { // When next_next_idx is removable, if next_next_idx < *index_set.last().unwrap() { edges.remove(&(distance[next_next_idx], next_next_idx)); current_difference -= distance[next_next_idx] - prev_query; } index_set.remove(&next_next_idx); match index_set.range((edge_idx + 1)..).next() { Some(&next_idx) => { distance[edge_idx] = (x[edge_idx] - x[next_idx]).abs(); edges.insert((distance[edge_idx], edge_idx)); current_difference += distance[edge_idx] - prev_query; } _ => {} } } else { // When next_next_idx can not be removed, assert!(index_set.remove(&edge_idx)); match index_set.range(..next_next_idx).next_back() { Some(&prev_idx) => { edges.remove(&(distance[prev_idx], prev_idx)); current_difference -= distance[prev_idx] - prev_query; distance[prev_idx] = (x[prev_idx] - x[next_next_idx]).abs(); edges.insert((distance[prev_idx], prev_idx)); current_difference += distance[prev_idx] - prev_query; } _ => { current_difference += (x[edge_idx] - x[next_next_idx]).abs(); } } } } current_difference -= (query - prev_query) * edges.len() as i64; ans[ans_index] = current_difference; prev_query = query; } for &ans in ans.iter() { println!("{}", ans); } } trait FirstLastElement<K> { fn first(&self) -> Option<&K>; fn last(&self) -> Option<&K>; } impl<K> FirstLastElement<K> for BTreeSet<K> { fn first(&self) -> Option<&K> { self.iter().next() } fn last(&self) -> Option<&K> { self.iter().next_back() } } struct Scanner { ptr: usize, length: usize, buf: Vec<u8>, small_cache: Vec<u8>, } #[allow(dead_code)] impl Scanner { fn new() -> Scanner { Scanner { ptr: 0, length: 0, buf: vec![0; 1024], small_cache: vec![0; 1024], } } fn load(&mut self) { use std::io::Read; let mut s = std::io::stdin(); self.length = s.read(&mut self.buf).unwrap(); } fn byte(&mut self) -> u8 { if self.ptr >= self.length { self.ptr = 0; self.load(); if self.length == 0 { self.buf[0] = b'\n'; self.length = 1; } } self.ptr += 1; return self.buf[self.ptr - 1]; } fn is_space(b: u8) -> bool { b == b'\n' || b == b'\r' || b == b'\t' || b == b' ' } fn read_vec<T>(&mut self, n: usize) -> Vec<T> where T: std::str::FromStr, T::Err: std::fmt::Debug, { (0..n).map(|_| self.read()).collect() } fn usize_read(&mut self) -> usize { self.read() } fn read<T>(&mut self) -> T where T: std::str::FromStr, T::Err: std::fmt::Debug, { let mut b = self.byte(); while Scanner::is_space(b) { b = self.byte(); } for pos in 0..self.small_cache.len() { self.small_cache[pos] = b; b = self.byte(); if Scanner::is_space(b) { return String::from_utf8_lossy(&self.small_cache[0..(pos + 1)]) .parse() .unwrap(); } } let mut v = self.small_cache.clone(); while !Scanner::is_space(b) { v.push(b); b = self.byte(); } return String::from_utf8_lossy(&v).parse().unwrap(); } }