AtCoder Beginner Contest 328 復習

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

自作ライブラリを使用し、ローカルで事前に展開する形で提出しています。展開前のコードを記述します。
破壊的変更をこの記事の投稿後にしている可能性があることにご注意ください。
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!(n:usize,x:usize,s:[usize;n]);
    let mut ans=0;
    for s in s {
        if s<=x {
            ans+=s;
        }
    }
    outputln!(ans);
}

B問題

atcoder.jp
コンテスト時は月で全探索しましたが、1～9までを全探索したほうが簡潔ですね。
あと、こういう場合分けを脳筋コピペ分岐せずにfor文で回すテクニックをコンテストの次の日に習得しました。（ほぼ最初に習得した言語がC言語だったので、for-each文を利用する発想には未だに弱い）
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 d:[usize;n]);
    d.move_right(1, 0);
    let mut ans=0;
    for i in 1..10 {
        for (a,b) in [(1,1),(1,11),(11,1),(11,11)] {
            if a*i<=n && b*i<=d[a*i] {
                ans+=1;
            }
        }
    }
    outputln!(ans);
}

追記
後でitertools::iproduct!マクロを知ったので使用してみました。こちらのほうが簡潔でミスしづらいですね。
atcoder.jp

use itertools::iproduct;
#[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 d:[usize;n]);
    d.move_right(1, 0);
    let mut ans=0;
    for i in 1..10 {
        for (a,b) in iproduct!([1,11],[1,11]) {
            if a*i<=n && b*i<=d[a*i] {
                ans+=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, Usize1};

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

    input!(n:usize,q:usize,s:Chars,lr:[(Usize1,Usize1);q]);
    let adj=vec_range(0, n-1, |i| (s[i]==s[i+1]) as usize);
    let adjsum=adj.construct_prefix_sum();
    for (l,r) in lr {
        outputln!(adjsum.calculate_partial_sum(l, r));
    }
}

D問題

atcoder.jp
今回のコンテストの反省点1。
この問題よりちょっと難しい類題のABC307-Dで沼ったのと全く同じような沼り方をしてしまいました。
1回謎重実装でWAを出してから、"ABC"を消すことにより"ABC"が新たに生まれた場合それは必ず消した位置にあるという性質に気付き、stackでの実装にすぐにたどり着きました。ちょっと考えれば最初からわかることだったのに…
Rustでstackの末尾が"ABC"であることを判定するのはどれが手っ取り早いのでしょうか。とりあえずスライスで書いてみました。
あと、VecをStringに変換するのはString::from_iter関数というのは忘れそうです。
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);
    let mut ans=Vec::<char>::new();
    for i in 0..s.len() {
        ans.push(s[i]);
        let l=ans.len();
        while l>=3 && ans[l-3..] == ['A','B','C'] {
            ans.pop();
            ans.pop();
            ans.pop();
        }
    }
    outputln!(String::from_iter(ans));
}

E問題

atcoder.jp
今回のコンテストの反省点2。
終了直前まで全探索するかグラフ理論の何かしらを使うか迷ってしまいました。
コンテスト時はitertools::Itertoolsを知らなかったのでnext_permutation関数でごり押しました。
atcoder.jp

use ac_library::Dsu;
use itertools::Itertools;
#[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,m:usize,k:usize,uvw:[(Usize1,Usize1,usize);m]);
    let mut ans=k;
    for comb in (0..m).combinations(n-1) {
        let mut uf=Dsu::new(n);
        let mut cost=0;
        for i in comb {
            uf.merge(uvw[i].0, uvw[i].1);
            cost+=uvw[i].2;
            cost%=k;
        }
        if uf.groups().len()==1 {
            ans.chmin(cost);
        }
    }
    outputln!(ans);
}

コンテスト後のサーチでプリューファーコードによるラベルつき木の全列挙を使えると知ったので、敬遠していたプリューファーコードを勉強してライブラリ化しました。
ついでにitertools::Itertoolsにない重複順列の全列挙もライブラリに入れ、グラフライブラリの仕様を少し変えました。
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,m:usize,k:usize,uvw:[(Usize1,Usize1,usize);m]);
    let mut ans=k;
    let g:MapGraph=construct_weighted_graph(n, m, &uvw);
    for code in permutations_with_replacement(n, n-2) {
        let t:VecGraph=code.labeled_tree();
        let mut cost=0;
        let mut ok=true;
        for v in 0..n {
            for &(u,_) in &t[v] {
                if let Some(w)=g.weight(v,u) {
                    if v<u {
                        cost+=w;
                        cost%=k;
                    }
                } else {
                    ok=false;
                }
            }
        }
        if ok {
            ans.chmin(cost);
        }
    }
    outputln!(ans);
}

F問題

atcoder.jp
あまりにも解かれすぎじゃないですか？
知っていればやるだけであるうえに知らなくてもわりと実装できる類とはいえ、水diffなのは怖くなってきますね…
一瞬線形代数かとも思いましたが、連結成分ごとに考える必要があることについて考えているうちに、重みつきUnion-Findのポテンシャルがにあたることに気付きました。
コンテスト時はNyaan's LibraryをコピペしてC++で提出しました。自作ライブラリにも追加。
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,q:usize,abd:[(Usize1,Usize1,isize);q]);
    let mut ans=Vec::<usize>::new();
    let mut wdsu=WeightedDSU::new(n);
    for (i,&(a,b,d)) in abd.iter().enumerate() {
        if wdsu.merge(a,b,d) {
            ans.push(i+1);
        }
    }
    ans.outputln();
}

G問題

atcoder.jp
こういう問題を解けるかどうかが上位陣との差である気がします。
コストが最小になる場合、1種類目の操作を行う回数は高々1回であることと、2種類目の操作は1種類目の操作後ののそれぞれの要素にを加えるのみであることが考察できます。
についてのDPテーブルを、の順列についての「×(それぞれが連番になるようにを分割したときの区間の個数)」の最小値と定義します。
すると、答えはとなります。DPテーブルの定義を変えてずらしてもよいのですが、自分はRustであまりisizeを使いたくないのでこの定義で書きました。
ここで、連番になっている最後の区間を一気に追加してDPを行うことを考えます。
DPの緩和は、をでchminすることで行えます。
また、は各についてを全探索しつつに含まれるものに当たるまでを増やしていけばよいです。
長さの区間は個あり、それぞれの区間を最後につなげられるは個あるので、緩和の回数はとなります。
またbreakする回数もなので、時間計算量はとなります。
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,c:usize,a:[usize;n],b:[usize;n]);
    let mut dp=vec![E[18];1<<n];
    dp[0]=0;
    for s in 0usize..(1<<n) {
        let cnt=s.count_ones().usize();
        for l in 0..n {
            let mut cost=c;
            let mut pos=cnt;
            for r in l..n {
                if (s>>r)%2>0 {
                    break;
                }
                cost+=abs_diff(a[r],b[pos]);
                let tmp=dp[s]+cost;
                dp[s+(1<<(r+1))-(1<<l)].chmin(tmp);
                pos+=1;
            }
        }
    }
    outputln!(dp[(1<<n)-1]-c);
}