AtCoder Regular Contest 168 (AからDまで) 復習 - 獅子座じゃない人のブログ

Rustで競プロするのに慣れたりライブラリを整備したりするのも兼ねて、ARC168を解き直します。
コンテスト時はA～Bの2完でした。

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

A問題

atcoder.jp
確証を持ってエスパーできる難易度ですね。
コンテスト時はランレングス圧縮を関数化していなかったので事故りました。

A問題でRustにしては珍しい凡ミスをしてしまった

←WA
AC→ pic.twitter.com/a5gBbgxi8a
— 獅子座じゃない人 / 🎶 / 🔔🐾 / ❇️ / 🀄️🏴‍☠️ (@Not_Leonian) 2023年11月19日

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!(_:usize,s:Chars);
    let mut ans=0;
    for (c,n) in s.rle() {
        if c=='>' {
            ans+=n*(n+1)/2;
        }
    }
    outputln!(ans);
}

B問題

atcoder.jp
エスパーで解くタイプの問題に見えて、NimやGrundy数の性質について理解していれば理詰めで論証できるので大好きな問題です。
自分の解いたAtCoderの問題のなかで一番好きまであります。
まず、 $k\geq\max{A}$ の場合は個数制限がないNimそのものになります。
つまり、この山で個数制限がないNimを行って先手必勝の場合、全ての $k\geq\max A$ で先手必勝となります。すなわち、答えは-1です。
次に、 $k$ の値にかかわらず、石の個数が等しい山が偶数個あれば真似っこ戦略が勝者の最適戦略になるため考慮する必要はありません。
そして、それらを除いて山の個数が0個になった場合、全ての $k$ で後手必勝となります。すなわち、答えは0です。
その他の場合について考えます。
こちらも石の個数が等しい偶数個の山を除いて考えます。
この場合、この山で個数制限がないNimを行うと後手必勝です。 $\bigoplus_i A_i=0$ ともいえます。
そして、 $\bigoplus_i A_i\!\!\!\!\mod(k+1)$ が非ゼロとなる最大の $k\ (\lt\max{A})$ が答えです。
ここで $k=\max{A}-1$ とすると、奇数個の $\max{A}$ のみが0になり、残りの要素は変わりません。
ニム和の性質から、このとき $\bigoplus_i A_i\!\!\!\!\mod(k+1)=\max{A}>0$ となります。すなわち、答えは奇数個ある最大の要素から1を引いたものになります。

Grundy数を求める関数もライブラリに追加しました。
こっちもランレングス圧縮したら実装楽だったじゃねーか！（ABC329の後すぐにライブラリに追加しなかったのは推し活してたからなのでしょうがないですが）
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,mut a:[usize;n]);
    if a.nimber(0)>0 {
        outputln!(-1);
    } else {
        a.sort();
        for &(a,i) in a.rle().iter().rev() {
            if i%2>0 {
                outputln!(a-1);
                return;
            }
        }
        outputln!(0);
    }
}

C問題

atcoder.jp
コンテスト中にはこの問題の本質に全くたどり着けていませんでした。
まず、文字列の順序は考慮する必要がなく、各文字の個数のみに注目すればよいことに気付きませんでした。
そして、アルゴリズムではなく数学と全探索で数え上げる解法も予想だにしていませんでした。

文字列の順序は考慮する必要がないので、まず「 $S$ で $x$ の位置の文字が $T$ で $y$ である個数」 $\mathrm{cnt}[x][y]$ を考えます。
$T$ から $S$ に戻すことを考えると、まず $\mathrm{cnt}[x][y]$ と $\mathrm{cnt}[y][x]$ の少なくとも片方が0になるまで $x$ と $y$ を交換する操作があります。
また、A→B→C→とA→C→B→という巡回置換は2つの互換の積で表されます。上の操作で $\mathrm{cnt}[x][y]$ と $\mathrm{cnt}[y][x]$ の少なくとも片方は0になっていますから、A→B→C→とA→C→B→のどちらかのみしか残りません。
全探索する要素を4つに絞れたので、あとは全探索すればよいです。
$\mathrm{cnt}[x][y]$ がわかれば、それぞれの数え上げは「 $x$ を $\mathrm{cnt}[x][y]$ 個選ぶ組み合わせ×残りの $x$ を $\mathrm{cnt}[x][z]$ 個選ぶ組み合わせ」の積になります。（復習でもここで1時間くらい悩んでしまった、悔しい…）
A→B→C→またはA→C→B→が1つもない場合に重複して数えないように注意する必要があります。

元々二項係数はライブラリに入れていましたが、さらに前計算のコードをスニペットにも入れました。
atcoder.jp

