AtCoder Beginner Contest 334 (ABC334) 復習 - 獅子座じゃない人のブログ

Rustで競プロするのに慣れたりライブラリを整備したりするのも兼ねて、ABC334を解き直します。
コンテスト時はA～Eの5完でした。
入青してから初めての冷えです。パフォ1400が半色下って嘘だろ…

自作ライブラリを使用し、ローカルで事前に展開する形で提出しています。展開前のソースコードを記述します。
AtCoderで使えるクレートに含まれない関数などを使っている可能性があること、破壊的変更をこの記事の投稿後にしている可能性があることにご注意ください。
github.com
この復習から自作の提出用プログラムを使用して、展開時に明らかに未使用のブロックを削除するようにしてみました。
とはいえ実質的に未使用なimplブロック等を削除しない仕様にしており、展開後のソースコードは提出結果から見られるので、これからも記事に記述するのは展開前のソースコードとします。
どこかバグってそうで本番で使うのはちょっと怖い…
バグっててもCEになるだけですし、直近の数回のコンテストで提出してデバッグはしているのですが…
github.com

A問題

atcoder.jp
なんでや！野球関係ないやろ！
コンテスト中は出力形式でBatとGloveの綴りを確認しながら解きました。
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!(b:usize,g:usize);
    outputif(b>g, "Bat", "Glove");
}

B問題

atcoder.jp
トラウマの問題になりました。
舐めた場合分けを書いて2ペナ。結局ACできたころには21:25になっていました。最後、愚直解と比べる全探索を書けたのは偉い。
R以西の最も東のツリーの位置と、Lより西の最も東のツリーの位置を調べるという方針はよかったのですが、ずらして考えるという発想がなかったため爆死。
ずらして考えるのができなければ実装系の青diff以上のF問題が解けない未来が見えます。気をつけなければ。

あと、Rustのnum_integerにはdiv_floor関数やmod_floor関数があるようですね。それ自体は嬉しいんですが、nightlyの標準ライブラリに採用されてるせいで警告が出るのが惜しい。
コンテスト中ならばそのまま提出しちゃうかもしれません。ただ、自分は警告出てると気が散っちゃうのでちょっと時間取ってでもallow書くかも？
atcoder.jp

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

#[allow(unstable_name_collisions)]

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

    input!(a:isize,m:isize,l:isize,r:isize);
    let l=l-a;
    let r=r-a;
    let lt=(l-1).div_floor(&m);
    let rt=r.div_floor(&m);
    outputln!(rt-lt);
}

ずらして考える方針とdiv_floor関数さえあればこんなに簡単なんですね…悔しい…
あと、二分探索を使うという方針もありだったようです。こっちならノーペナで書けた自信あります…
B問題でD問題相当のアルゴリズムを使わない単純な実装を最近心がけていましたが、B問題といえども制約が厳しければD問題相当のアルゴリズムを使うのもありだと思いました。

C問題

atcoder.jp
B問題ほどではないにしても、こちらもだいぶトラウマになりました。
色1・色9・色10・色18があったとして最初に色9と色10をとるのが最適なわけないだろ！短絡的すぎる
そもそもC問題で優先度つきキューによる計算量削減が出るわけないだろ！

優先度つきキューの地味に面倒な嘘解法を書いてWA。上の例を見つけて、隣同士をとるのが最適なことにやっと気づきました。
$k$ が偶数の場合はそのまま隣同士の和をとっておけばよく、奇数の場合は使わない1つを求めるのを累積和と差分更新で高速化すればよいというのは、流石にその後すぐにわかりました。

コンテスト直後はARC-Aだったら不等式を書いてノーペナで通せていたと息巻いていましたが、今不等式による論証を書こうとして失敗したのでそんなことはなかったです。実力です。
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!(_:usize,k:usize,a:[usize;k]);
    if k%2==0 {
        let mut ans=0;
        for i in 0..k/2 {
            ans+=a[2*i+1]-a[2*i];
        }
        outputln!(ans);
    } else {
        let mut ans=0;
        for i in 0..k/2 {
            ans+=a[2*i+1]-a[2*i];
        }
        let mut tmp=ans;
        for i in (0..k/2).rev() {
            tmp-=a[2*i+1]-a[2*i];
            tmp+=a[2*i+2]-a[2*i+1];
            ans.chmin(tmp);
        }
        outputln!(ans);
    }
}

D問題

atcoder.jp
B, Cに比べて流石に典型すぎる。
これはもう自作ライブラリで殴るだけでしょう。
自作ライブラリのcalculate_partial_sum関数とusize_binary_search関数はともに半開区間で実装されているため、上限をn+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,q:usize,mut r:[usize;n],x:[usize;q]);
    r.sort();
    let rsum=r.construct_prefix_sum();
    for x in x {
        outputln!(usize_binary_search(n+1, true, |mid| {
            rsum.calculate_partial_sum(0, mid)<=x
        }))
    }
}

