AtCoder Regular Contest 172 (ARC172) (AからCまで、およびE) 復習の提出

ARC172を解き直しました。
コンテスト時はAの1完でした。Bの考察ミスに60分気付かなかったのが痛すぎますし、Cに行かずにEを詰め切れなかったのも悔しいです。

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

自作ライブラリを使用し、ローカルで事前に明らかに未使用な部分を除いて展開する形で提出しています。展開前のソースコードを記述します。
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!(h:usize,w:usize,n:usize,mut a:[usize;n]);
    let mut sets=MultiSet::<(usize,usize)>::new();
    sets.insert_one((h,w));
    a.sort();
    a.reverse();
    for a in a {
        let l=1<<a;
        let mut hw=None;
        for (&(h,w),_) in &sets {
            if l<=h && l<=w {
                hw=Some((h,w));
                break;
            }
        }
        if let Some((h,w))=hw {
            sets.remove_one((h,w));
            if h>l {
                sets.insert_one((h-l,l));
            }
            if w>l {
                sets.insert_one((h,w-l));
            }
        } else {
            outputln!("No");
            return;
        }
    }
    outputln!("Yes");
}

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!(n:usize,k:usize,l:usize);
    let mut ans=Mint::new(1);
    let mut cur=l;
    for _ in 0..n {
        ans*=cur;
        if cur>0 && cur+n-k>l {
            cur-=1;
        }
    }
    outputln!(ans);
}

C問題

atcoder.jp
atcoder.jp

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

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

    input!(n:usize,c:Chars);
    let mut sum=vec![0;n];
    for i in 1..n {
        sum[i]=sum[i-1]+(c[i]=='A') as usize;
    }
    let mut ans=1;
    for i in 0..n-1 {
        if (sum[i]+(c[0]=='A') as usize).cmp(&(i-sum[i]+(c[0]=='B') as usize))!=(sum[i+1]).cmp(&(i+1-sum[i+1])) {
            ans+=1;
        }
    }
    outputln!(ans);
}

E問題

atcoder.jp
atcoder.jp

use ac_library::ModInt;
#[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);
    for _ in 0..q {
        input!(x:u32);
        let mut n=0;
        ModInt::set_modulus(E[2] as u32);
        for i in 1..E[2] {
            if ModInt::new(i).pow(i as u64)==ModInt::new(x) {
                n=i;
                break;
            }
        }
        if n==0 {
            outputln!(-1);
            continue;
        }
        let mut exists=true;
        for p in 3..=9 {
            let mut ok=false;
            ModInt::set_modulus(E[p] as u32);
            for k in 0..10 {
                let i=k*E[p-1]+n;
                if ModInt::new(i).pow(i as u64)==ModInt::new(x) {
                    n=i;
                    ok=true;
                    break;
                }
            }
            if !ok {
                outputln!(-1);
                exists=false;
                break;
            }
        }
        if exists {
            outputln!(n);
        }
    }
}