EDPC Xの解法というか考察過程が他の人と違ったので、解説記事なるものを書いてみます。
直感に頼ったお気持ち解法なので間違っていたらこっそり教えてください。
問題概要
個のブロックからいくつかを選び、それらを積み重ねてタワーを作ります。
個目のブロックは重さ
、頑丈さ
、価値
であり、
個目のブロックよりも上に載っているブロックの重さの総和が
を超えると耐えきれずこわれてしまいます。
タワーの価値を最大化してください。
解法
載せる順番まで全部試すと到底間に合わないので、ブロックを見る順番を適当にソートしてから貪欲っぽくDPをやらないと無理だろという気持ちになります。
直感に頼ると、頑丈なブロックを下の方に置きたくなります。置きたくなりますよね?ですが単純にの大きい順にソートすると、
みたいなときに破滅します。下から
の順に乗せれば価値は
になりますが、
の大きい順でソートしてから
の順に見るとどちらか片方しか乗せることができません。
そこで、頑丈さの定義を変えてしまうことにします。具体的には、番目のブロックが自分自身の重量
も支えると考えて、
と置いてあげます。こうすると、ある点より上のタワーの頑丈さを、ブロックを置いた後ではなく置く前に決められる(
番目のブロックを使う/使わないに関わらず、それ以降の重量制限が
になると考えることができる)ので、
の大きい順に見ていくことで上手く行くようになります。
順番さえ決めてしまえば、:ソート後の
番目のブロックまで見て、あと残り重さ
まで乗せられるときの価値の最大値 としてナップサックっぽいDPをすればよいです。計算量は
です。
public override void Solve(IOManager io) { var n = io.ReadInt(); var blocks = new (int stiffness, int weight, int value)[n]; for (int i = 0; i < blocks.Length; i++) { var w = io.ReadInt(); var s = io.ReadInt(); var v = io.ReadInt(); blocks[i] = (s + w, w, v); // s_i' = s_i + w_iとおく } blocks.Sort((a, b) => b.CompareTo(a)); const int MaxStiffness = 20000; var dp = new long[n + 1, MaxStiffness + 1]; for (int i = 0; i < blocks.Length; i++) { // s_i', w_i, v_i var (stiffness, weight, value) = blocks[i]; // 本来のs_i var upperStiffness = stiffness - weight; for (int s = 0; s <= MaxStiffness; s++) { // i番目のブロックを採用しない dp[i + 1, s].ChangeMax(dp[i, s]); // i番目のブロックを採用する // i番目より上に載せられるのはs-w_iかs_iのどちらか小さい方 var next = Math.Min(s - weight, upperStiffness); if (next >= 0) { dp[i + 1, next].ChangeMax(dp[i, s] + value); } } } long result = 0; for (int i = 0; i <= MaxStiffness; i++) { result.ChangeMax(dp[n, i]); } io.WriteLine(result); }
不等式を立てて場合分けすることでソートの比較関数を導く解法が主流かと思いますが、こういう考え方もあるよということで書いてみました。
こちらの方が個人的には直感的かな?と思っていますが、いかがでしょうか?