E問題

atcoder.jp
コンテスト中はUndo可能Union-FindをNyaan's LibraryからとってきてC++で提出してしまいました。必要なかったですね。
とはいえ、記述量がそこまで変わるわけではないので、自作ライブラリに入れていたらそのほうがよいかもしれませんね。

操作によって、操作する頂点と隣接した頂点を含む連結成分数は1になります。なので、操作する頂点と隣接した頂点のもとの連結成分数がわかればよいです。
これは色々な方法がありますが、たとえばUnion-Findで属する連結成分を代表する頂点をとり、その個数を数えることなどでできます。

グリッドからグラフを構築する関数を自作ライブラリに追加しました。
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!(h:usize,w:usize,s:[Chars;h]);
    let adj=VecGraph::from_grid(h, w, &s, '!');
    let g=VecGraph::from_grid(h, w, &s, '.');
    let mut uf=g.construct_union_find();
    let mut reds=0;
    for i in 0..h {
        for j in 0..w {
            if s[i][j]=='.' {
                reds+=1;
            }
        }
    }
    let inv=Mint::new(1)/reds;
    let mut ans=Mint::new(uf.groups().len()-reds);
    let graph_num=|i:usize,j:usize| i*w+j;
    let grid_num=|k:usize| (k/w,k%w);
    for i in 0..h {
        for j in 0..w {
            if s[i][j]=='.' {
                let v=graph_num(i,j);
                let mut leaders=Vec::new();
                for &(u,_) in &adj.get()[v] {
                    let (k,l)=grid_num(u);
                    if s[k][l]=='#' {
                        leaders.push(uf.leader(u));
                    }
                }
                leaders.sort_and_dedup();
                ans-=inv*leaders.len();
            }
        }
    }
    ans+=1;
    outputln!(ans);
}

F問題

atcoder.jp
B, Cのせいであまり時間が残っていなかったとはいえ、順番通りに巡るのだから計算量 $\Theta(NK)$ の自明なDPが存在することくらいはコンテスト中に気付けないと青の実力とはいえないでしょう。
とはいえARC・AGCならともかく、この計算量削減をABCの時間でやるのは厳しく、わかってもどうせ間に合わなかったとは思います。
あと、なぜかこの問題だけcargo-competeが浮動小数点数の問題だと認識してくれていませんでしたし。

どうしても悔しかったので、計算量削減は解説を参考にせず解いてみました。
正直載っている解説より楽な方法が出来上がりました。遅延セグ木（というか双対セグ木）最高！
not-leonian.hatenablog.com

atcoder.jp

use ac_library::{Monoid, MapMonoid, LazySegtree};
#[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,k:usize,mut xy:[(f64,f64);n+1]);
    let mut dp=LazySegtree::<MinAndAdd>::new(n+1);
    dp.set(0, 0.);
    for i in 1..=n {
        dp.apply_range(i..=n, (two_d_hypot(xy[i-1], xy[i]), 1e18));
        let have_nothing=dp.get(i-1);
        dp.apply_range(i..=min(n,i-1+k), (0., have_nothing+two_d_hypot(xy[i-1], xy[0])+two_d_hypot(xy[i], xy[0])));
    }
    outputln!(dp.get(n)+two_d_hypot(xy[n], xy[0]));
}

struct Min;

impl Monoid for Min {
    type S = f64;
    fn identity() -> Self::S {
        1e18
    }
    fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
        min(*a, *b)
    }
}

struct MinAndAdd;

impl MapMonoid for MinAndAdd {
    type M = Min;
    type F = (f64, f64);
    fn identity_map() -> Self::F {
        (0., 1e18)
    }
    fn mapping(f: &Self::F, x: &<Self::M as Monoid>::S) -> <Self::M as Monoid>::S {
        min(x+f.0, f.1)
    }
    fn composition(f: &Self::F, g: &Self::F) -> Self::F {
        (f.0+g.0, min(f.0+g.1, f.1))
    }
}

G問題

atcoder.jp
コンテスト中はオンラインダイコネをC++の何かのライブラリからとってきてTLEし、オフラインに切り替えようとして良いライブラリを探しているところで時間切れになりました。

前にBlock Cut Treeについて履修したときにちゃんとLowlinkについても勉強すべきでした。
関節点や橋の問題はまずLowlinkを疑うようにしましょう。

Lowlinkは主に関節点や橋の検出に使用されますが、ある頂点とその頂点から出る辺をグラフから削除したとき、その頂点を含む連結成分が何個の連結成分に変化するかというのも関節点の検出を応用することで求まります。
連結な無向グラフについてDFSをすると全域有向木を考えることができます。この有向木に辺 $(v,u)$ が存在するならば、元のグラフには辺 $\{v,u\}$ が存在します。また、 $\mathrm{ord}[v]$ と $\mathrm{low}[v]$ をそれぞれ行きがけ順のDFSで頂点 $v$ に何番目に到達したか、有向木に元々ある辺の逆でない辺を高々1個追加して頂点 $v$ から到達できる頂点の $\mathrm{ord}$ の最小値と定義します。
求めたい個数は、DFSの根である場合は有向木の子の個数となります。根でない場合は頂点を $v$ として、その子 $u$ が $\mathrm{ord}[v]\leq\mathrm{low}[u]$ を満たす個数に1を足したものとなります。

