## A - A Substring こういうのはPythonが楽。末尾の指定を-でやるとうまく行かないらしいですが、僕はよく知らないので引っかからずに済みました。[提出](https://atcoder.jp/contests/abc417/submissions/68144393) ```python n, a, b = map(int, input().split()) s = input() print(s[a:n-b]) ``` ## B - Search and Delete 雑に`multiset`で追加しておいて、あとから削除していけばよいです。Rustには`multiset`はないですが、それらしく使える`map`のラッパーを用意しているので問題なし。[提出](https://atcoder.jp/contests/abc417/submissions/68143583) ```rust use std::iter::repeat; use library::{data_structure::multiset::MultiSet, utils::input::Input}; fn solve(ip: &mut Input) { let (n, m) = ip.pair::(); let a = ip.vector::(n); let b = ip.vector::(m); let mut mset = MultiSet::new(); for ai in a { mset.add(ai, 1); } for bi in b { mset.remove(bi, 1); } let ans = mset.iter() .map(|(k, v)| repeat(*k).take(*v).map(|x| x.to_string()).collect::>().join(" ")) .collect::>() .join(" "); println!("{}", ans); } ``` ## C - Distance Indicators 条件式を整理すると、$A_i + i = j - A_j$となるので、$A_i + i$の数を前計算しておけば、$j-A_j$に対応するものの個数が$O(1)$で取れるようになります。前計算、答えの計算がそれぞれ$O(N)$でできるので、全体で$O(N)$時間で解くことができます。[提出](https://atcoder.jp/contests/abc417/tasks/abc417_c) ```rust use std::collections::BTreeMap; use library::utils::input::Input; fn solve(ip: &mut Input) { let n = ip.next::(); let a = ip.vector::(n); let mut map = BTreeMap::new(); for (i, &ai) in a.iter().enumerate() { *map.entry(i + 1 + ai).or_insert(0) += 1u64; } let ans = a.iter() .enumerate() .map(|(i, ai)| if *ai>i+1 { 0 } else if let Some(c) = map.get(&(i+1-ai)) { *c } else { 0 } ) .sum::(); println!("{}", ans); } ``` ## D - Takahashi's Expectation (upsolve) これ難しすぎませんか？水diffなの驚きです。 $\text{dp}_{i,j} :=i$番目の要素からテンション$j$で始めたときの、最終的なテンションの値、というdpを考えると、問題設定から後ろから順にテーブルが埋まっていきます。与えられた制約全てに対してこのテーブルを埋めるのは時間が足りませんが、$A_i, P_i$が500以下であることから、$j$として$1000$[^1]までを考えてあげれば十分です。よって、このdpを前計算しておき、初期時点でテンションが1000を超えている場合はそれを下回るまで減少させてからテーブルを参照することによってこの問題を解けます。ただこれも一筋縄とは行かず、累積和+二分探索を用いて「始めて1000を下回るインデックス」を調べる必要があります。結局、全体で$O(N (\max A_i + \max P_i) + \log N)$時間など？計算量解析はあまり自信がありませんが、とにかくACを得ることができます。[提出](https://atcoder.jp/contests/abc417/submissions/68222740) ```rust use library::{cumulative_sum::CumulativeSum, utils::input::Input}; fn solve(ip: &mut Input) { let n = ip.next::(); let v = (0..n) .map(|_| ip.triple::()) .collect::>(); let b = v.iter() .map(|&(_, _, b)| b) .collect::>(); let csum = CumulativeSum::new(&b); static M: u64 = 1000; // dp[i][j] := i番目にテンションがjで始めたときの最終的な値 let mut dp = vec![vec![0; M as usize+1]; n+1]; dp[n] = (0..=M).collect::>(); for i in (0..n).rev() { for j in 0..=M { if j <= v[i].0 { dp[i][j as usize] = dp[i+1][(j + v[i].1) as usize]; } else { let k = if j >= v[i].2 { j - v[i].2 } else { 0 }; dp[i][j as usize] = dp[i+1][k as usize]; } } } let q = ip.next::(); for _ in 0..q { let x = ip.next::(); let i = if x <= 500 { 0 } else { let targ = x-500; csum.binary_search(targ).unwrap_or_else(|x| x) }; if i == n+1 { println!("{}", x - csum.get(..)); } else { let s = x - csum.get(..i); println!("{}", dp[i][s as usize]); } } } ``` [^1]: $A_i + P_i$としてありうる最大値 ## E - A Path in A Dictionary 「ある頂点に到達したときに、その後ゴールの頂点に到達できるか？」を判定すればよいです。できるだけ辞書順が小さい方に移動していって、採用できるならば採用する貪欲でOKです。ただし、一度確認してゴールに行けないことがわかった頂点は2度目以降は確認しないなどの枝狩りが必要となることに注意。[提出](https://atcoder.jp/contests/abc417/submissions/68134458) ```rust use library::{data_structure::unionfind::UnionFind, utils::input::Input}; fn ch(n: usize, s: usize, t: usize, used: &[bool], edges: &Vec<(usize,usize)>) -> bool { let mut uf = UnionFind::new(n, |_x, _y| 0); for &(u,v) in edges.iter() { if !used[u] && !used[v] { uf.merge(u, v); } } uf.same(s, t) } fn solve(ip: &mut Input) { let (n, m) = ip.pair::(); let (x, y) = ip.pair::(); let x = x-1; let y = y-1; let e = (0..m).map(|_| { let (x, y) = ip.pair::(); (x-1, y-1) }).collect::>(); let mut g = e.iter().fold(vec![vec![]; n], |mut g, &(u,v)| { g[u].push(v); g[v].push(u); g }); let mut used = vec![false; n]; let mut checked = vec![false; n]; used[x] = true; let mut ans = vec![x]; let mut cur = x; for i in 0..n { g[i].sort(); } while cur != y { for &ni in g[cur].iter() { if checked[ni] { continue; } if ch(n, ni, y, &used, &e) { cur = ni; ans.push(ni); used[ni] = true; break; } else { checked[ni] = true; } } } println!("{}", ans.iter().map(|x| (x+1).to_string()).collect::>().join(" ")); } ``` ## F - Random Gathering (upsolve) え、簡単すぎないですか？これ。区間変更区間和取得の遅延セグ木を持って、その区間の和/区間長で全体を変更していくだけです。[提出](https://atcoder.jp/contests/abc417/submissions/68223146) ```rust use ac_library::{LazySegtree, MapMonoid, Monoid}; use ac_library::ModInt998244353 as Mint; use library::{utils::input::Input}; #[derive(Clone, Debug)] struct C { val: Option, size: usize, } struct A; impl Monoid for A { type S = C; fn identity() -> Self::S { C { val: None, size: 0} } fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S { let l = if let Some(a) = a.val { a } else { Mint::new(0)}; let r = if let Some(a) = b.val { a } else { Mint::new(0)}; let val = if a.val.is_none() && b.val.is_none() { None } else { Some(l+r) }; C { val, size: a.size + b.size } } } struct B; impl MapMonoid for B { type M = A; type F = Option; fn identity_map() -> Self::F { return None; } fn mapping(f: &Self::F, x: &::S) -> ::S { let mut res = x.clone(); if let Some(a) = f { res.val = Some(*a * res.size as u64); } res } fn composition(f: &Self::F, g: &Self::F) -> Self::F { if let Some(_) = f { *f } else { *g } } } fn solve(ip: &mut Input) { let (n, m) = ip.pair::(); let a = ip.vector::(n); let mut seg :LazySegtree = LazySegtree::new(n); for i in 0..n { seg.set(i, C { val: Some(Mint::new(a[i])), size: 1 }); } for _ in 0..m { let (l, r) = ip.pair::(); let l = l-1; let r = r; let s = seg.prod(l..r); seg.apply_range(l..r, Some(s.val.unwrap() / (r-l) as u64)); } let ans = (0..n).map(|x| seg.get(x).val.unwrap().val().to_string()).collect::>().join(" "); println!("{}", ans); } ```

ABC417