Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【Educational DP-Y Grid 2】使えないパスを減算する

Y - Grid 2

問題

HxWのグリッドに、通れない壁がN個ある。(1,1)から出発して(H,W)にたどり着くパスはいくつあるか?

制約: N=3000, H,W=105

方針

HWの積が1010なので、ふつうの数え上げをするとしんどいです。最初、座圧して場所によって非壁一マスの価値が変わるみたいな話なのかな?と思いましたが、もっとシンプルでした。

壁の数Nが3000であることを利用します。

壁を(i,j)でソートします。こうすると、先頭の壁は(1,1)により近いことになります。

ソートした中で、壁を1,2,3,4,...と番号をつけて、

dp[i] := i番目の壁まで行くことの出来るパス

とすると、これは、壁が全く存在しない通りから、iより前の壁を経由するパスを除去したものとなります。

f:id:akiradeveloper529:20191008201033j:plain

例えばこの例でいうと、dp[C]を計算する時には、(1,1)-A-B-Cというパスや(1,1)-A-Cというパスを除去します。

実装

fn solve() {
    input!{
        H:i64,W:i64,N:usize,
        rc: [(i64,i64);N]
    }
    let modcomb = ModComb::new(1000000, mo as u64);

    let mut p = rc;
    p.push((H,W));
    p.sort();
    let mut dp = vec![ModInt::new(0); N+1];
    dp[0] = ModInt::new(1);
    for i in 0..N+1 {
        let p0 = p[i];
        let mut all: ModInt = (modcomb.nCk((p0.0+p0.1-2) as u64, (p0.0-1) as u64) as i64).into();
        for j in 0..i {
            let p1 = p[j];
            if p1.0 > p0.0 || p1.1 > p0.1 { continue; }
            let x = p0.0-p1.0;
            let y = p0.1-p1.1;
            let comb: ModInt = (modcomb.nCk((x+y) as u64, x as u64) as i64).into();
            all -= dp[j] * comb;
        }
        dp[i] = all;
    }
    println!("{}", dp[N]);
}