Block Cut Treeについて履修したときに再帰Lowlinkは書いたことがあったのですが、非再帰Lowlinkをライブラリに追加しようとして痛い目を見ました。
まず、帰りがけ順も $\mathrm{low}$ を更新する必要があります。また、 $\mathrm{ord}$ に値を代入するタイミングは子を見るタイミングではなく、実際に到達したタイミングです。そして、連結成分ごとに配列を作るよりも1回で全ての連結成分を見るようにしたほうがよいです。また、連結成分数を求めるとき、有向木の親子関係を考慮する必要があります。
それらに気をつければ、そこまで実装は大変ではないと思います。
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!(h:usize,w:usize,s:[Chars;h]);
    let g=VecGraph::from_grid(h, w, &s, '.');
    let mut uf=g.construct_union_find();
    let mut reds=0;
    for i in 0..h {
        for j in 0..w {
            if s[i][j]=='.' {
                reds+=1;
            }
        }
    }
    let inv=Mint::new(1)/(h*w-reds);
    let groups=uf.groups();
    let mut ans=Mint::new(groups.len()-reds);
    let graph_num=|i:usize,j:usize| i*w+j;
    let (ord,low,parent)=g.lowlink();
    for i in 0..h {
        for j in 0..w {
            if s[i][j]=='#' {
                ans+=inv*g.number_of_connected_components_after_removing(graph_num(i,j), &ord, &low, &parent);
            }
        }
    }
    ans-=1;
    outputln!(ans);
}

Undo可能Union-Findと分割統治法を合わせた別解もやってみました。面白いですね。分割統治法まだ本番で使ったことがないのでいつか使えるようになりたい。

緑色の頂点の個数を $N$ とおき、それぞれの頂点をラベリングします。 $C(l,r)$ を $l$ 以上 $r$ 未満のラベルがついた頂点が赤色に塗られたときの連結成分数と定義します。すると、頂点 $v$ のみを赤く塗ったときの連結成分数は $C(v,v+1)$ となります。また、明らかに $C(0,N)=0$ です。
そして、区間を狭める操作がE問題のように赤色から緑色に塗る操作になり、より単純になります。
また、 $m=(l+r)/2$ として $C(l,r)$ から $C(l,m)$ と $C(m,r)$ を再帰的に求めていけば、計算量を削減できます。

再帰的に求めるためにはUndo可能Union-Findが使えます。 $C(l,r)$ から $C(l,m)$ を求めるためには、 $m$ 以上 $r$ 未満のラベルがついた頂点と $l$ 以上 $m$ 未満でないラベルのついた頂点を結ぶ辺を追加し、マージできた場合連結成分数を減らせばよいです。そして、マージする前にRollbackして、同様に $C(m,r)$ も求めればよいです。

Undo可能Union-Findをライブラリに追加しました。仕組みも実装も単純で良いですね。
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!(h:usize,w:usize,s:[Chars;h]);
    let g=VecGraph::from_grid(h, w, &s, '.');
    let mut greens=Vec::<usize>::new();
    for i in 0..h {
        for j in 0..w {
            if s[i][j]=='#' {
                greens.push(i*w+j);
            }
        }
    }
    let inv=Mint::new(1)/greens.len();
    let mut ans=Mint::new(0);
    let mut uf=DSUWithRollback::new(h*w);
    solve(0, greens.len(), 0, &mut uf, &mut ans, inv, &g, &greens);
    outputln!(ans);
}

fn solve(l: usize, r: usize, a: usize, uf: &mut DSUWithRollback, ans: &mut Mint, inv: Mint, g: &VecGraph, greens: &Vec<usize>) {
    if l+1==r {
        *ans+=inv*a;
        return;
    }
    let mut b=a;
    let m=(l+r)/2;
    let cur=uf.current_number();
    b+=r-m;
    for i in m..r {
        let v=greens[i];
        for &(u,_) in &g.get()[v] {
            if u<greens[l] || u>=greens[m] {
                if uf.merge(v, u) {
                    b-=1;
                }
            }
        }
    }
    solve(l, m, b, uf, ans, inv, g, greens);
    uf.rollback(cur);
    let mut b=a;
    b+=m-l;
    for i in l..m {
        let v=greens[i];
        for &(u,_) in &g.get()[v] {
            if u<greens[m] || u>greens[r-1] {
                if uf.merge(v, u) {
                    b-=1;
                }
            }
        }
    }
    solve(m, r, b, uf, ans, inv, g, greens);
    uf.rollback(cur);
}