use ac_library::ModInt998244353;
#[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!(n:usize,k:usize,s:Chars);
    let invs=construct_modint_inverses::<ModInt998244353>(max(n,k));
    let facts=construct_modint_facts::<ModInt998244353>(max(n,k));
    let factinvs=construct_modint_fact_inverses::<ModInt998244353>(max(n,k), &invs);
    let ncr=|n:usize,r:usize| facts[n]*factinvs[r]*factinvs[n-r];
    let mut cnt=[0;3];
    for c in s {
        cnt[c.from_uppercase()]+=1;
    }
    let mut ans=ModInt998244353::new(0);
    for a in 0..=k {
        if cnt[0]<a || cnt[1]<a {
            break;
        }
        for b in 0..=k-a {
            if cnt[1]<a+b || cnt[2]<b {
                break;
            }
            for c in 0..=k-a-b {
                if cnt[2]<b+c || cnt[0]<a+c {
                    break;
                }
                for d in 0..=(k-a-b-c)/2 {
                    if cnt[0]<a+c+d || cnt[1]<a+b+d || cnt[2]<b+c+d {
                        break;
                    }
                    let mut tmp=ModInt998244353::new(1);
                    tmp*=ncr(cnt[0], c);
                    tmp*=ncr(cnt[0]-c, a+d);
                    tmp*=ncr(cnt[1], a);
                    tmp*=ncr(cnt[1]-a, b+d);
                    tmp*=ncr(cnt[2], b);
                    tmp*=ncr(cnt[2]-b, c+d);
                    ans+=tmp;
                    if d>0 {
                        let mut tmp=ModInt998244353::new(1);
                        tmp*=ncr(cnt[0], a);
                        tmp*=ncr(cnt[0]-a, c+d);
                        tmp*=ncr(cnt[1], b);
                        tmp*=ncr(cnt[1]-b, a+d);
                        tmp*=ncr(cnt[2], c);
                        tmp*=ncr(cnt[2]-c, b+d);
                        ans+=tmp;
                    }
                }
            }
        }
    }
    outputln!(ans);
}

D問題

atcoder.jp
累積和などで高速化する区間DPだという予想はしていたものの、精進含め区間DPを解いたことがなかったのでDPテーブルも緩和も全くわからず…
操作の性質をしっかりと見抜けていなかった気がします。

操作によって、必ず1つ以上のマスが白から黒に変わります。
ある操作で黒になったマスのうちの1つに注目します。
その操作より前の操作が行われている間ずっとそのマスは白であったというのは明らかですが、これを言い換えると、前の操作はすべて注目しているマスより左の区間か右の区間に包含されているということがいえます。
この性質を活かし、 $\mathrm{DP}[l][r]$ を「区間 $[l,r]$ に包含される区間の操作のみでの操作回数の最大値」で定義します。
すると、 $[l,r]$ に包含されるある操作によって黒にすることができるマス $k\in[l,r]$ について、 $\mathrm{DP}[l][k-1]+\mathrm{DP}[k+1][r]+1$ が $\mathrm{DP}[l][r]$ の候補になります。
あとは、 $[l,r]$ に包含されるある操作によって $k\in[l,r]$ を黒にできるかを高速に判定できればよいです。
2次元累積和等を用いて事前に「区間 $[l,r]$ に包含される区間の操作の個数」 $\mathrm{cnt}[l][r]$ を求めておくと、 $[l,r]$ に包含されるある操作によって $k$ を黒にできることは $\mathrm{cnt}[l][r]>\mathrm{cnt}[l][k-1]+\mathrm{cnt}[k+1][r]$ で表せます。

実装では半開区間を用いました。
C問題でも用いましたが、添字のパターンが同じ配列へのアクセスをクロージャにしてしまうの混乱が生じにくくてよいですね。積極的に使っていきたい。
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,lr:[(Usize1,usize);m]);
    let mut event=vec![vec![0;n+1];n+1];
    for (l,r) in lr {
        event[0][r]+=1;
        event[l+1][r]-=1;
    }
    let cnt=event.construct_2d_prefix_sum();
    let get_cnt=|l:usize,r:usize| cnt[l+1][r+1];
    let mut dp=vec![vec![0;n+1];n+1];
    for i in 1..=n {
        for l in 0..=n-i {
            for k in 0..i {
                if get_cnt(l,l+i)>get_cnt(l,l+k)+get_cnt(l+k+1,l+i) {
                    let tmp=dp[l][l+k]+dp[l+k+1][l+i]+1;
                    dp[l][l+i].chmax(tmp);
                }
            }
        }
    }
    outputln!(dp[0][n]);
}

E問題のAlien DPはまだ自分には早いかなという気がしています。F問題は手も足も出なそう。