AtCoder Regular Contest 171 (ARC171) (AからDまで) 復習の提出

ARC171を解き直しました。
コンテスト時はA～Bの2完でした。頑張って2完しましたが周りと比べると遅かったようです…

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

自作ライブラリを使用し、ローカルで事前に明らかに未使用な部分を除いて展開する形で提出しています。展開前のソースコードを記述します。
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!(t:usize);
    for _ in 0..t {
        input!(n:usize,a:usize,b:usize);
        output_yes_or_no(a<=n && b<=min(n-a,(n+1)/2)*(n-a));
    }
}

B問題

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]);
    let mut ans=Mint::new(1);
    let mut cnt=0;
    let mut set=BTreeSet::<usize>::new();
    for i in 0..n {
        if a[i]<i {
            ans*=0;
            break;
        } else if a[i]==i {
            if !set.contains(&a[i]) {
                cnt+=1;
                set.insert(a[i]);
            }
            ans*=cnt;
            cnt-=1;
        } else if !set.contains(&a[i]) {
            cnt+=1;
            set.insert(a[i]);
        }
    }
    if cnt>0 {
        ans*=0;
    }
    outputln!(ans);
}

C問題

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,uv:[(Usize1,Usize1);n-1]);
    let g=VecGraph::construct_graph(n, n-1, &uv);
    let mut seen=vec![false;n];
    seen[0]=true;
    let mut deg=vec![0;n];
    let mut dp=vec![vec![Mint::new(0);n];n];
    dfs(0, n, &g, &mut seen, &mut deg, &mut dp);
    outputln!(dp[0].sum());
}

fn dfs(v: usize, n: usize, g: &VecGraph, seen: &mut Vec<bool>, deg: &mut Vec<usize>, dp: &mut Vec<Vec<Mint>>) {
    dp[v][0]+=1;
    for &(u,_) in &g.get()[v] {
        if seen[u] {
            continue;
        }
        seen[u]=true;
        deg[v]+=1;
        dfs(u, n, g, seen, deg, dp);
        let mut new=vec![Mint::new(0);n];
        for i in 0..deg[v] {
            for j in 0..=deg[u] {
                new[i+1]+=dp[v][i]*(i+1)*dp[u][j]*(j+1);
                new[i]+=dp[v][i]*dp[u][j];
            }
        }
        dp[v]=new;
    }
}

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!(p:usize,_:usize,n:usize,m:usize,lr:[(Usize1,usize);m]);
    let g=VecGraph::construct_graph(n+1, m, &lr);
    output_yes_or_no(g.chromatic_number()<=p);
}