AtCoder Regular Contest 170 (ARC170) (AからEまで) 復習

Rustで競プロするのに慣れたりライブラリを整備したりするのも兼ねて、ARC170を解き直します。
コンテスト時はA～Bの2完でした。
2完した時点で既にac-predictorが水パフォを示していたので必死にC問題を解こうとしましたが解けず…
Aが遅かったのでしょうがないですね。

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

A問題

atcoder.jp
こういう問題本当に苦手です…とはいえ44分+3ペナは普通に遅いので反省。

まず最小回数を求めるのではなく、とできる条件を考えたほうがよかったと思います。
これは、明らかに「全てのBからAに変えたい部分の右に、最終的にBとなる部分がある」かつ「全てのAからBに変えたい部分の左に、最終的にAとなる部分がある」を満たすことです。
満たさないものを弾いたうえで、なるべくAからBに変えたい部分とBからAに変えたい部分は同時に操作したいです。操作できる組の個数は括弧列の要領でstackを持ちながら数えればよいです。そして、今試しているものは一致できることがわかっているので、組にならなかったものの個数を足したものが最小の操作回数となります。

また、こういう問題は考察に悩むくらいならランダムテストを書いたほうがよいということを学びました。
今回は明らかに同一のに対して複数回操作をするのが無駄なので、順列全探索で楽にランダムテストを書くことができます。
そして、デバッグビルドであってもくらいなら100ms程度で全て確認してくれます。
これで提出デバッグを防ぐことができます。
atcoder.jp

#[allow(unused_attributes)] #[macro_use] #[allow(unused_imports)] use not_leonian_ac_lib::*;
use proconio::marker::Chars;
use superslice::Ext;

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

    input!(n:usize,s:Chars,t:Chars);
    let ans=solve(n, &s, &t);
    outputln!(ans);

    #[cfg(debug_assertions)]
    for i in 2..5 {
        for j in 0..1<<i {
            let mut s=Vec::new();
            for jj in 0..i {
                if (j>>jj)%2==0 {
                    s.push('A');
                } else {
                    s.push('B');
                }
            }
            for k in 0..1<<i {
                let mut t=Vec::new();
                for kk in 0..i {
                    if (k>>kk)%2==0 {
                        t.push('A');
                    } else {
                        t.push('B');
                    }
                }
                assert_eq!(solve(i, &s, &t), test(i, &s, &t));
            }
        }
    }
}

fn solve(n:usize,s:&Vec<char>,t:&Vec<char>) -> isize {
    let mut exists_a=false;
    for i in 0..n {
        if t[i]=='A' {
            exists_a=true;
        }
        if !exists_a && s[i]=='A' && t[i]=='B' {
            return -1;
        }
    }
    let mut exists_b=false;
    for i in (0..n).rev() {
        if t[i]=='B' {
            exists_b=true;
        }
        if !exists_b && s[i]=='B' && t[i]=='A' {
            return -1;
        }
    }
    let mut ans=0;
    let mut stack=Vec::new();
    for i in 0..n {
        if s[i]=='B' && t[i]=='A' {
            stack.push(i);
        }
        if s[i]=='A' && t[i]=='B' {
            if let Some(_)=stack.pop() {}
            ans+=1;
        }
    }
    ans+=stack.len();
    ans as isize
}

fn test(n:usize,s:&Vec<char>,t:&Vec<char>) -> isize {
    let mut p=Vec::new();
    if s==t {
        return 0;
    }
    for i in 0..n {
        for j in i+1..n {
            p.push((i,j));
        }
    }
    let mut ans=usize::MAX;
    do_while!(p.next_permutation(),{
        let mut ss=s.clone();
        for i in 0..p.len() {
            ss[p[i].0]='A';
            ss[p[i].1]='B';
            if ss==*t {
                ans.chmin(i+1);
                break;
            }
        }
    });
    if ans<usize::MAX {
        ans as isize
    } else {
        -1
    }
}

B問題

atcoder.jp
そんなに遅くないスピードで解けたのですが、Aの遅さは流石に巻き返せませんでした。

