ABC417

A - A Substring

こういうのはPythonが楽。末尾の指定を-でやるとうまく行かないらしいですが、僕はよく知らないので引っかからずに済みました。提出

n, a, b = map(int, input().split())
s = input()
print(s[a:n-b])

B - Search and Delete

雑にmultisetで追加しておいて、あとから削除していけばよいです。Rustにはmultisetはないですが、それらしく使えるmapのラッパーを用意しているので問題なし。提出

use std::iter::repeat;

use library::{data_structure::multiset::MultiSet, utils::input::Input};

fn solve(ip: &mut Input) {
    let (n, m) = ip.pair::<usize,usize>();
    let a = ip.vector::<u64>(n);
    let b = ip.vector::<u64>(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::<Vec<_>>().join(" "))
        .collect::<Vec<_>>()
        .join(" ");
    println!("{}", ans);
        
}

C - Distance Indicators

条件式を整理すると、$A_i + i = j - A_j$となるので、$A_i + i$の数を前計算しておけば、$j-A_j$に対応するものの個数が$O(1)$で取れるようになります。前計算、答えの計算がそれぞれ$O(N)$でできるので、全体で$O(N)$時間で解くことができます。提出

use std::collections::BTreeMap;

use library::utils::input::Input;

fn solve(ip: &mut Input) {
    let n = ip.next::<usize>();
    let a = ip.vector::<usize>(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::<u64>();
    println!("{}", ans);
}

D - Takahashi's Expectation (upsolve)

これ難しすぎませんか？水diffなの驚きです。

$\text{dp}_{i,j} :=i$番目の要素からテンション$j$で始めたときの、最終的なテンションの値、というdpを考えると、問題設定から後ろから順にテーブルが埋まっていきます。与えられた制約全てに対してこのテーブルを埋めるのは時間が足りませんが、$A_i, P_i$が500以下であることから、$j$として$1000$¹までを考えてあげれば十分です。

よって、このdpを前計算しておき、初期時点でテンションが1000を超えている場合はそれを下回るまで減少させてからテーブルを参照することによってこの問題を解けます。ただこれも一筋縄とは行かず、累積和+二分探索を用いて「始めて1000を下回るインデックス」を調べる必要があります。結局、全体で$O(N (\max A_i + \max P_i) + \log N)$時間など？計算量解析はあまり自信がありませんが、とにかくACを得ることができます。提出

use library::{cumulative_sum::CumulativeSum, utils::input::Input};

fn solve(ip: &mut Input) {
    
    let n = ip.next::<usize>();
    let v = (0..n)
        .map(|_| ip.triple::<u64,u64,u64>())
        .collect::<Vec<_>>();
    
    let b = v.iter()
        .map(|&(_, _, b)| b) 
        .collect::<Vec<_>>();

    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::<Vec<u64>>();

    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::<usize>();
    for _ in 0..q {
        let x = ip.next::<u64>();
        
        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]);
        }
    }
}

E - A Path in A Dictionary

「ある頂点に到達したときに、その後ゴールの頂点に到達できるか？」を判定すればよいです。できるだけ辞書順が小さい方に移動していって、採用できるならば採用する貪欲でOKです。ただし、一度確認してゴールに行けないことがわかった頂点は2度目以降は確認しないなどの枝狩りが必要となることに注意。提出

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::<usize,usize>();
    let (x, y) = ip.pair::<usize,usize>();
    let x = x-1;
    let y = y-1;
    
    let e = (0..m).map(|_| {
        let (x, y) = ip.pair::<usize, usize>();
        (x-1, y-1)
    }).collect::<Vec<_>>();
    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::<Vec<_>>().join(" "));
}

F - Random Gathering (upsolve)

え、簡単すぎないですか？これ。区間変更区間和取得の遅延セグ木を持って、その区間の和/区間長で全体を変更していくだけです。提出

use ac_library::{LazySegtree, MapMonoid, Monoid};
use ac_library::ModInt998244353 as Mint;
use library::{utils::input::Input};

#[derive(Clone, Debug)]
struct C {
    val: Option<Mint>,
    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<Mint>;

    fn identity_map() -> Self::F {
        return None;
    }

    fn mapping(f: &Self::F, x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::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::<usize, usize>();
    let a = ip.vector::<u64>(n);
    
    let mut seg :LazySegtree<B> = 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::<usize, usize>();
        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::<Vec<_>>().join(" ");
    println!("{}", ans);
}