AtCoder Beginner Contest 327 (AからFまで) 復習

Rustで競プロするのに慣れたりライブラリを整備したりするのも兼ねて、ABC327を解き直します。
リアルの都合で復習の記事がしばらく投稿できませんでしたね。
これからもできないときはやらず、できるときも自分のレートに比べて極めて難しい問題はリアルの都合に合わせる形にしようと思います。

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

A問題

atcoder.jp
これはコンテスト時の提出そのままで、contains関数でよいでしょう。
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,s:String);
    output_yes_or_no(s.contains("ab") || s.contains("ba"));
}

B問題

atcoder.jp
これもほぼコンテスト中の提出そのまま。
であることに気付けば、探索する範囲が1から15までなのはほぼ明らかでしょう。
pow関数の引数の型はu32のようです。
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);
    for a in 1..16usize {
        if a.pow(a as u32)==b {
            outputln!(a);
            return;
        }
    }
    outputln!(-1);
}

C問題

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!(a:[[usize;9];9]);
    let mut ans=true;
    for i in 0..9 {
        let mut tmp=vec_range(0, 9, |j| a[i][j]);
        tmp.sort();
        tmp.dedup();
        if tmp.len()<9 {
            ans=false;
        }
    }
    for j in 0..9 {
        let mut tmp=vec_range(0, 9, |i| a[i][j]);
        tmp.sort();
        tmp.dedup();
        if tmp.len()<9 {
            ans=false;
        }
    }
    for i in 0..9 {
        let mut tmp=vec_range(0, 9, |j| a[i%3*3+j%3][i/3*3+j/3]);
        tmp.sort();
        tmp.dedup();
        if tmp.len()<9 {
            ans=false;
        }
    }
    output_yes_or_no(ans);
}

D問題

atcoder.jp
問題文の見た目はごついですが、読み砕くと二部グラフの判定問題です。
を真理値として、がいえるため、判定問題は2-SATに帰着できます。
ac-library-rsの2-SATを用いてライブラリ化しておきました。
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,a:[Usize1;m],b:[Usize1;m]);
    let ab=vec_range(0, m, |i| (a[i],b[i]));
    let g:VecGraph=construct_graph(n, m, &ab);
    output_yes_or_no(g.is_bipartite_graph().is_some());
}

E問題

atcoder.jp
今回レートが冷えなかった勝因。
を固定すると第1項の分子を最大化する問題になるということに早めに気付けたので、回目までのコンテストで個選んだ場合の最大値をDPテーブルとするDPにわりとすんなり辿り着けました。
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,p:[usize;n]);
    let mut dp=vec![vec![-1e18;n+1];n+1];
    dp[0][0]=0.;
    for i in 0..n {
        dp[i+1][0]=0.;
        for j in 0..=i {
            dp[i+1][j+1]=dp[i][j+1];
            let tmp=0.9*dp[i][j]+p[i] as f64;
            dp[i+1][j+1].chmax(tmp);
        }
    }
    let mut ans=-1e18;
    for j in 1..=n {
        ans.chmax(dp[n][j]/10./(1.-(0.9_f64).powf(j as f64))-1200./(j as f64).sqrt());
    }
    outputln!(ans);
}

F問題

atcoder.jp
平面走査をほぼ解いたことがなく、なんとなく理解したつもりでいただけだったので手も足も出ませんでした。
解説を読み砕いて理解できました。読めば読むほど当たり前に見えてくるのが悲しい。
最も多くの格子点を覆うの長方形を見つけるという考え方とは逆に、それぞれのりんごを得ることができる範囲を表すの長方形が最も多く重なる格子点を見つけるという考え方をすることがこの問題の肝です。
あとはを順に見ていき、長方形の個数の変更と最大値の候補を求めることが高速にできればよいです。
これはイベントソートをして区間加算と区間最大値の遅延セグ木を用いれば容易にできます。
区間加算や区間変更の遅延セグ木はライブラリ化しました。
atcoder.jp

use ac_library::{LazySegtree, segtree};
#[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,tx:[(usize,usize);n]);
    let mut pq=RevBinaryHeap::<(usize,bool,usize)>::new();
    for &(t,x) in &tx {
        pq.push((t.saturating_sub(d)+1,true,x));
        pq.push((t+1,false,x));
    }
    let mut lst=LazySegtree::<SegmentAffineTransform<segtree::Max<isize>>>::from(vec![0;2*E[5]+1]);
    let mut ans=0;
    for s in 1..=2*E[5] {
        while let Some(&(t,b,x))=pq.peek() {
            if s!=t {
                break;
            }
            pq.pop();
            if b {
                lst.apply_range(x.saturating_sub(w)+1..=x, (1,1));
            } else {
                lst.apply_range(x.saturating_sub(w)+1..=x, (1,-1));
            }
        }
        ans.chmax(lst.all_prod());
    }
    outputln!(ans);
}

G問題

面白そうですが、まだやらないでおきます。
除原理DP、そろそろどういうものなのかくらいは理解しておきたいなぁ…