公式解説と異なる方法ですが、悪くない方法だと思います。
事前にsetのベクタでそれぞれを管理しておきます。
まず、を固定します。等差数列を全探索すると、setを用いてかその右の最も左のの位置がわかり、その位置より右の最も左のの位置がわかり、その位置より右の最も左のの位置がわかります。これがに対する、条件を満たすの最小値となり、それ以上のは全て条件を満たします。
よって、そのような区間の個数の総和をとればよいです。

時間計算量のオーダーはを、等差数列の項数をとして、の個数が、等差数列の個数が、を見つける時間計算量がであることより、となるはずです。空間計算量をからにすれば容易に時間計算量をに落とせるため、公式解説と遜色ない計算量になっていると思います。
atcoder.jp

use std::collections::BTreeSet;

#[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,a:[Usize1;n]);
    let mut ans=0usize;
    let mut ss=vec![BTreeSet::new();10];
    for i in 0..n {
        ss[a[i]].insert(i);
    }
    for l in 0..n {
        let mut r=n;
        for d in 1..=4 {
            for i in 0..10-2*d {
                let j=i+d;
                let k=j+d;
                if let Some(&ip)=ss[i].range(l..).next() {
                    if let Some(&jp)=ss[j].range(ip+1..).next() {
                        if let Some(&kp)=ss[k].range(jp+1..).next() {
                            r.chmin(kp);
                        }
                    }
                }
            }
        }
        for i in 0..10 {
            if let Some(&ip)=ss[i].range(l..).next() {
                if let Some(&jp)=ss[i].range(ip+1..).next() {
                    if let Some(&kp)=ss[i].range(jp+1..).next() {
                        r.chmin(kp);
                    }
                }
            }
        }
        for d in 1..=4 {
            for k in 0..10-2*d {
                let j=k+d;
                let i=j+d;
                if let Some(&ip)=ss[i].range(l..).next() {
                    if let Some(&jp)=ss[j].range(ip+1..).next() {
                        if let Some(&kp)=ss[k].range(jp+1..).next() {
                            r.chmin(kp);
                        }
                    }
                }
            }
        }
        ans+=n-r;
    }
    outputln!(ans);
}

C問題

atcoder.jp
コンテスト中惜しいところまでいったと思っていたんですが、改めて考えると惜しくなかったです…
mexで種類数に注目するの、確かにだいぶ前に見たかもなぁ…

mexではなく種類数をDPテーブルでもつことで2次元DPになります。
の場合、元から全種類埋まっている場合を除いては一意に定まり、種類数は1増えます。
一方、で種類数がの場合、元からある個を選べば種類数は増えません。また、残りのうちmexとなる1個を除いた個を選べば種類数は1増えます。
これに気付くことができれば、あとは単純な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,m:usize,s:[usize;n]);
    let max=min(n, m+1);
    let mut dp=vec![vec![Mint::new(0);max+1];n+1];
    dp[0][0]+=1;
    for i in 0..n {
        for j in 0..=max {
            if s[i]==1 {
                if j<max {
                    dp[i+1][j+1]=dp[i+1][j+1]+dp[i][j];
                }
            } else {
                dp[i+1][j]=dp[i+1][j]+dp[i][j]*j;
                if j<max {
                    dp[i+1][j+1]=dp[i+1][j+1]+dp[i][j]*(m-j);
                }
            }
        }
    }
    outputln!(dp[n].sum());
}

D問題

atcoder.jp
やることは丁寧な言い換えなのですが、upsolve中にWAを連発してしまいました。
こういう問題はむしろ本番のように集中しているときのほうが解けるかもしれませんね。

Bobが勝つということを言い換えていきます。

以降、とします。
について、ならばなので、以下の言い換えが成立します。

また、はと言い換えられます。
ここで、が成立するならば、も成立します。
これらを合わせると、Bobが勝つということはさらに言い換えられます。

最後に、の性質や不等式の変形を使ってさらに言い換えると以下のようになります。

