AtCoder Beginner Contest 340 (ABC340) 復習の提出

ABC340を解き直しました。
コンテスト時はA～Fの6完でした。典型祭りでめちゃくちゃ温まりました。

復習したときのメモを動画にして提出したもののみ載せます。

自作ライブラリを使用し、ローカルで事前に明らかに未使用な部分を除いて展開する形で提出しています。展開前のソースコードを記述します。
AtCoderで使えるクレートに含まれない関数などを使っている可能性があること、破壊的変更をこの記事の投稿後にしている可能性があることにご注意ください。
github.com

A問題

atcoder.jp
atcoder.jp

#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;

fn main() {
    /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更）
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
            // proconio::input_interactive!($($tt)*);
        };
    }

    input!(a:usize,b:usize,d:usize);
    (a..=b).step_by(d).collect::<Vec<_>>().outputln();
}

B問題

atcoder.jp
atcoder.jp

#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;

fn main() {
    /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更）
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
            // proconio::input_interactive!($($tt)*);
        };
    }

    input!(q:usize);
    let mut vec=Vec::<usize>::new();
    for _ in 0..q {
        input!(q:usize);
        if q==1 {
            input!(x:usize);
            vec.push(x);
        } else {
            input!(k:usize);
            outputln!(vec.get_from_last(k));
        }
    }
}

C問題

atcoder.jp
atcoder.jp

#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;
use memoise::memoise_map;

fn main() {
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
        };
    }

    input!(n:usize);
    outputln!(f(n));
}

#[memoise_map(n)]
fn f(n:usize) -> usize {
    if n==1 {
        0
    } else {
        f(n/2)+f((n+1)/2)+n
    }
}

D問題

atcoder.jp
atcoder.jp

#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;
use proconio::marker::Usize1;

fn main() {
    /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更）
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
            // proconio::input_interactive!($($tt)*);
        };
    }

    input!(n:usize,abx:[(usize,usize,Usize1);n-1]);
    let mut vuw=Vec::new();
    for i in 0..n-1 {
        vuw.push((i,i+1,abx[i].0));
        vuw.push((i,abx[i].2,abx[i].1));
    }
    let g=VecGraph::construct_weighted_directed_graph(n, 2*n-2, &vuw);
    outputln!(g.dist_of_shortest_paths(0, true)[n-1]);
}

E問題

atcoder.jp
atcoder.jp

use ac_library::LazySegtree;
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;

fn main() {
    /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更）
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
            // proconio::input_interactive!($($tt)*);
        };
    }

    input!(n:usize,m:usize,a:[usize;n],b:[usize;m]);
    let mut a=LazySegtree::<SegmentAffineTransform<DummyOperation<usize>>>::from(a);
    for i in 0..m {
        let cur_box=b[i];
        let mut balls=a.get(cur_box);
        a.set(cur_box, 0);
        let all=balls/n;
        a.apply_range(0..n, (1,all));
        balls-=all*n;
        if cur_box+balls<n {
            a.apply_range(cur_box+1..=cur_box+balls, (1,1));
        } else {
            a.apply_range(cur_box+1..n, (1,1));
            a.apply_range(0..=(cur_box+balls)%n, (1,1));
        }
    }
    (0..n).into_iter().map(|i| a.get(i)).collect::<Vec<_>>().outputln();
}

F問題

atcoder.jp
atcoder.jp

#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;

fn main() {
    /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更）
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
            // proconio::input_interactive!($($tt)*);
        };
    }

    input!(x:isize,y:isize);
    let mut a=0;
    let mut b=0;
    let g=extended_euclidean_algorithm(y, -x, &mut a, &mut b);
    if g.abs()==2 {
        outputln!(a,b);
    } else if g.abs()==1 {
        outputln!(2*a,2*b);
    } else {
        outputln!(-1);
    }
}

G問題

atcoder.jp
atcoder.jp

use std::collections::BTreeSet;

#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;
use proconio::marker::Usize1;

fn main() {
    /// 標準入力のマクロ（インタラクティブ問題ならば中のマクロを変更）
    macro_rules! input {
        ($($tt:tt)*) => {
            proconio::input!($($tt)*);
            // proconio::input_interactive!($($tt)*);
        };
    }

    input!(n:usize,a:[Usize1;n],uv:[(Usize1,Usize1);n-1]);
    let mut g=VecGraph::construct_graph(n, n-1, &uv);
    let (_,par,depth,_,_,in_idx,out_idx)=g.easiest_hld_and_euler_tour();
    let lca=LCA::construct_lca_segtree(n, &par, &depth, &in_idx, &out_idx);
    let mut exists=BTreeSet::<usize>::new();
    let mut vertex_sets=vec![Vec::new();n];
    for i in 0..n {
        exists.insert(a[i]);
        vertex_sets[a[i]].push(i);
    }
    let mut ans=Mint::new(0);
    for &color in &exists {
        let (list,par)=g.auxiliary_tree(&mut vertex_sets[color], &in_idx, &out_idx, &lca);
        let len=list.len();
        let mut seen=vec![false;len];
        seen[0]=true;
        let mut dp=vec![(Mint::new(0),Mint::new(0));len];
        dfs(&mut ans, color, &a, 0, &vertex_sets[color], &list, &par, &mut seen, &mut dp);
    }
    outputln!(ans);
}

fn dfs(ans:&mut Mint,color:usize,a:&Vec<usize>,v:usize,vertex_set:&Vec<usize>,list:&Vec<Vec<usize>>,par:&Vec<usize>,seen:&mut Vec<bool>,dp:&mut Vec<(Mint,Mint)>) {
    for &u in &list[v] {
        if !seen[u] {
            seen[u]=true;
            dfs(ans, color, a, u, vertex_set, list, par, seen, dp);
            let tmp=dp[v].1*(dp[u].0+dp[u].1);
            dp[v].1=dp[v].1+dp[v].0*(dp[u].0+dp[u].1);
            dp[v].1=dp[v].1+tmp;
            dp[v].0=dp[v].0+(dp[u].0+dp[u].1);
        }
    }
    if a[vertex_set[v]]==color {
        dp[v].0+=1;
        *ans+=dp[v].0;
    }
    *ans+=dp[v].1;
}