AtCoder Beginner Contest 332 (AからFまで) 復習 - 獅子座じゃない人のブログ

Rustで競プロするのに慣れたりライブラリを整備したりするのも兼ねて、ABC332を解き直します。
コンテスト時はA～DとFの5完でした。
風邪（というか副鼻腔炎）なのに無理して参加して死にかけました。逆によくこの状態で入青に立直かけたよ…

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

A問題

atcoder.jp
コンテスト中の提出そのままです。foldにだいぶ慣れてきました。
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,s:usize,k:usize,pq:[(usize,usize);n]);
    let sum=pq.iter().fold(0, |sum,&(p,q)| sum+p*q);
    if sum>=s {
        outputln!(sum);
    } else {
        outputln!(sum+k);
    }
}

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!(k:usize,g:usize,m:usize);
    let mut cur_g=0;
    let mut cur_m=0;
    for _ in 0..k {
        if cur_g==g {
            cur_g=0;
        } else if cur_m==0 {
            cur_m=m;
        } else {
            let tmp=min(g-cur_g,cur_m);
            cur_g+=tmp;
            cur_m-=tmp;
        }
    }
    outputln!(cur_g,cur_m);
}

C問題

atcoder.jp
事故りました。
前回あたりにライブラリにusizeで値を返す二分探索の関数を追加してたんですが、その境界の仕様が不自然で、それに正しく適応するのに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!(_:usize,m:usize,s:Chars);
    outputln!(usize_binary_search(1000, false, |mid| {
        let mut cnt1=m;
        let mut cnt2=mid;
        let mut ok=true;
        for &c in &s {
            if c=='2' {
                if cnt2>0 {
                    cnt2-=1;
                } else {
                    ok=false;
                    break;
                }
            } else if c=='1' {
                if cnt1>0 {
                    cnt1-=1;
                } else if cnt2>0 {
                    cnt2-=1;
                } else {
                    ok=false;
                    break;
                }
            } else {
                cnt1=m;
                cnt2=mid;
            }
        }
        ok
    }));
}

D問題

atcoder.jp
重実装と見せかけた軽実装で助かりました。
C問題のペナとE問題の難しさと風邪で死にかけていた自分を落ち着かせてくれました。

行と列を独立に考えてよいことと、バブルソートの最小回数は転倒数であることさえ知っていれば、行と列それぞれ順列全探索をし、AとBが一致するときの転倒数の和の最小値を答えとすればよいとわかります。

コンテスト中は脳筋do-while（Rustのwhile文の条件に処理を全て書くことで無理矢理do-whileを実装することを勝手にそう呼んでいる）をしていましたが、流石に順列全探索のたびにそれをするのは汚く混乱するので、do-while文をマクロで実装しました。
atcoder.jp

use itertools::Itertools;
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;
use superslice::Ext;

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

    input!(h:usize,w:usize,a:[[usize;w];h],b:[[usize;w];h]);
    let mut hs=(0..h).collect_vec();
    let mut ws=(0..w).collect_vec();
    let mut ans=E[18];
    do_while!{ hs.next_permutation(), {
        do_while!{ ws.next_permutation(), {
            let mut ok=true;
            for i in 0..h {
                for j in 0..w {
                    if a[hs[i]][ws[j]]!=b[i][j] {
                        ok=false;
                    }
                }
            }
            if ok {
                let mut cnt=0;
                for i in 0..h {
                    for j in i+1..h {
                        if hs[i]>hs[j] {
                            cnt+=1;
                        }
                    }
                }
                for i in 0..w {
                    for j in i+1..w {
                        if ws[i]>ws[j] {
                            cnt+=1;
                        }
                    }
                }
                ans.chmin(cnt);
            }
        }}
    }}
    ans.output_val_or(E[18]);
}

E問題

