AtCoder Beginner Contest 336 (ABC336) 復習

Rustで競プロするのに慣れたりライブラリを整備したりするのも兼ねて、ABC336を解き直します。
コンテスト時はA～Fの6完でした。
落水の危機だったので、黄パフォでHighest更新できてよかったです。

自作ライブラリを使用し、ローカルで事前に明らかに未使用な部分を除いて展開する形で提出しています。展開前のソースコードを記述します。
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);
    print!("L");
    for _ in 0..n {
        print!("o");
    }
    println!("ng");
}

B問題

atcoder.jp
ライブラリ盆栽のおかげでtrailing_zeros関数を知っていたので助かりました。leading_zeros関数とちょっと迷った。
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);
    outputln!(n.trailing_zeros());
}

C問題

atcoder.jp
Rustは基数変換の自由度が低いので自力で実装する必要がありますが、そんなに大変でもないのでとりあえずはライブラリに追加しないでおきます。
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!(mut n:Usize1);
    let mut ans=0;
    let mut d=2;
    while n>0 {
        ans+=n%5*d;
        n/=5;
        d*=10;
    }
    outputln!(ans);
}

D問題

atcoder.jp
evimaさんの別解のほうで解きました。
左側と右側でそれぞれ、その位置を頂点とした最大レベルを考えるとそれ以下のレベルは全て達成できるということに早めに気付けたのがよかったです。

公式解説のほうの考え方に近い類題もあるという噂ですが、面倒なのでとりあえずは解かないでおきます。
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,a:[usize;n]);
    let mut left=vec![1;n];
    let mut right=vec![1;n];
    for i in 0..n-1 {
        if a[i+1]>left[i] {
            left[i+1]=left[i]+1;
        } else {
            left[i+1]=a[i+1];
        }
    }
    for i in (1..n).rev() {
        if a[i-1]>right[i] {
            right[i-1]=right[i]+1;
        } else {
            right[i-1]=a[i-1];
        }
    }
    let mut ans=1usize;
    for i in 0..n {
        ans.chmax(min(left[i],right[i]));
    }
    outputln!(ans);
}

E問題

atcoder.jp
桁DPであることをすぐに察して、精進除けば初めてですがググってちゃんと早めに書けたのがよかったです。
ただし、また型推論に頼って答えをi32にしてしまい1ペナをつけたのがもったいないです。入力を受け取る変数はproconioで型を書くわけですが、出力のための変数もこれから型を書いていくようにしたいと思います。

DPテーブルの桁和に関する個数を可変にしようが固定にしようが、足す一番下の桁の数のループは適切にbreakする必要があるという点に気を付ける必要があります。また、実装にもよりますが最初の0の桁を考える場合、それはNの一番上の桁の上に0を書いておくようなものなので、Nと同じほうの添字に最初の1を入れる点にも注意が必要です。

一番下の遷移はループではないですが、ループとして書いてしまったほうがむしろ早く書けるかもしれません。
atcoder.jp

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

const MAX:usize=9*14;

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

    input!(n:usize);
    let mut m=n;
    let mut d=Vec::new();
    while m>0 {
        d.push(m%10);
        m/=10;
    }
    d.reverse();
    let mut ans=0usize;
    for i in 1..=MAX {
        let mut dp=vec![vec![vec![vec![0;i];i+1];2];d.len()+1];
        dp[0][1][0][0]=1;
        for j in 0..d.len() {
            for k in 0..=i {
                for l in 0..i {
                    for m in 0..10 {
                        if k+m>i {
                            break;
                        }
                        dp[j+1][0][k+m][(l*10+m)%i]+=dp[j][0][k][l];
                    }
                    for m in 0..d[j] {
                        if k+m>i {
                            break;
                        }
                        dp[j+1][0][k+m][(l*10+m)%i]+=dp[j][1][k][l];
                    }
                    for m in d[j]..=d[j] {
                        if k+m>i {
                            break;
                        }
                        dp[j+1][1][k+m][(l*10+m)%i]+=dp[j][1][k][l];
                    }
                }
            }
        }
        ans+=dp[d.len()][0][i][0]+dp[d.len()][1][i][0];
    }
    outputln!(ans);
}

