TERRYのブログ

最近は競技プログラミングにお熱。

Sponsored Link

EDPC X - Tower 解説

EDPC Xの解法というか考察過程が他の人と違ったので、解説記事なるものを書いてみます。

直感に頼ったお気持ち解法なので間違っていたらこっそり教えてください。

問題概要

N個のブロックからいくつかを選び、それらを積み重ねてタワーを作ります。

i個目のブロックは重さw_i、頑丈さs_i、価値v_iであり、i個目のブロックよりも上に載っているブロックの重さの総和がs_iを超えると耐えきれずこわれてしまいます。

タワーの価値を最大化してください。

atcoder.jp

解法

載せる順番まで全部試すと到底間に合わないので、ブロックを見る順番を適当にソートしてから貪欲っぽくDPをやらないと無理だろという気持ちになります。

直感に頼ると、頑丈なブロックを下の方に置きたくなります。置きたくなりますよね?ですが単純にs_iの大きい順にソートすると、(w_1, s_1, v_1)=(1, 2, 1),(w_2, s_2, v_2)=(100, 1, 1)みたいなときに破滅します。下から2\rightarrow1の順に乗せれば価値は2になりますが、s_iの大きい順でソートしてから1\rightarrow2の順に見るとどちらか片方しか乗せることができません。

そこで、頑丈さの定義を変えてしまうことにします。具体的には、i番目のブロックが自分自身の重量w_iも支えると考えて、s_i'=s_i+w_iと置いてあげます。こうすると、ある点より上のタワーの頑丈さを、ブロックを置いた後ではなく置く前に決められるi番目のブロックを使う/使わないに関わらず、それ以降の重量制限がs_i'になると考えることができる)ので、s_i'の大きい順に見ていくことで上手く行くようになります。

順番さえ決めてしまえば、dp[i][j]:ソート後のi番目のブロックまで見て、あと残り重さjまで乗せられるときの価値の最大値 としてナップサックっぽいDPをすればよいです。計算量はO(N(\log N+\max s_i'))です。

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);
}

不等式を立てて場合分けすることでソートの比較関数を導く解法が主流かと思いますが、こういう考え方もあるよということで書いてみました。

こちらの方が個人的には直感的かな?と思っていますが、いかがでしょうか?