yukicoder No.951 【本日限定】1枚頼むともう1枚無料!

典型のはずなのにかなりハマった。
No.951 【本日限定】1枚頼むともう1枚無料! - yukicoder

問題

N 種類のピザがあり、i 番目のピザのコストは P[i] 円、美味しさは D[i] である。各ピザはちょうど1枚だけ売られている。以下の行動を好きな回数繰り返すことができる。

  • ピザを買う。そのピザの値段を P[i] 円としたとき、P[i] 円以下の残っているピザを一つ選び、0 円で買うことができる。

買ったピザの美味しさの和を最大にしたい。支払いを K 円以内にするとき、実現できる美味しさの和の最大値を求めよ。

解法

最適戦略としてどのようなものがありえるかを考察する。買ったピザの値段を高い順に並べたものを X_0, X_1, ..., X_{a - 1} とすると、この中で 0 円にすべきなのは X_1, X_3, ... である。値段の低い順番に見た時、以下のようなルールでピザを選んでいくのと同値である。

  • 「正規の金額でピザを買う」「0 円でピザを買う」「ピザを無視する」の3種類の行動を取ることができる。「0 円でピザを買う」は「0 円にできる権利」を使わないと選べない。最初「0 円にできる権利」を 1 回使うことができる。「0 円にできる権利」を使うと 1 個減り、正規の金額でピザを買うと「0 円にできる権利」は 1 回使える状態に戻る。最終的に「0 円にできる権利」は 1 回使える状態になっていないといけない。(最後の購入は正規の金額でなければならない)

0 円にできる権利はどの地点でも最大 1 回しか残っていない。よって、状態は [現在位置][使った金額][権利の残り回数] の O(NK) 状態である。

登場する典型

  • 最適戦略の形を考える
  • ナップサック DP などの、更新の方向が決まっている DP について、次元を一つ落とす
    • 遷移が DP[i][j] -> DP[i + 1][k] (常に j < k) の形をしている場合、逆からループすることで1次元で済ませることができる。
    • 今回の場合は、(使った金額, 権利の残り回数) の辞書順で考えるとよい

実装上の注意点

  • (P[i], D[i]) のソートを忘れない

提出:
#413247 (Rust, 高速化前)
#413250 (Rust, 高速化後)

(高速化後)

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        n: usize, k: usize,
        pd: [(usize, i64); n],
    }
    let mut pd = pd;
    pd.sort();
    const INF: i64 = 1 << 50;
    let mut dp = vec![[-INF; 2]; k + 1];
    dp[0] = [0, 0];
    // (j, 0) -> (j, 1), (j, 1) -> (j + p, 0) の遷移を一挙にやりたい。
    // (j, l) が大きくなる方向にしか遷移しないため、
    // (j, l) の辞書順の逆に遷移させればよい.
    for i in 0..n {
        let (p, d) = pd[i];
        for j in (0..k + 1).rev() {
            if j + p <= k {
                dp[j + p][0] = max(dp[j + p][0], dp[j][1] + d);
            }
            dp[j][1] = max(dp[j][1], dp[j][0] + d);
        }
    }
    let mut ma = 0;
    for i in 0..k + 1 {
        ma = max(ma, dp[i][0]);
    }
    puts!("{}\n", ma);
}

まとめ

こういう DP 配列を潰す系の高速化は、常識な気もする一方でどこにも書かれていない気がする。誰かまとめてほしい