InTheDayDream

AWC0134D - お買い物プラン の分割統治解法

Published on 2026-08-14
Last Modified 2026-08-14

Table Of Contents

問題概要

問題リンク

$N$個の商品がある。$i$番目の商品は価格$H _ i$、満足度$V _ i$である。 $Q$個のクエリを処理せよ。

$i$番目のクエリは$1 \leq L _ i \leq R _ i \leq N$と$X _ i$が与えられるので、$L _ i$番目から$R _ i$番目の$R _ i - L _ i + 1$個の商品をそれぞれ高々1つまで買えるとき、予算$X _ i$円以下で実現できる最大の満足度を求めよ。

商品の価格と予算は$M$円以下であることが保証される。

想定解法

要するに指定区間に入るアイテムたちだけで01ナップサック問題を解けばよい。 $\mathrm{dp}[i][j]$を先頭$i$個の商品を買うか決めて、値段$j$円で実現できる最大満足度とすると、クエリあたり$O(NM)$時間かかる。 よって普通にやると$O(QNM)$になるが、流石に計算量が厳しい。

また、ナップサックは数え上げ等と異なり、「戻す」操作が出来ないことを考えると、何らかの方法で完成したナップサックテーブルから計算するというのも考えにくい。なので、各区間に対して問題を解くのではなく、複数クエリをいっぺんに捌く方法を取りそうな気配がする。

そこで、$L _ i$が同じクエリたちを一括で処理してしまうことを考える。 要するに、どのアイテムからスタートするかだけ全部見て、$N$回ナップサックdpを行うということだ。 こうすればナップサックdpの実行回数を$Q$回から$N$回に減らせる。 クエリ処理の際は左端が一致する回のナップサックdpテーブルで、右端も一致する場所を見に行けば良い。 事前に$O(NM)$時間かけて上方向にchmaxしておけばクエリは$O(1)$時間で答えられるため、$O(N^2 M + Q)$時間になる。

実装例

少々わかりにくいかもしれないが、53-58行目のwhileで左端が一致するクエリを全て処理している。

分割統治解法

分割統治を用いて$O(MQ + NM\log N + Q\log N)$時間で解く。 細かい$\log$は消せる気がするが、各クエリ$O(M)$時間が支配的なためほとんど意味はないと思われる。

さて、まずはある種の動的計画法がsegtreeで処理できることを見ておこう。 次の問題を考える。

長さ$N$のa、bから成る文字列$S$がある。 $S$の$[l, r)$のなかで、部分列abは何通り作れるか？

普通のdpをするなら、次のような形になるだろう。

$\mathrm{dp}[i][j] = \text{先頭$i$文字からabの先頭$j$文字を作る場合の数}$

これを区間クエリに対応させるために、「ある区間に対するdp値」のようなものを考えてみる。

$\mathrm{dp}[l][r][j] = \text{$[l, r)$の文字を使って、abの先頭$j$文字を作る場合の数}$

一見良さそうだが、これでは2つのdpテーブルを意味を保ったままマージすることができない。 例えば$[l, m)$のテーブルと$[m, r)$のテーブルがあったとき、左側でaまで作り、右側でbを作る場合をテーブルから計算できない。そこで、左側の値の情報も含めてしまい、次のようにする。

$\mathrm{dp}[l][r][j][k] = \text{$[l, r)$の文字を使って、abの先頭$j$文字作った状態から先頭$k$文字作った状態に至る場合の数}$

これで具体的なマージが可能になる。マージは一つの$(j, k)$に対して以下の式で表され、合計$3^3$回の計算で行うことができる。（始点、終点で9通り、区間を跨ぐときに何文字目まで考えるかで3通り。不可能な状態も含めている。）

$$ dp[l][r][j][k] = \sum _ {0 \leq t < 3} dp[l][m][j][t] \cdot dp[m][r][t][k] $$

segtreeのように各ノードが区間を表す高さ$O(\log N)$の二分木を作ると、マージのコストを$c$として、任意の区間に対する答えを$O(c \log N)$時間で答えられる。

より詳しい問題例は yukicoder no2554 を参照してほしい。

さて、ナップサックdpもこれと同様に区間のdpテーブルを考えることで区間クエリに答えることができる。

