AtCoder Beginner Contest 333 復習 - 獅子座じゃない人のブログ

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

自作ライブラリを使用し、ローカルで事前に展開する形で提出しています。展開前のコードを記述します。
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!(n:usize);
    for _ in 0..n {
        print!("{n}");
    }
    println!();
}

B問題

atcoder.jp
evimaさんの別解がきれいすぎる。
コンテスト中は、ABCDEを数値に変換したときの差が等しいか足して5になるで判定しました。
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!(s:String,t:String);
    let adj="ABCDEAEDCBA";
    output_yes_or_no(adj.contains(&s)==adj.contains(&t));
}

C問題

atcoder.jp
10の累乗のconst配列を用意していたのですが、それをベクタ化して累積和とったらレピュニットが列挙できて助かりました。
その方針がなんだかんだ一番簡潔に書けそうなので、これでよしとします。
ただし本番ではsort後にdedupで重複を削除していたのですが、これは3重ループのカウンタのi,j,kのjをiから、kをjからとすることで必要なくなります。
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);
    let r=E.to_vec().construct_prefix_sum();
    let mut v=Vec::<usize>::new();
    for i in 0..19 {
        for j in i..19 {
            for k in j..19 {
                v.push(r[i+1]+r[j+1]+r[k+1]);
            }
        }
    }
    v.sort();
    outputln!(v[n-1]);
}

D問題

atcoder.jp
頂点1に関する辺だけ除いて連結成分を考える方法に早くに気付き、そのまま最もサイズの大きい連結成分だけを残して頂点1を削除できるようにすればよいことに気付けたのはでかかったです。
atcoder.jp

use ac_library::Dsu;
#[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 mut uf=Dsu::new(n);
    for (u,v) in uv {
        if u*v>0 {
            uf.merge(u, v);
        }
    }
    let gg=uf.groups();
    let mut max=0;
    for g in gg {
        max.chmax(g.len());
    }
    outputln!(n-max);
}

E問題

atcoder.jp
結果的に入青できたからよかったものの、見た瞬間に後ろからの貪欲で解けるとわかったのに誤読やデバッグによる正しい部分の改変などで時間を取られてしまったのが痛かったです。
自作ライブラリにはVecDequeの出力関数は用意してない（し用意するつもりもない）ので、答えの2行目のデータ構造をVecDequeにしてしまったのも一因かもしれません。
あとは、答えの1行目は「(これより後で倒さないといけないモンスターの総数)-(これより後で手に入るポーションの総数)」の最大値なので、前から見直して計算する必要はないです。（またシンプルに、ポーションが手に入った後から入る前に戻れば個数は減り、モンスターを倒した後から倒す前に戻れば個数は増えるともいえます。）　ただ、今の自分にコンテスト中にここまで考察して綺麗に書けというのはちょっと苦かもしれません。
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,tx:[(usize,Usize1);n]);
    let mut pcnt=vec![0;n];
    let mut mcnt=vec![0;n];
    let mut ans1=0;
    let mut ans2=Vec::<usize>::new();
    let mut cur_p=0;
    let mut cur_m=0;
    for &(t,x) in tx.iter().rev() {
        if t==1 {
            if pcnt[x]<mcnt[x] {
                pcnt[x]+=1;
                ans2.push(1);
                cur_p+=1;
            } else {
                ans2.push(0);
            }
        } else {
            mcnt[x]+=1;
            cur_m+=1;
        }
        ans1.chmax(cur_m-cur_p);
    }
    let mut ok=true;
    for i in 0..n {
        if pcnt[i]<mcnt[i] {
            ok=false;
            break;
        }
    }
    if ok {
        ans2.reverse();
        outputln!(ans1);
        ans2.outputln();
    } else {
        outputln!(-1);
    }
}

F問題

atcoder.jp
kanpurinさんの別解と同じ方法で解きました。

最初の10分くらいとっかかりが見つからなかったですが、 $N=2$ の場合を試してすぐにこの関係に気付けたのはよかったです。
最後連立方程式を解くときに分母分子のはらい方を逆にしてしまい、20分くらい無駄にしてしまいました。結果的にはACして入青できたのでよかったですが。
あと、Mintをライブラリ内で定義していたのにそれを忘れたり、 $\mathrm{DP}[i][j]\ (j\gt 1)$ を計算するのに元の等式を使わず $\mathrm{DP}[i][1]$ から計算しようとしたり、無駄なムーブが多かったです。
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);
    let mut dp=vec![vec![Mint::new(1);n];n+1];
    let inv=Mint::new(1)/2;
    for i in 1..n {
        let mut b=Mint::new(0);
        for j in 0..i {
            b+=dp[i][j];
            b*=inv;
        }
        b*=inv;
        let p=Mint::new(2).pow(i as u64+1);
        dp[i+1][0]=b*p/(p-1);
        for j in 0..i {
            dp[i+1][j+1]=dp[i][j]*inv+dp[i+1][j]*inv;
        }
    }
    dp[n].outputln();
}

maspyさんの別解がきれいすぎます。

