AtCoder Grand Contest 065 (AからBまで) 復習

Rustで競プロするのに慣れたりライブラリを整備したりするのも兼ねて、AGC065を解き直します。
コンテスト時はAの1完でした。
水への逆戻りを防ぐとともに、次回水パフォを出しても入水しないレートに上げることができました。

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

A問題

atcoder.jp
distinctの場合については序盤に正しく考察できていましたが、そうでない場合に手間取って、不要な場合分けなどをしてしまいました。

modをとったりその基準をずらしたりして大丈夫です。
結局は、重複しているぶんを除いて減少（modの世界では大きく増加）するように並べるのが最適で、左端と右端については左の条件を満たせるならば同じ数にするのが最適です。それができないならば、左端から右端で減少したぶんだけ解が小さくなるので、左の条件を満たせるような隣接した数について差が小さくとれるものを端にすればよいです。
これは、modをとってソートしてから、最頻値についてその差を最小化すればよいです（自分のコードでは逆にして最大化しています）。答えは、から最頻値の個数を引いたものにをかけ、差を引いたものになります。
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,k:usize,mut a:[usize;n]);
    for i in 0..n {
        a[i]%=k;
    }
    a.sort();
    let mut maxs=Vec::<usize>::new();
    let mut maxcnt=0;
    let mut cur=(k,0);
    for &a in &a {
        if cur.0==a {
            cur.1+=1;
        } else {
            cur=(a,1);
        }
        if maxcnt<cur.1 {
            maxcnt=cur.1;
            maxs=vec![a];
        } else if maxcnt==cur.1 {
            maxs.push(a);
        }
    }
    let maxlen=maxs.len();
    let mut diff=maxs[0]+k-maxs[maxlen-1];
    for i in 0..maxlen-1 {
        diff.chmax(maxs[i+1]-maxs[i]);
    }
    outputln!((n-maxcnt-1)*k+diff);
}

B問題

atcoder.jp
コンテスト中、「逆順に考える」「そのままだとのDPを累積和などで高速化」「を操作するときに、より小さな数との関係は確定させなければならないことを利用する」という風に断片的な解法は思いつけていたのですが、具体的にDPテーブルや緩和を構成することができず…
力不足でした。ただ、解説を見ると納得でき、とても面白い問題だと思いました。

サンプル1のという操作を、という列に置き換えます。この列は、既に操作が終わった数を区切りとした、並んでいるまだ操作していない数の個数を表したものです。
こうすることで、操作を次のように簡潔に表せます。
まず、操作するのは確定していない数のなかで最も左にあるものなので、0でない最も左の項の数を1減らすことになります。
次に、を操作するときに、より小さな数（すわなち既に操作が終わっている数）との関係は確定させなければなりません。したがって、操作によって新たに分割される項は固定されます。
具体的には、左端の添字を0として、未満かつでより左にある数の個数を添字とする項を分割することになります。

そして、この操作を逆順に見ることを考えます。
まず、が個並んでいるものから始まります。そして、未満かつでより左にある数の個数を左の添字とする2つの項を足して1つの項にします。次に、自身より左に0しかない項を選び、その項に1を足します。
そして、回操作した後左にが0個になる場合の数を求めればよいです。
これは、累積和で高速化するDPで計算できます。
未満かつでより左にある数の個数を前計算し、計算するテーブルの添字がそれ以下か超かによって累積和の始まりをずらして計算すればよいです。
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,p:[Usize1;n]);
    let mut ahead=vec![0;n];
    for i in 0..n {
        for j in 0..i {
            if p[j]<p[i] {
                ahead[p[i]]+=1;
            }
        }
    }
    let mut dp=vec![vec![OldMint::new(0);n+2];n+1];
    dp[0][n+1]=OldMint::new(1);
    for i in 0..n {
        let dpsum=dp[i].construct_prefix_sum();
        for j in 0..=ahead[n-1-i] {
            dp[i+1][j]=dpsum.calculate_partial_sum(j, n+2);
        }
        for j in ahead[n-1-i]+1..=n-1-i {
            dp[i+1][j]=dpsum.calculate_partial_sum(j+1, n+2);
        }
    }
    outputln!(dp[n][0]);
}

C問題以降は流石に自分の今の実力では手も足も出なそうなので、やらないでおきます。