$\mathrm{dp}[l][r][j] = \text{$[l, r)$のアイテムから$j$円使って得られる最大満足度}$

としたとき、テーブルのマージは1つの金額に対して次式により$O(M)$時間になるため、テーブル全体のマージはこれの$O(M)$回分である$O(M^2)$時間で可能なため、クエリあたり$O(M^2 \log N + M)$時間になる。よって合計$O(QM^2 \log N + QM)$時間である。

$$ dp[l][r][x] = \max_{0 \le p \le x} \left(dp[l][m][p] + dp[m][r][x-p] \right) $$

しかし、これでは実行時間に間に合わない。

ここで、ナップサックdpの特徴を用いる。 ナップサックdpはテーブルのマージには$O(M^2)$時間かかるが、1つのアイテムの追加には$O(M)$時間しかかからないという特徴がある。（これは通常のdpのアイテム追加処理と同様） そこで、テーブル同士をマージするのではなく、何とか点追加のみでテーブル更新を行えれば良さそうだ。

分割統治法

ここで分割統治法を導入する。 「分割統治」という語がさす範囲は広大だが、ここでは区間クエリに対するある種の分割統治に絞って話を進める。 今クエリ区間が$[l, r)$に入るものに答える関数$f$を設計しているとする。 このとき、クエリ区間は次の3つに分類される。

区間の中点$m = (l + r) / 2$として

  1. $m - 1$と$m$の間を跨ぐもの（$L _ i < m < R _ i$）
  2. 跨がず、左にあるもの（$R _ i \leq m$）
  3. 跨がず、右にあるもの（$m \leq L _ i$）

1のものだけ処理して、他のクエリは$f(l, m)$と$f(m, r)$に任せることにすると、処理したい1の区間は、

  1. $m - 1, m - 2, \dots$と左方向へアイテムを追加して作ったdp
  2. $m, m + 1, \dots$と右方向へアイテムを追加して作ったdp

の2つの状態から計算できそうなことがわかる。 そこで、次の2つのdpテーブルを構築する。

  1. $[l, m)$のアイテムを$m$側から使って作ったdpテーブル
  2. $[m, r)$のアイテムを$m$側から使って作ったdpテーブル

よく見ると、この2つのテーブルは「1つのアイテムの追加」を繰り返すことで作られていることがわかる。 よって、マージの$O(M^2)$を巧妙に回避できており、全体$O((r - l)M)$時間で構築できる。

抽象的な議論が続いていたが、左側のdpテーブル構築の具体的なコードは次のような感じになる。

auto ldp = new long[][](m - l + 1, M + 1);
// ldp: [l, m)のアイテム

// 初期化
foreach (d; ldp) {
    d[] = -long.max;
}

ldp[0][0] = 0;
foreach (i; 0 .. m - l) {
    foreach (j; 0 .. M + 1) {
        if (ldp[i][j] == -long.max) {
            continue;
        }

        ldp[i + 1][j] = max(ldp[i + 1][j], ldp[i][j]);
        if (j + H[m - i - 1] <= M) {
            ldp[i + 1][j + H[m - i - 1]] = max(ldp[i + 1][j + H[m - i - 1]], ldp[i][j] + V[m - i - 1]);
        }
    }
}

クエリにこたえる際はテーブルのマージと異なり、「左側で$p$円使って、右側で$X _ i - p$円使う」という$X _ i$通りのうち最も良いものを採用すればよいだけなので、各クエリ$O(M)$時間で答えられる。 コードは次のようになる。

// 担当するクエリそれぞれをO(M)時間かけて解く
foreach (qi; mqs) {
    auto lv = ldp[m - L[qi]].dup;
    const rv = rdp[R[qi] - m];

    // 「ちょうどi円」から「i円以下での最大満足度」へ変換
    foreach (i; 0 .. M) {
        lv[i + 1] = max(lv[i], lv[i + 1]);
    }

    long ret = -long.max;
    // X[qi]通りの候補を探索
    foreach (i; 0 .. X[qi] + 1) {
        ret = max(ret, rv[i] + lv[X[qi] - i]);
    }
    ans[qi] = ret;
}

分割統治で現れる区間はsegtreeで現れるノードと同様の高さ$\log N$の二分木状になっており、各層の区間は互いに共通部分を持たず、区間長の総和が$N$以下という構造をしている。 これらすべてに$区間長 \times M$のdpを行うので、dpテーブルの総計算コストは