atcoder.jp
入青に失敗した原因。風邪っ引きには厳しかったです。
コンテスト中は平均が固定なことに気付かなかったです。それさえわかっていれば分散の定義の式の変化する部分が $x_i$ のみになるので、より単純な形で書くことができたはずです。
以下の問題の別解を精進していたことから $3^N$ bit DPであることは見抜け、分散を(2乗の平均)-(平均の2乗)で表して解こうと頑張りました。
atcoder.jp
しかし、引き算の最小化となるため桁落ち誤差に殺され、オーバーフローや初期値の設定ミスなどにも殺され、結局解法が合っていることに気付かないまま時間切れとなりました。
特に、オーバーフローや初期値の設定ミスは今の復習でもだいぶひっかかりました。最小化のDPでは横着せず初期値をusize::MAXにし、オーバーフローが起こりそうならsaturatingを使うのが安全そうですね。
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,d:usize,w:[usize;n]);
    let mut ws=vec![0;1<<n];
    let mut dp=vec![vec![usize::MAX;d+1];1<<n];
    let u=(1<<n)-1;
    for s in 0..1<<n {
        for i in 0..n {
            if (s>>i)%2>0 {
                ws[s]+=w[i];
            }
        }
    }
    for s in 0..1<<n {
        dp[s][1]=ws[u].abs_diff(d*ws[s]).saturating_pow(2);
    }
    for s in 0..1<<n {
        let sc=u-s;
        let mut t=sc;
        loop {
            for i in 1..d {
                let tmp=dp[s][i].saturating_add(dp[t][1]);
                dp[s+t][i+1].chmin(tmp);
            }
            if t==0 {
                break;
            }
            t=(t-1)&sc;
        }
    }
    outputln!(dp[u][d] as f64/d as f64/d as f64/d as f64);
}

F問題

atcoder.jp
「やるだけ」で助かりました。

与えられた区間に対して、区間の幅を $L$ 、 $A_i$ を $E_i$ の初期値として ${E_i}'=(L-1)/L\times X+E_i/L$ という一括変更をすればよいことは、ABC-Eレベルの期待値DPなどが解ければ容易にわかります。
この操作は明らかに遅延セグ木で行え、あとはライブラリに入れている遅延セグ木用のアフィン変換を使い、一応何かしらのモノイドを書けば終わりです。

…という感じで一発でACできたのですが、一応書いたモノイドが遅延セグ木に正しく乗せられないものであったことに後から気付き、それならば最初から適当な二項演算と単位元を書いておくべきだったと思いました。一応そちらもライブラリに入れました。

自分の証明が間違っていなければ、そのまま正しく乗せられるモノイドはないようですね。もちろん、ACLならば正しく乗せなくても区間変更1点取得はできます。また、そうでない実装でも、単位元を添加したり長さとの組にしたりすれば乗せられます。できれば、そういう議論は公式解説に載っていてほしいですね。

ABC332-F、要件を守りつつそのまま遅延セグ木に乗せることはできないのかな pic.twitter.com/TtvFDdUDCw
— 獅子座じゃない人🎶🔔❇️ (@Not_Leonian) 2023年12月12日

そうならば双対セグ木も持っておくべきかもと思いましたが、ACLの遅延セグ木は前述の通り（実行速度がおそらくより悪い）双対セグ木として使えることと、そろそろライブラリのサイズが512KiBを超える可能性を考えなければならないことから書かないでおきます。
atcoder.jp

use ac_library::LazySegtree;
#[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,a:[usize;n],lrx:[(Usize1,usize,usize);m]);
    let mut st=LazySegtree::<SegmentAffineTransform<DummyOperation<Mint>>>::new(n);
    for i in 0..n {
        st.set(i, Mint::new(a[i]));
    }
    for (l,r,x) in lrx {
        st.apply_range(l..r, (Mint::new(1)-Mint::new(1)/Mint::new(r-l),Mint::new(x)/Mint::new(r-l)));
    }
    let mut ans=vec![Mint::new(0);n];
    for i in 0..n {
        ans[i]=st.get(i);
    }
    ans.outputln();
}

G問題は、今までネットワークフローの問題を解けたことがないことと、そのなかでもだいぶ応用問題でありそうなことから、やらないでおきます。
他のやらなければならないことも多いですし。