Rustコトハジメ

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

【Educational DP-X Tower】ブロックを交換可能とはどういうことか考える

教育DPの後半は自力AC出来ないものが多かったですが、これはコンビニに行く途中にたまたま閃いて絶叫しました。

X - Tower

問題

ブロックがN個あり、ブロックiの重さはwi, 丈夫さはsi, 価値はviです。

ブロックは、その上に積んであるブロックの重さがsi以下になるようにしか詰めません。

ブロックは全部使わなくても良いとして、価値合計の最大値を求めよ。

制約: N=103, wi,si=104

方針

ブロックになんらかの順序づけをして、頭から使っていくDP(dp[w] = v)に帰着させたいです。

f:id:akiradeveloper529:20191008191736j:plain

何らかの詰みが出来たあと、どこかのブロックと一番下のブロックが交換可能であるというのは、sj-si > wi - wjの時です。(重さの増加分より、丈夫さの増加分が多ければよい)

つまり、これが起こらなければ、どのタイミングでもブロックは交換する必要がなくなり、先にいった頭から使っていくふつうのナップザックDPに帰着出来ます。

DPテーブルは、si,wiの上限が104なことから、重さの上限は、一番のブロックがsi=104,wi=104の時とわかり、TLEとMLEを避けることが出来ます。

実装

fn solve() {
    input!{
        N:usize,
        wsv: [(usize,usize,i64);N]
    }

    let mut wsv = wsv;
    wsv.sort_by_key(|&x| x.0+x.1);
    
    // dp[i][w]
    let mut W_MAX = 10000 + 10000; // 最後のやつがs=10000で、その上までが合計10000
    let mut dp = vec![vec![None; W_MAX+1]; N+1];
    dp[0][0] = Some(0 as i64);
    for i in 0..N {
        let (wi,si,vi) = wsv[i];
        for w in 0..W_MAX+1 {
            dp[i+1][w] = dp[i][w];
        }
        for w in 0..W_MAX {
            if dp[i][w].is_none() { continue; }
            let v = dp[i][w].unwrap();
            if si >= w && w+wi < W_MAX+1 {
                let old = dp[i][w+wi].unwrap_or(0);
                dp[i+1][w+wi] = Some(max(old, v+vi));
            }
        }
    }

    let mut maxv=0;
    for w in 0..W_MAX+1 {
        maxv=max(maxv,dp[N][w].unwrap_or(0));
    }

    println!("{}",maxv);
}

考察

こういう問題は、2つのものの関係に着目することが切り口なことが多いと思います。まずはじめに、「ふつうのナップザックに帰着させたい」と強く思うことが鍵でした。