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

Rustで競プロするのに慣れたりライブラリを整備したりするのも兼ねて、ABC338を解き直します。
コンテスト時はA～Eの5完でした。
温まったとはいえ、Fが解けなかったのがめちゃくちゃ悔しいです。

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

A問題

atcoder.jp
is_uppercase()関数やis_lowercase()関数、あると予想していましたが調べるのが面倒でコンテスト中は愚直に不等式評価しました。
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!(s:Chars);
    for i in 0..s.len() {
        if i==0 {
            if !s[i].is_uppercase() {
                outputln!("No");
                return;
            }
        } else {
            if !s[i].is_lowercase() {
                outputln!("No");
                return;
            }
        }
    }
    outputln!("Yes");
}

正規表現でいいじゃん…
正規表現による一致などはライブラリに入れたほうがいいのではと思いつつ、1行で書けるのでいいのではと放置しています。
atcoder.jp

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

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

    input!(s:String);
    output_yes_or_no(Regex::new(r"^[A-Z][a-z]*$").unwrap().is_match(&s));
}

B問題
atcoder.jp
初期から（普通に標準ライブラリにもありそうな）from_lowercase()関数とto_lowercase()関数は作ってあったのでよかったです。
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!(s:Chars);
    let mut cnts=vec![0;26];
    for c in s {
        cnts[c.from_lowercase()]+=1;
    }
    let mut ans=0;
    for i in 0..26 {
        if cnts[i]>cnts[ans] {
            ans=i;
        }
    }
    outputln!(ans.to_lowercase());
}

C問題

atcoder.jp
やることは片方全探索なんですが、コンテスト中はC問題にしては珍しい制約に見えてちょっと悩みました。

実装について、こういう風に確実に上限がありその上限で問題なく抜けられるループは、ループ回数を考えないほうが楽になる可能性がありそう。
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;n],a:[usize;n],b:[usize;n]);
    let mut ans=0;
    for aans in 0.. {
        let mut valid=true;
        for i in 0..n {
            if a[i]*aans>q[i] {
                valid=false;
                break;
            }
        }
        if !valid {
            break;
        }
        let mut bans=usize::MAX;
        for i in 0..n {
            if b[i]>0 {
                bans.chmin((q[i]-a[i]*aans)/b[i]);
            }
        }
        ans.chmax(aans+bans);
    }
    outputln!(ans);
}

D問題

atcoder.jp
やることはすぐに見えたのですが、imos法が楽ということに気付くまで結構時間を使ってしまいました。

コンテスト中は $X_i$ と $X_{i+1}$ の大小、そして短いほうの距離が $|X_{i+1}-X_i|$ であるかで4通りの場合分けをしましたが、ちゃんと考察をすると場合分けは要らないですね。（ここまで見えてたらimos法ではなく遅延セグ木で実装してたかも）

昨日のD問題のimos法、結局パターンこれだけしかないから場合分け必要ないのか pic.twitter.com/laypXnndTl
— 獅子座じゃない人❇️🔔🎶 (@Not_Leonian) 2024年1月28日

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,x:[Usize1;m]);
    let mut imos=vec![0;n];
    for i in 0..m-1 {
        let n=n as isize;
        let xl=min(x[i], x[i+1]);
        let xr=max(x[i], x[i+1]);
        let d=(xr-xl) as isize;
        imos[0]+=d;
        imos[xl]+=n-d-d;
        imos[xr]-=n-d-d;
    }
    let mut ans=isize::MAX;
    let mut tmp=0;
    for i in 0..n {
        tmp+=imos[i];
        ans.chmin(tmp);
    }
    outputln!(ans);
}

E問題

atcoder.jp
ITF.PCで解けなかった問題そのものですねぇ…stackなのはわかっていましたがどう判定するかでちょっとだけ悩みました。
結局コンテスト中の実装はあまりきれいではなかったですが…

$A_i\lt B_i$ を満たすように交換しておけば、積んでいくstackが空の状態で $b\in B$ が来ることはないというのが実装を楽にするポイントでした。
$B$ の要素ならば対応する $A$ の要素をもち、 $A$ の要素ならば別の適当な値をもつ配列を用意します。
すると、時計回りで順に $A$ の要素がきたらstackに積み、 $B$ の要素がきたら対応する要素がstackの末尾にあるかを確認すればよいです。
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,mut ab:[[Usize1;2];n]);
    let mut pair_a=vec![2*n;2*n];
    for i in 0..n {
        if ab[i][0]>ab[i][1] {
            ab[i].swap(0, 1);
        }
        pair_a[ab[i][1]]=ab[i][0];
    }
    let mut stack=Vec::new();
    for i in 0..2*n {
        if pair_a[i]==2*n {
            stack.push(i);
        } else if stack.pop().unwrap()!=pair_a[i] {
            outputln!("Yes");
            return;
        }
    }
    outputln!("No");
}

F問題

atcoder.jp
解けなかったのは本当に悔しいですが、これが実力と言われればぐうの音も出ません。