$$ NM + 2 \cdot \frac{N}{2}M + 4 \cdot \frac{N}{4}M \cdots = NM + NM + NM + \cdots = O(NM\log N) $$

となり、$O(NM\log N)$である。

これにクエリ解答の時間$O(QM)$が加わり、最後に「分割統治のどの時点でクエリを担当するか」も再帰的に行っているため、その分の時間$O(Q \log N)$も加わる。（具体的なやり方は実装例を参照してください。）

以上により、合計$O(NM \log N + QM + Q \log N)$時間で問題を解くことができた。

実装例

216ms 26324KiB 

import std;

void main () {
    int N, M, Q;
    readln.read(N, M, Q);
    auto H = new int[](N);
    auto V = new int[](N);
    foreach (i; 0 .. N) {
        readln.read(H[i], V[i]);
    }
    auto L = new int[](Q);
    auto R = new int[](Q);
    auto X = new int[](Q);
    foreach (i; 0 .. Q) {
        readln.read(L[i], R[i], X[i]);
        L[i]--;
    }

    auto ans = new long[](Q);

    void f (int l, int r, int[] qs) {
        if (r - l == 1) {
            foreach (qi; qs) {
                if (H[l] <= X[qi]) {
                    ans[qi] = V[l];
                }
                else {
                    ans[qi] = 0;
                }
            }
            return;
        }

        int m = (l + r) / 2;
        int[] lqs, rqs, mqs;
        foreach (qi; qs) {
            if (R[qi] <= m) {
                lqs ~= qi;
            }
            else if (m <= L[qi]) {
                rqs ~= qi;
            }
            else {
                mqs ~= qi;
            }
        }

        // 1 < r - lであることに注意
        f(l, m, lqs);
        f(m, r, rqs);

        auto ldp = new long[][](m - l + 1, M + 1);
        auto rdp = new long[][](r - m + 1, M + 1);
        // ldp: [l, m)のアイテム
        // rdp: [m, r)のアイテム

        foreach (d; ldp) {
            d[] = -long.max;
        }
        foreach (d; rdp) {
            d[] = -long.max;
        }

        ldp[0][0] = 0;
        foreach (i; 0 .. m - l) {
            foreach (j; 0 .. M + 1) {
                if (ldp[i][j] == -long.max) {
                    continue;
                }

                ldp[i + 1][j] = max(ldp[i + 1][j], ldp[i][j]);
                if (j + H[m - i - 1] <= M) {
                    ldp[i + 1][j + H[m - i - 1]] = max(ldp[i + 1][j + H[m - i - 1]], ldp[i][j] + V[m - i - 1]);
                }
            }
        }

        rdp[0][0] = 0;
        foreach (i; 0 .. r - m) {
            foreach (j; 0 .. M + 1) {
                if (rdp[i][j] == -long.max) {
                    continue;
                }

                rdp[i + 1][j] = max(rdp[i + 1][j], rdp[i][j]);
                if (j + H[m + i] <= M) {
                    rdp[i + 1][j + H[m + i]] = max(rdp[i + 1][j + H[m + i]], rdp[i][j] + V[m + i]);
                }
            }
        }

        foreach (qi; mqs) {
            auto lv = ldp[m - L[qi]].dup;
            const rv = rdp[R[qi] - m];

            foreach (i; 0 .. M) {
                lv[i + 1] = max(lv[i], lv[i + 1]);
            }

            long ret = -long.max;
            foreach (i; 0 .. X[qi] + 1) {
                ret = max(ret, rv[i] + lv[X[qi] - i]);
            }
            ans[qi] = ret;
        }
    }

    auto qs = iota(Q).array;
    f(0, N, qs);

    writefln("%(%s\n%)", ans);
}

void read (T...) (string S, ref T args) {
    import std.conv : to;
    import std.array : split;
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}

余談

問題Eも面白い話題があるが、それはまたの機会に紹介しようと思う。

Tags for this post: 競技プログラミング 一問解説

Other posts tagged by "競技プログラミング"

more ...

Other posts tagged by "一問解説"

more ...
Power by Hugo / Theme simplog by michimani