Codeforces Round #748 (Div. 3)
Codeforces Round #748 (Div. 3) のバーチャル参加をしたのでまとめ。
A,B,C,D1,E の 5完。7ペナ。ペナが多くて良くないね。
A. Elections
他の候補者に勝つために、最低後何票必要ですか？という問題。 良い方針が思いつかないので、最大値が何個あるかで場合分けをする。
よく考えると、 a_ans = max(0, max(b, c) + 1 - a) とかで良い。
fn solve() { let a : Vec<usize> = input_vec(); let max = *a.iter().max().unwrap(); let mut cnt = a.iter().filter(|&&a| a==max).count(); if cnt == 3 { println!("{} {} {}", 1, 1, 1); } else if cnt == 2 { println!("{} {} {}", if a[0] == max {1} else {max-a[0]+1}, if a[1] == max {1} else {max-a[1]+1}, if a[2] == max {1} else {max-a[2]+1}, ) } else { println!("{} {} {}", if a[0] == max {0} else {max-a[0]+1}, if a[1] == max {0} else {max-a[1]+1}, if a[2] == max {0} else {max-a[2]+1}, ) } }
B. Make it Divisible by 25
正整数 $n$ が与えられるので、何文字か削除して 25 の倍数にして下さいという問題。
雑にどこか1文字を消すプログラムを書くも TLE。よく考えると、下位3桁くらい（本当は2桁で良いバチャ中は雑に考えてた）が 25 で割り切れたら良いので、削除するのは下位3桁のどれかだけで良い。念のため同じ値を入れないように BTree な Set に探索済みの値を入れておいた（こっちの方が効いたかも？）。
fn solve() { let n : usize = input(); let mut q = VecDeque::new(); q.push_back((n, 0)); let mut s = BTreeSet::new(); while let Some((n, i)) = q.pop_front() { if n % 25 == 0 { println!("{}", i); return; } if s.insert(n/10) { q.push_back((n/10, i+1)); } if s.insert(n/100*10 + n%10) { q.push_back((n/100*10 + n%10, i+1)); } if s.insert(n/1000*100 + n%100) { q.push_back((n/1000*100 + n%100, i+1)); } } }
C. Save More Mice
一直線上に猫1匹と、ネズミが $n$匹 居て $k$ に穴がある。ネズミを1匹だけ1進める・猫を1進めるを交互に繰り返して、ネズミを何匹穴に到達させられるかという問題（猫に追いつかれるとダメ）。
ネズミが先に移動するので、ネズミは猫が穴に到達するまでの $k$回の移動ができる。 よって穴に近い方からゴールさせていき $k$ 回以下となるギリギリを求めたら良い。
fn solve() { let (k, n) : (usize, usize) = input_t(); let mut x : Vec<usize> = input_vec(); x.sort(); x.reverse(); let mut ans = 0; let mut sum = 0; for x in x { if sum + (k - x) >= k { break } sum += (k - x); ans += 1; } println!("{}", ans); }
D1. All are Same
数列 $a$ が与えられる。ある $i$ を選んで $a_i = a_i - k$ をするのを繰り返して、 $a$ を全部同じ値にするとき、それを達成できる $k$ の最大値を求めて下さい。という問題。
操作回数 0回で済む場合は、 $k$ はどんな値でも良いので操作回数0を考えると最初から全部同じ場合である。全部同じ場合は -1 とする。それ以外のときを考える。
適当な $i,j$ を選んで、それらを1回で揃えるには $ \mid a _ i - a _ j \mid $ かかる。それを共通で良い感じにしたいので、 GCD を取れば良い。$n$ が小さいので、適当で良い。
fn solve() { let n : usize = input(); let a : Vec<i64> = input_vec(); if a.iter().filter(|&&b| a[0] == b).count() == n { println!("-1"); return; } let mut g = 0; for i in 0..n { for j in i+1..n { g = gcd(g, (a[i]-a[j]).abs()); }} println!("{}", g); }
D2. Half of Same
バチャ中は解けなかった。 揃えるやつを決めて、その差の絶対値で GCD を map で管理しながらやれば良いと思ったんだけどダメ…。これなんでダメなんだ…？（いくつかあるけどこんな感じ → WA （これ GCD が 0 になるやつの扱いがダメそうだな。））。
$n$ がそんなに多くないので、差の絶対値の約数を列挙してちゃんと数えて良い。
$a_i$ を決め打ちして、$a_i$ と同じやつは別で数えておく。後は、差を取って約数列挙カウントを愚直によやると良い。これも D1 と同様に、同じやつが $n/2$ 以上あったら -1 。
fn solve() { let n : usize = input(); let mut a : Vec<i64> = input_vec(); let mut cnt = BTreeMap::new(); for &a in a.iter() { *cnt.entry(a).or_insert(0) += 1; } let max = cnt.into_iter().map(|(_,c)| c).max().unwrap(); if max>=n/2 { println!("-1"); return; } let mut ans = 0; for &ai in a.iter() { let mut cnt = BTreeMap::new(); let mut c = 0; for &aj in a.iter() { if ai == aj { c+=1; continue } for d in f((ai - aj).abs()) { *cnt.entry(d).or_insert(0) += 1; } } for (g, j) in cnt { if j+c>=n/2 { ans=ans.max(g); }} } println!("{}", ans); } fn f(x: i64) -> Vec<i64> { let mut sqrt = 0.max((x as f64).sqrt() as i64 - 10); while (sqrt+1)*(sqrt+1) <= x { sqrt += 1; } let mut res = vec![]; for i in 1..=sqrt { if x % i != 0 { continue } res.push(i); if x/i != i { res.push(x/i); } } res }
【追記】
差の絶対値で GCD を map で個数を管理するやつダメだって言ったけどできました。 管理の仕方が悪くて、その GCD になる最大値を管理するべきでした…
fn solve() { let n : usize = input(); let a : Vec<i64> = input_vec(); let mut cnt = BTreeMap::new(); for &a in a.iter() { *cnt.entry(a).or_insert(0) += 1; } let max = cnt.into_iter().map(|(_,c)| c).max().unwrap(); if max >= n/2 { println!("-1"); return; } let mut ans = 0; for i in 0..n { let mut cnt = BTreeMap::new(); for j in 0..n { for (g, c) in cnt.clone() { let g = gcd(g, (a[i] - a[j]).abs()); let t = cnt.entry(g).or_insert(0); *t = (c+1).max(*t); } cnt.entry((a[i]-a[j]).abs()).or_insert(1); } for (g, c) in cnt { if c >= n/2 {ans=ans.max(g); }} } println!("{}", ans); }
E. Gardener and Tree
木が与えられるので、葉から消していくのを $k$ 回繰り返して残る頂点数を答えて下さいという問題。特に根が有るわけじゃないので、端っこから消えていく。
多始点の BFS みたいなことをしながら端っこを取り除くみたいなことを繰り返すと良い。何回目で取り除かれるかっていうのを入れていくと良いが、次数が $1$ になる（親だけ残る）タイミングだけ取り除かれるカウンターを更新する必要がある（4 WA）。
fn solve() { let (n, k) : (usize, usize) = input_t(); if n == 1 { println!("0"); return; } let mut g = vec![vec![]; n]; let mut cnt = vec![0; 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); cnt[a]+=1; cnt[b]+=1; } let mut d = vec![0; n]; let mut q = VecDeque::new(); let mut used = vec![false; n]; for i in 0..n { if cnt[i] == 1 { q.push_back(i); d[i]=1; used[i]=true;}} while let Some(v) = q.pop_front() { used[v] = true; for &u in g[v].iter() { if used[u] { continue } cnt[u] -= 1; if cnt[u] == 1 { q.push_back(u); d[u]=d[v]+1;} } } println!("{}", d.iter().filter(|&&d| d>k).count()); }
F. Red-Black Number
読んだけど解けてない
【2022/05/28 追記】
ネタバレ？を見つつ実装。
$N, A, B$ が小さいので、良い感じに DP をして、復元をする。
dp[i][j][k][l] $i$ 桁使って、$A$ で割った余りが $j$ 、$B$ で割った余りが $k$ 、赤（もしくは黒）が $l$ 桁 をして、復元する。そんなに遅くないようにかいたつもりなんだけど TL ギリギリだった。 $t$ がそんなに大きくないのでまとめて出力するようにしてもほぼ変わらず…。これ遅めの言語だと辛そう？ usize をたくさん持っているのが良くないのかね？
fn solve() { let (n, a, b) : (usize, usize, usize) = input_t3(); let x : Vec<_> = input::<String>().chars().collect(); let x = x.into_iter().map(|c| (c as u8 - b'0') as usize).collect::<Vec<_>>(); let mut dp = vec![vec![vec![vec![false; n+1]; b]; a]; n+1]; let mut pref = vec![vec![vec![vec![None; n+1]; b]; a]; n+1]; dp[0][0][0][0] = true; // dp for (i, c) in x.into_iter().enumerate() { for j in 0..a { for k in 0..b { for l in 0..n { if !dp[i][j][k][l] { continue } let d = dp[i][j][k][l]; if l+1 <= n { dp[i+1][(j*10 + c) % a][k][l+1] |= d; pref[i+1][(j*10 + c) % a][k][l+1] = Some((i,j,k,l)); } dp[i+1][j][(k*10 + c) % b][l] |= d; pref[i+1][j][(k*10 + c) % b][l] = Some((i,j,k,l)); }}} } // 赤と黒の桁の差が少なくなるところを探す let mut min = std::usize::MAX; let mut index = None; for i in 1..n { if !dp[n][0][0][i] { continue } let d = i.max(n-i) - i.min(n-i); if min >= d { min = d; index = Some(i); } } if index.is_none() { println!("-1"); return; } // 復元 let mut ans = Vec::with_capacity(n); let mut now = (n, 0, 0, index.unwrap()); while let Some(next) = pref[now.0][now.1][now.2][now.3] { ans.push(if now.3 == next.3 {'B'} else {'R'}); now = next; } println!("{}", ans.iter().rev().collect::<String>()); }
G. Changing Brackets
読んでない
まとめ
Codeforces Anytime は冷え。うーん、 D2 は解けるべきだったかもしれない。
[バーチャル参加] zeronosu77108_さんのCodeforces Round #748 (Div. 3)での結果は662位でした！ パフォーマンス：1645相当 レーティング：1707→1691 (-16) #CodeforcesAnytime https://codeforces-anytime.sonoapp.page/users/0RUV6NRz0XY7Jco7nDg0fjn4z3h2?cert=17