まず、普通の巡回セールスマン問題（の戻る必要がないもの）に落とし込めそうとも一瞬思いましたが、その方針を詰めませんでした。
条件を満たす最短のウォークの頂点列から、全ての頂点を1つずつとった場合、辺の距離ではなく最短経路を結合する巡回セールスマン問題（の戻る必要がないもの）に落とし込まれます。ちょっと考えればわかりましたねこれは…

そのうえで、あとは普通にbit DPなのですが、当時疲れてたのかそこでもバグらせまくってましたね…
operate_if_not_max()関数を作ることで、isize::MAXに負の値が足されてINF扱いでなくなってしまうことを防ぐようにしました。
また、負の辺を含むグラフに対してのワーシャル・フロイド法も追加しました。非負の辺のみに対するワーシャル・フロイド法もバグってたので怪我の功名です。
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,uvw:[(Usize1,Usize1,isize);m]);
    let g=IsizeGraph::construct_weighted_directed_graph(n, m, &uvw);
    let d=g.floyd_warshall();
    let mut dp=vec![vec![isize::MAX;n];1<<n];
    for v in 0..n {
        dp[1<<v][v]=0;
    }
    for s in 0..1<<n {
        for v in 0..n {
            if (s>>v)%2>0 {
                for u in 0..n {
                    if (s>>u)%2==0 {
                        let cand=dp[s][v].operate_if_not_max(d[v][u], isize::saturating_add);
                        dp[s+(1<<u)][u].chmin(cand);
                    }
                }
            }
        }
    }
    let ans=*dp[(1<<n)-1].iter().min().unwrap();
    outputif(ans<isize::MAX, ans, "No");
}

G問題
atcoder.jp
明らかに橙diffのなかでは簡単なDPでしたが、細かいところを時間内に詰めるのが難しい問題なんだと思います。

寄与を、右の数値のみの部分、真ん中の数値と*のみの部分、左側の数値と*と+がある部分に分けて考えます。
$j$ についてのループを回し、それぞれの部分についての $f(i,j)$ の総和を更新していくことを考えます。
まず、記号が来た場合は明らかにそれぞれの部分の結果をより左側のものにずらしていけばよいです。
数字の場合の寄与の更新を、一旦総和をとらずに考えます。
右側の部分は10倍して来た数値を足せばよいです。真ん中の部分の寄与は右側の元の全体の数値で割って新たな右側の全体の数値をかければ求まります。左側の部分の寄与は真ん中から右側にかけての元の全体の数値を引いて新たな真ん中から右側にかけての全体の数値を足せば求まります。
では、これらの総和を更新することを考えます。右側の部分について10倍はそのままでよく、右側の長さを来た数値にかけて足せば更新できます。真ん中の部分はそのまま割ってかければよいです。左側の部分は、左側の長さだけかけたうえで引き算と足し算をすればよいです。

まあこれだけなんですが、0除算にならないように気をつけたり、真ん中から右側にかけての全体の初期値を1にしたいが差分をとるときは0であってほしかったり、と細かい部分が面倒ではあります。
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!(s:Chars);
    let n=s.len();
    let mut ans=Mint::new(0);
    let mut plus_sum=Mint::new(0);
    let mut ast_sum=Mint::new(0);
    let mut num_sum=Mint::new(0);
    let mut cur_ast=Mint::new(0);
    let mut cur_num=Mint::new(0);
    let mut after_plus=true;
    let mut after_ast=false;
    let mut plus_nums_cnt=Mint::new(0);
    let mut ast_nums_cnt=Mint::new(0);
    let mut nums_cnt=Mint::new(0);
    for i in 0..n {
        let c=s[i];
        if c=='+' {
            plus_sum+=ast_sum+num_sum;
            ast_sum=Mint::new(0);
            num_sum=Mint::new(0);
            cur_ast=Mint::new(0);
            cur_num=Mint::new(0);
            ast_nums_cnt=Mint::new(0);
            nums_cnt=Mint::new(0);
            after_plus=true;
        } else if c=='*' {
            ast_sum+=num_sum;
            num_sum=Mint::new(0);
            cur_num=Mint::new(0);
            nums_cnt=Mint::new(0);
            after_ast=true;
        } else {
            let n=c.from_fig();
            plus_nums_cnt+=1;
            ast_nums_cnt+=1;
            nums_cnt+=1;
            plus_sum-=(plus_nums_cnt-ast_nums_cnt)*cur_ast;
            if after_plus {
                cur_ast=Mint::new(1);
            } else if !after_ast {
                cur_ast/=cur_num;
                ast_sum/=cur_num;
            }
            cur_num*=10;
            cur_num+=n;
            num_sum*=10;
            num_sum+=nums_cnt*n;
            after_plus=false;
            after_ast=false;
            cur_ast*=cur_num;
            ast_sum*=cur_num;
            plus_sum+=(plus_nums_cnt-ast_nums_cnt)*cur_ast;
            ans+=plus_sum+ast_sum+num_sum;
        }
    }
    outputln!(ans);
}