AtCoder Beginner Contest 329 (AからFまで) 復習

Rustで競プロするのに慣れたりライブラリを整備したりするのも兼ねて、ABC329を解き直します。
コンテスト時はA～Fの6完でした。

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

A問題

atcoder.jp
ライブラリを整備しすぎて、実質2行で解けました。
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!(s:Chars);
    s.outputln();
}

B問題

atcoder.jp
コンテスト中は楽な実装を思いつきませんでしたが、dedup関数でよいですね。
一応、sortしてそのままdedupする関数と末尾からのインデックスでアクセスする関数をライブラリに追加しました。
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,mut a:[usize;n]);
    a.sort_and_dedup();
    outputln!(a.get_from_last(2));
}

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!(_:usize,s:Chars);
    let mut maxs=[0;26];
    for (c,l) in s.rle() {
        maxs[c.from_lowercase()].chmax(l);
    }
    outputln!(maxs.sum());
}

D問題

atcoder.jp
コンテスト中は絶対比べる回数を少なくできるよなと思いつつ、BTreeSetで殴りました。
実際、当選者の候補は前回の当選者か今回票が入った人に絞られるので、それらを比較するだけでよいですね。
(降順, 昇順)の比較の実装、悩みますね。
（BTreeSet等の場合はやはりReverseを使うのがよさそうですかね。）
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,m:usize,a:[usize;m]);
    let mut cnts=vec![0;n+1];
    let mut ans=0;
    for a in a {
        cnts[a]+=1;
        if (cnts[ans],a)<(cnts[a],ans) {
            ans=a;
        }
        outputln!(ans);
    }
}

E問題

atcoder.jp
コンテスト中は、逆順で考えたときに貪欲でよい確証と計算量を減らすすべが思い浮かばず、DPに逃げました。
数ある解法の中ではこれが最も好きですね。
これで実装してみました。


イテレータどうしの結合はchain関数らしいですね。
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,m:usize,s:Chars,t:Chars);
    let mut x=s;
    for i in (0..=n-m).chain((0..=n-m).rev()) {
        let mut matched=true;
        for j in 0..m {
            if x[i+j]!='#' && x[i+j]!=t[j] {
                matched=false;
            }
        }
        if matched {
            for j in 0..m {
                x[i+j]='#';
            }
        }
    }
    x.dedup();
    output_yes_or_no(x==vec!['#']);
}

F問題

atcoder.jp
マージテクが何かを知っていればやるだけの問題。
マージテクは各要素の属する成分のサイズに注目した計算量解析がエレガントすぎます。
この記事を参考にマージテクをライブラリ化しておきました。
scrapbox.io
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,q:usize,c:[Usize1;n],ab:[(Usize1,Usize1);q]);
    let mut boxes=vec_range(0, n, |i| BTreeSet::from([c[i]]));
    for (a,b) in ab {
        boxes.merge(a,b);
        outputln!(boxes[b].len());
    }
}

G問題は面倒そうだったので今はやらないでおきます。
ABC275-D等でmemoiseクレートの使い方は覚えたので許して…（AtCoderに入っていないmemoizeクレートとAtCoderに入っているmemoiseクレートがあるのややこしい…）