各試行は独立なので、取り除かれた人が勝手に列の末尾に残っていると考えても問題ありません。
この場合の求める確率は、順番に1/2の確率で当たるくじを引いていき、全員のなかでその人が当てるのが最後となる確率となります。
人 $i$ が最後で $k$ 回目に当てた場合、人 $i'\ (i'\lt i)$ は全員 $k$ 回以内に当てており、人 $i'\ (i'\gt i)$ は全員 $(k-1)$ 回以内に当てていることになります。
したがって、求める確率は $\sum_{k=1}^{\infty} 2^{-k}(1-2^{-k})^{i-1}(1-2^{-k+1})^{N-i}$ と表せます。
ここで、 $f_i(x)=x(1-x)^{i-1}(1-2x)^{N-i}$ とおくと、以下のように式変形ができます。
$\displaystyle \begin{align*}\sum_{k=1}^{\infty} 2^{-k}(1-2^{-k})^{i-1}(1-2^{-k+1})^{N-i}&=\sum_{k=1}^{\infty} f_i(2^{-k})\\&=\sum_{k=1}^{\infty}\left(\sum_{j=1}^N 2^{-jk}[x^j]f_i(x)\right)\\&=\sum_{j=1}^N\left([x^j]f_i(x)\cdot\sum_{k=1}^{\infty} 2^{-jk}\right)\\&=\sum_{j=1}^N\left(\frac{1}{2^j-1}[x^j]f_i(x)\right)\end{align*}$

あとは、 $f_i(x)$ から $f_{i+1}(x)$ を求めるために疎な多項式の乗除を行えばよいです。
疎な多項式についての乗除などは前にライブラリに入れようとして諦めていたのですが、このさい追加しました。
$1/(2^j-1)$ の前計算をしないと明らかに遅くなることに注意。
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);
    let mut f=vec![(0,Mint::new(1)),(1,Mint::new(-2))].sparse_fps_pow(n-1, n-1);
    let mut invs=vec![Mint::new(1);n+1];
    for j in 1..=n {
        invs[j]=Mint::new(1)/(Mint::new(2).pow(j as u64)-1);
    }
    f.move_right(1, Mint::new(0));
    let mut ans=vec![Mint::new(0);n];
    for j in 1..=n {
        ans[0]+=f[j]*invs[j];
    }
    for i in 1..n {
        f.sparse_fps_div_assign(&vec![(0,Mint::new(1)),(1,Mint::new(-2))], n);
        f.sparse_fps_mul_assign(&vec![(0,Mint::new(1)),(1,Mint::new(-1))], n);
        for j in 1..=n {
            ans[i]+=f[j]*invs[j];
        }
    }
    ans.outputln();
}

G問題

atcoder.jp
ファレイ数列は競プロやる前から興味持ってた概念ではありますが、微妙に忙しいのでガバガバupsolveで終わらせます。
最良近似分数についてはmaspyさんの記事があるので、その通りにファレイ数列の中間数を取り続けます。
maspypy.com
入力の有理数のパースのみ頑張れば、RustではRatioに任せることができます。
しかし、このままでは無限ループでTLEになってしまう場合があり、それはおかしいです（暴論）。
よって、TLEにならない程度に十分大きい回数ループを回してそのまま出力すると、ACします（ガバガバ）。

本番でも、こういうずる賢い立ち回りしてみたいですね。
atcoder.jp

#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;
use num_rational::Ratio;

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

    input!(r:String,n:u128);
    let r=Ratio::<u128>::new(r[2..].parse().unwrap(), E[r.len()-2] as u128);
    if *r.denom()<=n {
        outputln!(r.numer(),r.denom());
        return;
    }
    let mut l=Ratio::<u128>::new(0, 1);
    let mut u=Ratio::<u128>::new(1, 1);
    let mut cnt=0;
    while l.denom()+u.denom()<=n && cnt<8000000 {
        let m=Ratio::<u128>::new(l.numer()+u.numer(), l.denom()+u.denom());
        if m<=r {
            l=m;
        } else {
            u=m;
        }
        cnt+=1;
    }
    if r-l<=u-r {
        outputln!(l.numer(),l.denom());
    } else {
        outputln!(u.numer(),u.denom());
    }
}

Pythonだと標準ライブラリでさらに楽にACできるようですね。
ただし、小さいほうを出力という最後の条件を満たすためには、あらかじめ十分絶対値の小さい数を引いておくか、返ってきた値と同じ差の小さいほうの値が存在しないかを確認するかをする必要があるようです。

追記
TLEになるのは、最良近似分数の片側が更新されずにもう片側に足され続けることによってオーダーが悪化する場合であると気付きました。たとえば、ずっと下側が $0/1$ のまま、上側が $k/(k+1)$ として更新され続ける場合です。
したがって、どこまで片側が更新されないかを二分探索すればかなり高速にACできます。

この解法と連分数展開の関係はいつかちゃんと考えたいですね。
atcoder.jp

#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;
use num_rational::Ratio;

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

    input!(r:String,n:u128);
    let r=Ratio::<u128>::new(r[2..].parse().unwrap(), E[r.len()-2] as u128);
    if *r.denom()<=n {
        outputln!(r.numer(),r.denom());
        return;
    }
    let mut l=Ratio::<u128>::new(0, 1);
    let mut u=Ratio::<u128>::new(1, 1);
    while l.denom()+u.denom()<=n {
        let m=Ratio::<u128>::new(l.numer()+u.numer(), l.denom()+u.denom());
        if m<=r {
            let k=binary_search(1, (n-l.denom())/u.denom()+1, |mid| {
                Ratio::<u128>::new(l.numer()+mid*u.numer(), l.denom()+mid*u.denom())<=r
            });
            l=Ratio::<u128>::new(l.numer()+k*u.numer(), l.denom()+k*u.denom());
        } else {
            let k=binary_search(1, (n-u.denom())/l.denom()+1, |mid| {
                Ratio::<u128>::new(mid*l.numer()+u.numer(), mid*l.denom()+u.denom())>r
            });
            u=Ratio::<u128>::new(k*l.numer()+u.numer(), k*l.denom()+u.denom());
        }
    }
    if r-l<=u-r {
        outputln!(l.numer(),l.denom());
    } else {
        outputln!(u.numer(),u.denom());
    }
}