前者は、ソートしたときにと隣接するの要素について見ることで容易に判定できます。
後者は、各に最も近いの要素および次に近いの要素などをもっておき、を（多重）集合で管理することで判定できます。
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!(t:usize);
    for _ in 0..t {
        input!(n:usize,mut a:[usize;n],mut b:[usize;n]);
        a.sort();
        b.sort();
        let mut bob=true;
        let mut badiffs=vec![Vec::new();n];
        let mut minbidx=vec![Vec::new();n];
        let mut bminmset=MultiSet::new();
        for i in 0..n {
            let j=usize_binary_search(n, false, |mid| a[mid]>=b[i]);
            if j<n {
                badiffs[i].push((a[j]-b[i],j));
            }
            if j+1<n {
                badiffs[i].push((a[j+1]-b[i],j+1));
            }
            if j>0 {
                badiffs[i].push((b[i]-a[j-1],j-1));
            }
            if j>1 {
                badiffs[i].push((b[i]-a[j-2],j-2));
            }
            badiffs[i].sort();
            while badiffs[i].len()>2 {
                badiffs[i].pop();
            }
            minbidx[badiffs[i][0].1].push(i);
            bminmset.insert_one(badiffs[i][0].0);
        }
        for i in 0..n {
            if a[i]>=b[0] {
                let mut min=usize::MAX;
                if i>0 {
                    min.chmin(a[i]-a[i-1]);
                }
                if i<n-1 {
                    min.chmin(a[i+1]-a[i]);
                }
                if min>=b[0] {
                    continue;
                }
            }
            for &idx in &minbidx[i] {
                bminmset.remove_one(badiffs[idx][0].0);
                if badiffs[idx].len()>1 {
                    bminmset.insert_one(badiffs[idx][1].0);
                }
            }
            if *bminmset.last_key_value().unwrap().0<a[i] {
                bob=false;
                break;
            }
            for &idx in &minbidx[i] {
                if badiffs[idx].len()>1 {
                    bminmset.remove_one(badiffs[idx][1].0);
                }
                bminmset.insert_one(badiffs[idx][0].0);
            }
        }
        outputif(bob, "Bob", "Alice");
    }
}

E問題

Dまでのupsolveで結構日数を使ってしまったことと、自分がまともに闘えるレベル帯の問題ではないことから、Berlekamp-MasseyアルゴリズムとBostan-Moriアルゴリズムの練習のみします。

まず、についての答えの列が線形漸化式になることを願います。そして、漸化式中の項数が多くないことも願います。（この問題で線形漸化式であると願うのは神の一手すぎる）
そのうえで、くらいまではビット全探索とVecDequeを用いた愚直なシミュレーションでも答えを全て出すことができます。
Berlekamp-MasseyアルゴリズムとBostan-Moriアルゴリズムを用いると、シミュレーションで出した答えから問題の答えを高速に求めることができます。えぇ…

一応、Berlekamp-MasseyアルゴリズムとBostan-Moriアルゴリズムはライブラリに追加しておきました。
atcoder.jp

use std::collections::VecDeque;

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

const MAX:usize=14;

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

    let mut prefix=vec![vec![Mint::new(0);MAX];100];
    for p in 1..100 {
        let prob=Mint::new(p)/100;
        for n in 3..MAX+3 {
            for i in 0..(1<<n) as usize {
                let mut deque=VecDeque::from([(0,0)]);
                let mut seen=vec![false;n];
                let mut e=Mint::new(0);
                let mut cnt=0;
                let mut seen_cnt=0;
                while let Some((x,d))=deque.pop_front() {
                    if !seen[x] {
                        seen[x]=true;
                        e+=d;
                        seen_cnt+=1;
                        if !seen[(x+1)%n] {
                            if (i>>cnt)%2>0 {
                                deque.push_front(((x+1)%n,d+1));
                            } else {
                                deque.push_back(((x+1)%n,d+1));
                            }
                            cnt+=1;
                        }
                        if !seen[(x+n-1)%n] {
                            if (i>>cnt)%2>0 {
                                deque.push_front(((x+n-1)%n,d+1));
                            } else {
                                deque.push_back(((x+n-1)%n,d+1));
                            }
                            cnt+=1;
                        }
                    }
                    if seen_cnt==n {
                        break;
                    }
                }
                prefix[p][n-3]+=e*prob.pow(i.count_ones() as u64)*(Mint::new(1)-prob).pow(n as u64-i.count_ones() as u64);
            }
        }
    }
    let bm=vec_range(0, 100, |i| prefix[i].berlekamp_massey());
    input!(t:usize);
    for _ in 0..t {
        input!(n:usize,p:usize);
        outputln!(prefix[p].calculate_nth_term(n-3, &bm[p]));
    }
}

流石にF問題はやめておきます。