みんなのプロコン2018 決勝 A- Uncommon
解法
ある整数 i について配列内の i と互いに素な整数の数を数えるのは大変そうなので、i と互いに素でない数を数えることにする。
i を素因数分解し、例えば素因数が p, q, r だったとき、配列 a に含まれる i と互いに素でないでない整数の数は以下のように求められる。
(配列 a に含まれる i と互いに素でないでない整数の数) = (配列 a に含まれる p の倍数の数) + (配列 a に含まれる q の倍数の数) + (配列 a に含まれる r の倍数の数) - (配列 a に含まれる p*q の倍数の数) - (配列 a に含まれる q*r の倍数の数) - (配列 a に含まれる r*p の倍数の数) + (配列 a に含まれる p*q*r の倍数の数)
配列 a 内の中にある x の倍数の数をカウントしたいが、 は なので、以下のような愚直なループで求まる。
for x in 2..n: cur = x while cur <= max: sum[x] += count[cur] cur += x
コード
/// Thank you tanakh!!! /// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let mut s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::<Vec<char>>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } fn get_primes(n: usize) -> Vec<usize> { let mut is_prime = vec![true; n + 1]; is_prime[0] = false; is_prime[1] = false; let mut primes = vec![]; for i in 2..(n + 1) { if is_prime[i] { primes.push(i); let mut pos = i * 2; while pos < is_prime.len() { is_prime[pos] = false; pos += i; } } } primes } use std::collections::BTreeSet; fn main() { input!(n: usize, m: usize, a: [usize; n]); let primes = get_primes(350); let mut divisors = vec![vec![]; m + 1]; let mut set = BTreeSet::new(); for i in 1..(m + 1) { let mut a = i; for &prime in primes.iter() { if a % prime == 0 { divisors[i].push(prime); set.insert(prime); while a % prime == 0 { a /= prime; } } if prime * prime > a { break; } } if a > 1 { divisors[i].push(a); set.insert(a); } } let max: usize = *a.iter().max().unwrap(); let mut a_count = vec![0; max + 1]; for &a in a.iter() { a_count[a] += 1; } let mut divide_count = vec![0; m + 1]; for i in 2..(m + 1) { let mut cur = i; let mut count = 0; while cur <= max { count += a_count[cur]; cur += i; } divide_count[i] = count; } for i in 1..(m + 1) { let divisors = &divisors[i]; let n = divisors.len(); let mut ans: i64 = 0; for mask in 1..(1 << n) { let mut count_ones = 0; let mut t = 1; for i in 0..n { if mask & (1 << i) != 0 { t *= divisors[i]; count_ones += 1; } } let sum = divide_count[t] as i64; let sum = if count_ones % 2 == 1 { sum } else { -sum }; ans += sum; } println!("{}", a.len() as i64 - ans); } }
AtCoder Regular Contest 101 D - Median of Medians
解法
完全に解法の通り。
- 全ての連続部分列のうち、中央値が x 以上であるものがいくつあるかを考える問題になる。
- 数列の中央値が x 以上である。 => 数列の各要素を x 以上なら 1 そうでなければ -1 に置き換えた時に数列の和が 0 以上である。
- 我が 0 以上になる連続部分列の数を求めたい。 => 累積和をとって転倒数を調べれば良い(これすごく頭いい変形だと思うけど典型っぽい)
コード
/// Thank you tanakh!!! /// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let mut s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::<Vec<char>>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } use std::collections::{BTreeMap, BTreeSet}; use std::ops::{AddAssign, Sub}; fn main() { input!(n: usize, a: [i64; n]); let mut ok = 0; let mut ng = 1e10 as i64; while ng - ok > 1 { let x = (ng + ok) / 2; let a = a .iter() .map(|&a| if a < x { -1 } else { 1 }) .collect::<Vec<_>>(); let mut sum = vec![0; n + 1]; for i in 0..n { sum[i + 1] = sum[i] + a[i]; } let mut set = BTreeSet::new(); for i in 0..(n + 1) { set.insert(sum[i]); } let mut map = BTreeMap::new(); for (i, &x) in set.iter().enumerate() { map.insert(x, i); } let mut compact = vec![0; n + 1]; for i in 0..(n + 1) { compact[i] = *map.get(&sum[i]).unwrap(); } let m = map.len(); let mut ans = 0; let mut bit = FenwickTree::new(m, 0); for i in 0..(n + 1) { ans += bit.sum_one(compact[i] + 1); bit.add(compact[i], 1); } let total = n * (n - 1) / 2 + n; let half = (total + 1) / 2; if ans >= half { ok = x; } else { ng = x; } } println!("{}", ok); } pub struct FenwickTree<T> { n: usize, data: Vec<T>, init: T, } impl<T: Copy + AddAssign + Sub<Output = T>> FenwickTree<T> { /// Constructs a new `FenwickTree`. The size of `FenwickTree` should be specified by `size`. pub fn new(size: usize, init: T) -> FenwickTree<T> { FenwickTree { n: size + 1, data: vec![init; size + 1], init: init, } } pub fn add(&mut self, k: usize, value: T) { let mut x = k; while x < self.n { self.data[x] += value; x |= x + 1; } } /// Returns a sum of range `[l, r)` pub fn sum(&self, l: usize, r: usize) -> T { self.sum_one(r) - self.sum_one(l) } /// Returns a sum of range `[0, k)` pub fn sum_one(&self, k: usize) -> T { if k >= self.n { panic!(""); } let mut result = self.init; let mut x = k as i32 - 1; while x >= 0 { result += self.data[x as usize]; x = (x & (x + 1)) - 1; } result } }
lowlink, 橋や関節点について練習
lowlink や橋や関節点について、いくつか問題を解いたのでリンクを貼っておく。
関節点・橋の確認用問題
AOJ 3022: Cluster Network
解法
雰囲気から、関節点を求める機運が高まるが、実際の問題はその後に最後の答えを出力するパートである。
http://web-ext.u-aizu.ac.jp/circles/acpc/commentary/ACPC2017Day2/J.pdf
解説 PDF にあるとおり、 DFS Tree において、頂点 i と、その子 v について lowlink[v] < order[i] が成り立つならば、 v を根とする部分木と i の親は後退辺によって連結である、という性質を利用する。
コード
/// Thank you tanakh!!! /// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let mut s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::<Vec<char>>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } use std::cmp; use std::collections::{BTreeSet, VecDeque}; const INF: usize = 1e15 as usize; fn main() { input!( n: usize, m: usize, power: [usize; n], edges: [(usize1, usize1); m] ); let mut graph = vec![vec![]; n]; for &(u, v) in edges.iter() { graph[v].push(u); graph[u].push(v); } let bridge_detector = BridgeDetector::new(&graph); let total: usize = power.iter().sum(); let mut is_articulation = vec![false; n]; for &v in bridge_detector.articulations.iter() { is_articulation[v] = true; } let mut dp = vec![INF; n]; let tree = bridge_detector.dfs_tree; let low_link = bridge_detector.low_link; let order = bridge_detector.order; for i in 0..n { if is_articulation[i] { let mut max_child = 0; let mut connected_to_parent = 0; for &child in tree[i].iter() { let dp_child = dfs(child, &tree, &mut dp, &power); max_child = cmp::max(max_child, dp_child); if low_link[child] < order[i] { connected_to_parent += dp_child; } } let dp_parent = total - (dfs(i, &tree, &mut dp, &power) - connected_to_parent); println!("{}", cmp::max(dp_parent, max_child)); } else { println!("{}", total - power[i]); } } } fn dfs(v: usize, tree: &Vec<Vec<usize>>, dp: &mut Vec<usize>, power: &Vec<usize>) -> usize { if dp[v] != INF { return dp[v]; } dp[v] = power[v]; for &next in tree[v].iter() { dp[v] += dfs(next, tree, dp, power); } dp[v] } pub struct BridgeDetector { articulations: Vec<usize>, bridges: Vec<(usize, usize)>, visit: Vec<bool>, order: Vec<usize>, low_link: Vec<usize>, k: usize, dfs_tree: Vec<Vec<usize>>, } impl BridgeDetector { pub fn new(graph: &Vec<Vec<usize>>) -> Self { let n = graph.len(); let mut d = BridgeDetector { articulations: vec![], bridges: vec![], visit: vec![false; n], order: vec![0; n], low_link: vec![0; n], k: 0, dfs_tree: vec![vec![]; n], }; d.run(graph); d } fn run(&mut self, graph: &Vec<Vec<usize>>) { let n = graph.len(); for i in 0..n { if !self.visit[i] { self.dfs(i, 0, graph, i); } } } fn dfs(&mut self, v: usize, previous: usize, graph: &Vec<Vec<usize>>, root: usize) { self.visit[v] = true; self.order[v] = self.k; self.k += 1; self.low_link[v] = self.order[v]; let mut is_articulation = false; let mut dimension = 0; for &next in graph[v].iter() { if !self.visit[next] { // The edge (v->next) is not a backedge. self.dfs_tree[v].push(next); dimension += 1; self.dfs(next, v, graph, root); self.low_link[v] = cmp::min(self.low_link[v], self.low_link[next]); if v != root && self.order[v] <= self.low_link[next] { is_articulation = true; } if self.order[v] < self.low_link[next] { let min = cmp::min(v, next); let max = cmp::max(v, next); self.bridges.push((min, max)); } } else if v == root || next != previous { // The edge (v->next) is a backedge. self.low_link[v] = cmp::min(self.low_link[v], self.order[next]); } } if v == root && dimension > 1 { is_articulation = true; } if is_articulation { self.articulations.push(v); } } }
ARC 039 D - 旅行会社高橋君
解法
橋を2回通らずに A->B->C の移動が出来るかという問題になる。
まず橋を検出し、それらを取り除くと、グラフはいくつかの連結成分に分かれる。各連結成分内では頂点間を移動する経路が常に複数あるため、移動に制限がかからない。これらの連結成分をそれぞれ頂点とし、元のグラフの橋を辺とした木を考える。この木の上で dist(A,B)+dist(B,C)==dist(C,A) ならば A->B->C は同じ橋を 2 回通らずに移動可能である。
コード
/// Thank you tanakh!!! /// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let mut s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::<Vec<char>>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } use std::cmp; use std::collections::{BTreeMap, BTreeSet, VecDeque}; fn main() { input!( n: usize, m: usize, edges: [(usize1, usize1); m], q: usize, queries: [(usize1, usize1, usize1); q] ); solve(n, &edges, &queries); } fn solve(n: usize, edges: &Vec<(usize, usize)>, queries: &Vec<(usize, usize, usize)>) { let bridges = { let mut graph = vec![vec![]; n]; for &(u, v) in edges.iter() { graph[u].push(v); graph[v].push(u); } let mut bridge_detector = BridgeDetector::new(n); bridge_detector.run(&graph); let mut bridges = BTreeSet::new(); for &(a, b) in bridge_detector.bridges.iter() { bridges.insert((a, b)); bridges.insert((b, a)); } bridges }; let mut uf = UnionFind::new(n); for &(a, b) in edges.iter() { if bridges.contains(&(a, b)) { continue; } uf.unite(a, b); } let mut set = BTreeSet::new(); let mut find = vec![0; n]; for i in 0..n { let f = uf.find(i); let cur = set.len(); set.insert(f); if cur == set.len() { find[i] = find[f]; } else { find[f] = cur; find[i] = find[f]; } } let super_tree = { let mut super_tree = vec![vec![]; set.len()]; for &(a, b) in edges.iter() { let a = find[a]; let b = find[b]; if a == b { continue; } super_tree[a].push(b); super_tree[b].push(a); } super_tree }; let lca = LowestCommonAncestor::new(&super_tree); for &(a, b, c) in queries.iter() { let (a, b, c) = (find[a], find[b], find[c]); if lca.get_dist(a, b) + lca.get_dist(b, c) == lca.get_dist(a, c) { println!("OK"); } else { println!("NG"); } } } struct BridgeDetector { articulations: Vec<usize>, bridges: Vec<(usize, usize)>, visit: Vec<bool>, ord: Vec<usize>, low: Vec<usize>, k: usize, } impl BridgeDetector { fn new(n: usize) -> Self { BridgeDetector { articulations: vec![], bridges: vec![], visit: vec![false; n], ord: vec![0; n], low: vec![0; n], k: 0, } } fn run(&mut self, graph: &Vec<Vec<usize>>) { let n = graph.len(); for i in 0..n { if !self.visit[i] { self.dfs(i, None, graph); } } } fn dfs(&mut self, v: usize, p: Option<usize>, graph: &Vec<Vec<usize>>) { self.visit[v] = true; self.ord[v] = self.k; self.k += 1; self.low[v] = self.ord[v]; let mut is_articulation = false; let mut count = 0; for &next in graph[v].iter() { if !self.visit[next] { count += 1; self.dfs(next, Some(v), graph); if self.low[v] > self.low[next] { self.low[v] = self.low[next]; } if p.is_some() && self.ord[v] <= self.low[next] { is_articulation = true; } if self.ord[v] < self.low[next] { let (v, next) = if v < next { (v, next) } else { (next, v) }; self.bridges.push((v, next)); } } else if p.is_none() || next != p.unwrap() && self.low[v] > self.ord[next] { self.low[v] = self.ord[next]; } } if p.is_none() && count > 1 { is_articulation = true; } if is_articulation { self.articulations.push(v); } } } const MAX_PARENT: usize = 1 << 50; pub struct LowestCommonAncestor { parent: Vec<Vec<usize>>, depth: Vec<usize>, log_v: usize, } impl LowestCommonAncestor { pub fn new(graph: &Vec<Vec<usize>>) -> Self { let num_v = graph.len(); let root = 0; let mut depth = vec![0; num_v]; let mut log_v = 1; let mut i = 1; while i <= num_v { i *= 2; log_v += 1; } let mut parent: Vec<Vec<usize>> = vec![vec![0; num_v]; log_v]; let mut depth_vis = vec![false; num_v]; let mut stack = VecDeque::new(); stack.push_front(root); parent[0][root] = MAX_PARENT; depth[root] = 0; depth_vis[root] = true; while !stack.is_empty() { let v = stack.pop_front().unwrap(); stack.push_front(v); for &u in &graph[v] { if depth_vis[u] { continue; } parent[0][u] = v; depth[u] = depth[v] + 1; depth_vis[u] = true; stack.push_front(u); } let head = stack.pop_front().unwrap(); if head != v { stack.push_front(head); } } for k in 0..(log_v - 1) { for u in 0..num_v { parent[k + 1][u] = if parent[k][u] == MAX_PARENT { MAX_PARENT } else { parent[k][parent[k][u]] }; } } LowestCommonAncestor { parent: parent, depth: depth, log_v: log_v, } } pub fn get_lca(&self, u: usize, v: usize) -> usize { let (mut u, mut v) = if self.depth[u] <= self.depth[v] { (u, v) } else { (v, u) }; for k in 0..self.log_v { if ((self.depth[v] - self.depth[u]) & (1 << k)) != 0 { v = self.parent[k][v]; } } if u == v { return u; } for k in (0..self.log_v).rev() { if self.parent[k][u] != self.parent[k][v] { u = self.parent[k][u]; v = self.parent[k][v]; } } return self.parent[0][u]; } pub fn get_dist(&self, u: usize, v: usize) -> usize { let lca = self.get_lca(u, v); self.depth[u] + self.depth[v] - self.depth[lca] * 2 } } pub struct UnionFind { parent: Vec<usize>, sizes: Vec<usize>, size: usize, } impl UnionFind { pub fn new(n: usize) -> UnionFind { UnionFind { parent: (0..n).map(|i| i).collect::<Vec<usize>>(), sizes: vec![1; n], size: n, } } pub fn find(&mut self, x: usize) -> usize { if x == self.parent[x] { x } else { let px = self.parent[x]; self.parent[x] = self.find(px); self.parent[x] } } pub fn unite(&mut self, x: usize, y: usize) -> bool { let parent_x = self.find(x); let parent_y = self.find(y); if parent_x == parent_y { return false; } let (large, small) = if self.sizes[parent_x] < self.sizes[parent_y] { (parent_y, parent_x) } else { (parent_x, parent_y) }; self.parent[small] = large; self.sizes[large] += self.sizes[small]; self.sizes[small] = 0; self.size -= 1; return true; } }
CS Academy: Growing Segment
コード
use std::cmp; use std::collections::BTreeSet; macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let mut s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::<Vec<char>>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } fn main() { input!{ n: usize, q: usize, x: [i64; n], l: [i64; q], } let mut l: Vec<(i64, usize)> = (0..q).map(|i| (l[i], i)).collect(); l.sort(); let mut x = { let mut v: Vec<i64> = vec![0]; for &x in x.iter() { while v.len() >= 2 && (v[v.len() - 2] < v[v.len() - 1]) == (v[v.len() - 1] < x) { v.pop(); } v.push(x); } v }; let mut offset = 0; if x.len() >= 2 && x[1] < 0 { offset = -x[1]; x.remove(0); for x in x.iter_mut() { *x += offset; } } let mut point_set = BTreeSet::new(); for i in 0..x.len() { point_set.insert(i); } let mut edge_set = EdgeSet::new(offset); for i in 1..x.len() { edge_set.insert(i - 1, i, &x); } let mut ans = vec![0; q]; for &(length, ans_id) in l.iter() { while let Some(&(distance, i1, i2)) = edge_set.first() { if distance >= length { break; } if edge_set.set.len() == 1 { break; } if i1 == 0 { let &i3 = point_set.range((i2 + 1)..).next().unwrap(); edge_set.remove(i1, i2, &x); edge_set.remove(i2, i3, &x); x[i2] = length; edge_set.insert(i1, i2, &x); edge_set.insert(i2, i3, &x); continue; } let i3 = point_set.range((i2 + 1)..).next().cloned(); if i3.is_none() { edge_set.remove(i1, i2, &x); point_set.remove(&i2); continue; } let &i0 = point_set.range(..i1).next_back().unwrap(); let i3 = i3.unwrap(); assert!((x[i0] < x[i1]) != (x[i1] < x[i2])); assert!((x[i1] < x[i2]) != (x[i2] < x[i3])); // remove i2 edge_set.remove(i1, i2, &x); edge_set.remove(i2, i3, &x); point_set.remove(&i2); if (x[i0] - x[i1]).abs() > (x[i0] - x[i3]).abs() { // remove i3 let &i4 = point_set.range((i3 + 1)..).next_back().unwrap(); point_set.remove(&i3); edge_set.remove(i3, i4, &x); edge_set.insert(i1, i4, &x); } else { // remove i1 point_set.remove(&i1); edge_set.remove(i0, i1, &x); edge_set.insert(i0, i3, &x); } } ans[ans_id] = cmp::max(0, edge_set.total - (edge_set.set.len() as i64) * length); } for &ans in ans.iter() { println!("{}", ans); } } #[derive(Debug)] struct EdgeSet { set: BTreeSet<(i64, usize, usize)>, total: i64, } impl EdgeSet { fn new(offset: i64) -> Self { EdgeSet { set: BTreeSet::new(), total: offset, } } fn insert(&mut self, from: usize, to: usize, x: &Vec<i64>) { assert!(from < to); let distance = (x[from] - x[to]).abs(); self.set.insert((distance, from, to)); self.total += distance; } fn remove(&mut self, from: usize, to: usize, x: &Vec<i64>) { assert!(from < to); let distance = (x[from] - x[to]).abs(); self.set.remove(&(distance, from, to)); self.total -= distance; } fn first(&self) -> Option<&(i64, usize, usize)> { self.set.iter().next() } }
AtCoder Regular Contest 083 E - Bichrome Tree
解法
頂点 v を根とする部分木で、頂点 v と同じ色の頂点の重みの合計は x[v] だが、同じ色でない頂点の重みの合計は小さければ小さいほどよい。よって、「頂点 v を根とする部分木の、頂点 v と異なる色の頂点の、重みの合計値の最小値」を求めていく。
コード
use std::cmp; const INF: usize = 1e18 as usize; fn dfs(v: usize, parent: usize, x: &Vec<usize>, graph: &Vec<Vec<usize>>) -> usize { let mut dp = vec![INF; x[v] + 1]; dp[0] = 0; for &child in graph[v].iter() { if child == parent { continue; } let white = dfs(child, v, x, graph); let black = x[child]; let mut next = vec![INF; x[v] + 1]; for i in 0..(x[v] + 1) { if dp[i] != INF { if i + white <= x[v] { next[i + white] = cmp::min(next[i + white], dp[i] + black); } if i + black <= x[v] { next[i + black] = cmp::min(next[i + black], dp[i] + white); } } } dp = next; } *dp.iter().min().unwrap() } fn main() { let mut sc = Scanner::new(); let n = sc.read(); let mut graph = vec![vec![]; n]; for i in 0..(n - 1) { let p = sc.read::<usize>() - 1; graph[p].push(i + 1); graph[i + 1].push(p); } let x = sc.read_vec(n); if dfs(0, INF, &x, &graph) != INF { println!("POSSIBLE"); } else { println!("IMPOSSIBLE"); } } 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(); } }