F問題

atcoder.jp
ちゃんと問題文を読み、すぐに半分全列挙であることを見抜けてよかったです。
しかし、全体的に実装は良くなかったので確認していきます。

まず、bit全探索ではなくBFSを使うことで時間計算量が\Theta(2^K KHW)から\Theta(\sqrt{3}^K KHW)（ただしK=20）に落ちます。コンテスト中は定数倍の枝刈りだと思い無視していましたが、よく考えたら自明ですね。
また、多少富豪的プログラミングにはなってしまいますが、swapするよりもコピーして全て書き換えたほうが実装が楽です。
そして、常に半分全列挙するのではなく、10回以内に目的の盤面にたどり着けたか、ちょうど10回でたどり着けた盤面へ10回以内に目的の盤面からたどり着けるか、というので判定していったほうが単純になります。

こういう問題はどうしてもメモリをかなり使用してしまいますね。i32をu8に変えたものも試してみたのですが、いうほどは変わりませんでした。
atcoder.jp

use std::collections::{BTreeMap, VecDeque, BTreeSet};

use itertools::iproduct;
#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;

const HALF:i32=10;

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

    input!(h:usize,w:usize,s:[[i32;w];h]);
    let t=vec_range(0, h, |i| vec_range(0, w, |j| (i*w+j+1) as i32));
    let mut seen=BTreeMap::from([(s.clone(),0)]);
    let mut ten=BTreeSet::new();
    let mut queue=VecDeque::from([(s.clone(),0)]);
    while let Some((p,c))=queue.pop_back() {
        if *p==t {
            outputln!(c);
            return;
        }
        if c==HALF {
            continue;
        }
        for (x,y) in iproduct!([0,1],[0,1]) {
            let mut new=p.clone();
            for i in 0..h-1 {
                for j in 0..w-1 {
                    new[h-2-i+x][w-2-j+y]=p[i+x][j+y];
                }
            }
            if !seen.contains_key(&new) {
                seen.insert(new.clone(), c+1);
                if c+1==HALF {
                    ten.insert(new.clone());
                }
                queue.push_front((new,c+1));
            }
        }
    }
    let mut seen=BTreeMap::<Vec<Vec<i32>>,i32>::from([(t.clone(),0)]);
    let mut queue=VecDeque::<(Vec<Vec<i32>>,i32)>::from([(t.clone(),0)]);
    while let Some((p,c))=queue.pop_back() {
        if ten.contains(&p) {
            outputln!(HALF+c);
            return;
        }
        if c==HALF {
            continue;
        }
        for (x,y) in iproduct!([0,1],[0,1]) {
            let mut new=p.clone();
            for i in 0..h-1 {
                for j in 0..w-1 {
                    new[h-2-i+x][w-2-j+y]=p[i+x][j+y];
                }
            }
            if !seen.contains_key(&new) {
                seen.insert(new.clone(), c+1);
                queue.push_front((new,c+1));
            }
        }
    }
    outputln!(-1);
}

G問題

atcoder.jp
F問題が解けた時点でほぼコンテスト終了間際だったので、ほぼ問題文は見れていませんでしたが、ちゃんと見ても問題文の理解に時間をかけていたと思います。
とはいえ、de Bruijn列の知識はあったのに問題とその解説を見てそれを思い浮かべられなかったのは反省です。

この問題はまず、de Bruijn列、BEST定理、有向行列木定理を知っているかという部分が難しいと思います。
実装で気を付けるべき点がいくつかあるのはそうなのですが、高度典型は意外と理解するだけなら難しくないのでこういう問題を精進するのは大事だと思っています。

