Codeforces Round #787 (Div. 3)
Codeforces Round #787 (Div. 3) です。 ABCDEF 6完でした。
A. Food for Animals
ドッグフードが $x$、キャットフードが $y$ が必要。お店には、ドッグフードが $a$ 個、キャットフードが $b$ 個、どちらも食べられるものが $c$ 個ある。必要個数変えますか？という問題。
専用のものは、そっちを使った方が良いので基本的に $a,b$ を買えるだけ買って、足りない分を $c$ で補うようにする。 $\max(0, x - a) + \max(0, y - b) \leq c $ なら "YES"
fn main() { let t : usize = input(); for _ in 0..t { solve() } } fn solve() { let (a, b, c, x, y) : (usize, usize, usize, usize, usize) = input_t5(); let x = x.saturating_sub(a); let y = y.saturating_sub(b); println!("{}", if (x+y) <= c {"Yes"} else {"No"}); }
B. Make It Increasing
列が与えられるので $a_i = \left \lfloor \frac{a_i}{2} \right \rfloor$ の操作を何回かして、狭義単調増加にできるか。
後ろから貪欲にやると良い。途中で $0$ になると達成できないので -1。
fn main() { let t : usize = input(); for _ in 0..t { solve() } } fn solve() { let n : usize = input(); let mut a : Vec<usize> = input_vec(); let mut ans = 0; for i in (0..n-1).rev() { while a[i] >= a[i+1] { if a[i]==0 { println!("-1"); return; } a[i]/=2; ans += 1; } } println!("{}", ans); }
C. Detective Task
泥棒されたので友達の証言から、泥棒の可能性がある人を数えてという問題。
1 は物があった、 0 は無かった、 ? は覚えていない。
泥棒以外は正しい事を言っているので、最後から2番目に 1 を言った人までは絶対に正しくて、最後に 1 を言った人は泥棒の可能性がある。同様に頭から2番目に 0 を言った人は絶対に正しくて、最初に 0 を言った人は泥棒の可能性がある。よって、最後に 1 と言った人から最初に 0 を言った人が泥棒の可能性がある。
fn main() { let t : usize = input(); for _ in 0..t { solve(); } } fn solve() { let mut s : Vec<_> = input::<String>().chars().collect(); let n = s.len(); if n == 1 || s[0] == '0' { println!("1"); return; } let (index, _) = s.iter().enumerate().filter(|(_, &c)| c == '1').last().unwrap(); let mut ans = 0; for i in 1.max(index)..=n { ans += 1; if s[i] == '0' {break} } println!("{}", ans); }
D. Vertical Paths
問題読解に時間がかかった…。 木が与えられるので、1本のパスに分解してねって問題。
それがパスのスタート地点かどうかを持ちながら DFS する。
1個目の子供は親に繋がっていて、他の子供はパスのスタート地点にしたら良い。
葉まで来たら ans に入れておく。
fn main() { let t : usize = input(); for _ in 0..t { solve(); } } fn solve() { let n : usize = input(); let p : Vec<usize> = input_vec(); let mut g = vec![vec![]; n]; let mut root = 0; for i in 0..n { let p = p[i] - 1; if i == p { root = i; continue } g[p].push(i); } let mut ans = vec![]; dfs(root, &g, true, &mut vec![], &mut ans); println!("{}\n{}", ans.len(), ans.join("\n")); } fn dfs(v:usize, g:&Vec<Vec<usize>>, p:bool, path:&mut Vec<usize>, ans:&mut Vec<String>) { let mut leaf = true; path.push(v); for (i, &u) in g[v].iter().enumerate() { leaf = false; if i > 0 { dfs(u, g, true, path, ans); } else { dfs(u, g, false, path, ans); } } if leaf { ans.push(format!("{}\n{}",path.len(),path.iter().map(|&p| (p+1).to_string()).collect::<Vec<_>>().join(" "))); path.clear(); } }
E. Replace With the Previous, Minimize
$a$ に含まれるあるアルファベットを全て1つ前のアルファベットに置き換える操作が $k$ 回できるので、辞書順最小の文字列を求めて下さいという問題。
辞書順最小は、前から 'a' に近づけて行けば良い。
操作は 1 つずつアルファベットが1つ戻っていくので、 そこ以前のアルファベットは全て同じだけ戻すことができる。 例えば 'f' が 'a' にできるなら、その間の "bcde" は全て 'a' にすることができる。
よって、以下のような変換のテーブルを持って、更新しながら貪欲に前から変換していけば良い。
例に挙げたような 'f' が 'a' にできるときは、こんな感じで更新しておく。
fn main() { let t : usize = input(); for _ in 0..t { solve(); } } fn solve() { let (n,mut k) : (usize, usize) = input_t(); let mut s : Vec<_> = input::<String>().chars().collect(); let mut t : Vec<_> = "abcdefghijklmnopqrstuvwxyz".chars().collect(); for i in 0..n { let mut index = (s[i] as u8 - b'a') as usize; let c = index.min(k); for j in index-c..=index { if t[j] != t[index-c] { k-=1; } t[j] = t[index-c]; } s[i] = t[index]; } println!("{}", s.iter().collect::<String>()); }
F. Vlad and Unfinished Business
木が与えられて、 $x$ から $y$ に行きたいが、途中で $a_1, a_2, \cdots, a_k$ のノードに寄る必要ある。その最短経路の距離を求めて下さいという問題。
必要な頂点の最小全域木みたいなものを考える。このとき、 $x$ と $y$ の間にない頂点は、行って帰ってくる必要がある。よって2倍かかる。だいたい 最小全域木の辺の数 * 2 であることが分かる。後は、 $x$ から $y$ の間は往復する必要がないのでその分を引いてあげる。
035 - Preserve Connectivity（★7） に思いを馳せると解ける。
fn main() { let t : usize = input(); for _ in 0..t { let _ = input::<String>(); solve() } } fn solve() { let (n,k) : (usize, usize) = input_t(); let (mut x, mut y) : (usize, usize) = input_t(); let mut v : Vec<usize> = input_vec(); for v in v.iter_mut() { *v-=1; } v.sort(); v.dedup(); x-=1; y-=1; let mut g = vec![vec![]; n]; for _ in 0..n-1 { let (mut a,mut b) : (usize, usize) = input_t(); a-=1; b-=1; g[a].push(b); g[b].push(a); } let mut lca = LowestCommonAncestor::from(&g); lca.init(x); v.push(x); v.push(y); v.sort_by_key(|&v| lca.time[v][0]); v.push(v[0]); let ans = v.windows(2).map(|v| lca.distance(v[0],v[1])).sum::<usize>() - lca.distance(x,y); println!("{}", ans); }
本当は、 v.into_iter().cycle().take(n+1) とかしたいんだけど、 tuple_windows() が使えないので、諦めた…
G. Sorting Pancakes
本番では解けてない。
合計が $m \leq 250$ と小さいので DP する。 $i$ 番目を決めるとき 直前が $k$ だったら $k$ 以下にしかできない。で、 この桁を $b$ とするときの操作回数は、$a$ のここまでの和と今まで使ったやつの差の絶対値を求めて行けば良いので、そんな感じで計算する。
$k$ は以下ならなんでも良いので、今までの min を取ってくると良くて、累積min すると良い感じになる。
fn main() { let (n, m) : (usize, usize) = input_t(); let a : Vec<i64> = input_vec(); const INF : i64 = std::i64::MAX / 10; let mut csum = vec![0; n+1]; for i in 0..n { csum[i+1] += csum[i] + a[i]; } let mut dp = vec![vec![INF; m+1]; m+1]; dp[0][m] = 0; for &s in csum.iter().skip(1) { let mut next = vec![vec![INF; m+1]; m+1]; for j in 0..=m { let mut min = INF; for k in (0..=m).rev() { chmin(&mut min, dp[j][k]); if j + k > m { continue } chmin(&mut next[j+k][k], min + (s - (j+k) as i64).abs()); } } dp = next; } let ans = dp[m].iter().min().unwrap(); println!("{}", ans); }
まとめ
コドフォレート 1329 → 1506（+177） これは成功回。 F 諦めなくて良かった～
