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 配列を潰す系の高速化は、常識な気もする一方でどこにも書かれていない気がする。誰かまとめてほしい