まず、問題をde Bruijn列の一般化として考えることで、準オイラーグラフまたはオイラーグラフのもつオイラー路の個数を求める問題に帰着できます。
帰着したグラフがその2つのどちらかでなければ答えは0です。
オイラーグラフであった場合、オイラー回路の個数を求め、どの辺からスタートするかという意味でN倍すればよいです。
準オイラーグラフであった場合、始点と終点を結ぶ辺を1本追加してオイラー回路の個数を求めればよいです。
オイラーグラフのもつオイラー回路の個数はBEST定理で求めることができます。（BEST定理、主張のわりに証明が難しくなくて面白いですね）
そして、BEST定理中に現れる有向全域木の個数は有向行列木定理を使って求めることができます。
ここで、BEST定理では多重辺を区別しますが、この問題では多重辺を区別しないことに注意が必要です。

実装で気を付けるべき点がいくつかあります。
まず、準オイラーグラフまたはオイラーグラフとして考えるために孤立点は除く必要があります。
また、グラフの有向ラプラシアン行列を考えるとき、自己ループは除く必要があります。
また細かい点として、準オイラーグラフで辺を実際に追加して考えた場合、多重辺を区別しないことの考慮のときに辺の個数を戻して考える必要があります。

ライブラリに行列式を求める関数を追加しました。いつか追加しようと思っていたので良い機会です。掃き出し法もどっかで追加しなきゃ…
（ところで、公式解説の自然な実装の時間計算量のオーダーがO(B^4+N)となっているのは何なのでしょう？解説の主張通りに自然に書くならB^5で、工夫するとしてもB^3だと思います）
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!(x:[usize;16]);
    let mut n=0;
    let mut g=vec![vec![0;8];8];
    let mut outdeg=vec![0;8];
    let mut indeg=vec![0;8];
    for i in 0..16 {
        n+=x[i];
        g[i/2][i%8]+=x[i];
        outdeg[i/2]+=x[i];
        indeg[i%8]+=x[i];
    }
    let invs=Mint::construct_modint_inverses(n);
    let facts=Mint::construct_modint_facts(n);
    let factinvs=Mint::construct_modint_fact_inverses(n, &invs);
    let mut eulerian=true;
    for v in 0..8 {
        if outdeg[v]!=indeg[v] {
            eulerian=false;
        }
    }
    let mut start=0;
    let mut finish=0;
    if !eulerian {
        let mut ok=true;
        let mut exists_start=false;
        let mut exists_finish=false;
        for v in 0..8 {
            if outdeg[v]==indeg[v]+1 {
                if exists_start {
                    ok=false;
                    break;
                } else {
                    start=v;
                    exists_start=true;
                }
            } else if outdeg[v]+1==indeg[v] {
                if exists_finish {
                    ok=false;
                    break;
                } else {
                    finish=v;
                    exists_finish=true;
                }
            } else if outdeg[v]!=indeg[v] {
                ok=false;
                break;
            }
        }
        if ok && exists_start && exists_finish {
            g[finish][start]+=1;
            outdeg[finish]+=1;
            indeg[start]+=1;
        } else {
            outputln!(0);
            return;
        }
    }
    let vertices=(0..8).filter(|&i| outdeg[i]>0).collect::<Vec<_>>();
    let mut laplacian=vec![vec![Mint::new(0);vertices.len()-1];vertices.len()-1];
    for i in 0..vertices.len()-1 {
        let v=vertices[i];
        for j in 0..vertices.len()-1 {
            let u=vertices[j];
            if v!=u {
                laplacian[i][j]=-Mint::new(g[v][u]);
            } else {
                laplacian[i][j]=Mint::new(outdeg[v]-g[v][v]);
            }
        }
    }
    let mut ans=laplacian.determinant();
    for &v in &vertices {
        ans*=facts[outdeg[v]-1];
    }
    if eulerian {
        ans*=n;
    } else {
        g[finish][start]-=1;
    }
    for &v in &vertices {
        for &u in &vertices {
            ans*=factinvs[g[v][u]];
        }
    }
    outputln!(ans);
}