概要

この問題は、全長 \(L\) の廊下に、いくつかの広告パネル（幅 \(w_i\), 価値 \(b_i\)）を重ならないように配置し、空きスロットが連続して \(K\) 個以上並ばないようにする（＝空きスロットの連続幅をすべて \(K-1\) 以下にする）という制約のもとで、得られる価値の合計を最大化する問題です。

条件を満たす配置が可能かどうかを判定し、可能な場合はその最大価値を求めます。

---

考察

1. 防災規定の条件を数式で整理する

選んだ広告パネルの個数を \(j\) 個とします。 \(j\) 個のパネルを廊下に配置したとき、パネルとパネルの間、および両端の空きスペース（空き区間）は全部で \(j + 1\) 箇所 存在します。

防災規定を満たすためには、これら \(j + 1\) 箇所の空き区間の長さがすべて \(K - 1\) 以下でなければなりません。 したがって、空きスロットの総数の最大値は、すべての空き区間が最大の長さ \(K - 1\) であるときの \((j + 1) \times (K - 1)\) となります。

選んだ \(j\) 個のパネルの幅の合計を \(w\) とすると、実際の空きスロットの総数は \(L - w\) です。 したがって、防災規定を満たすように配置できるための必要十分条件は、以下のようになります。 $\(L - w \le (j + 1) \times (K - 1)\)$

これを \(w\) について整理すると、以下の不等式が得られます。 $\(w \ge L - (j + 1) \times (K - 1)\)$

また、パネルが廊下からはみ出てはならないため、当然 \(w \le L\) も満たす必要があります。

2. ナップサック問題への帰着

上記の考察より、この問題は以下のように言い換えることができます。

\(N\) 個のパネルから \(j\) 個を選び、それらの幅の合計を \(w\) としたとき、 $\(L - (j + 1) \times (K - 1) \le w \le L\)$ を満たすような選び方のうち、価値の総和の最大値を求めよ。

これは、「選んだ個数 \(j\)」と「幅の総和 \(w\)」の2つの状態を持つ、個数制限付きのナップサック問題（動的計画法） として解くことができます。

---

アルゴリズム

動的計画法（DP）の設計

DPテーブルの定義: dp[j][w] : パネルを \(j\) 枚選び、幅の合計がちょうど \(w\) であるときの、集客効果（価値）の最大値（到達不可能な状態は -1）。

初期状態: - dp[0][0] = 0 - それ以外の要素はすべて -1

遷移: 各パネル \(i\) （\(1 \le i \le N\)、幅 \(w_i\)、価値 \(b_i\)）について、DPテーブルを更新します。 同じパネルを2回以上選ばないようにするため、選ぶ個数 \(j\) のループは 逆順（大きい方から小さい方へ） に回します。

dp[j][w] が有効な値（\(-1\) 以外）であるとき、このパネルを選ぶことで以下のように遷移します。 $\(\text{dp}[j + 1][w + w_i] = \max(\text{dp}[j + 1][w + w_i], \text{dp}[j][w] + b_i)\)$

答えの算出: すべてのパネルについて遷移を行った後、以下の条件を満たす \((j, w)\) の中から dp[j][w] の最大値を探します。 - \(0 \le j \le N\) - \(\max(0, L - (j + 1) \times (K - 1)) \le w \le L\)

条件を満たす状態が1つも存在しない（最大値が初期値の -1 のまま）場合は、-1 を出力します。

---

計算量

時間計算量: \(O(N^2 L)\)

• 外側のループでパネルを \(N\) 個順に処理します。
• 内側のループで、選ぶ個数 \(j\)（最大 \(N\)）と、現在の幅 \(w\)（最大 \(L\)）を走査します。
• したがって、全体の遷移回数は最大で \(N \times N \times L = N^2 L\) となります。
• 本実装では、これまでに選んだパネルの幅の合計の最大値 total_w を保持し、無駄な \(w\) のループをスキップすることで、定数倍を大幅に高速化しています。
• \(N \le 400\), \(L \le 1000\) の制約下では、\(N^2 L \approx 1.6 \times 10^8\) ですが、上記の最適化により、実行時間制限に十分間に合います。

空間計算量: \(O(N L)\)

• DPテーブルのサイズは \((N + 1) \times (L + 1)\) です。
• \(N \le 400\), \(L \le 1000\) のため、メモリ使用量は極めて小さく、空間計算量は \(O(N L)\) となり、制限時間・メモリともに安全に動作します。

---

実装のポイント

• インプレースDPによるメモリ節約: DPテーブルを更新する際、個数 \(j\) のループを逆順（for j in range(i, -1, -1)）に回すことで、遷移前の古いデータを上書きすることなく、2次元配列だけで正しく遷移を行うことができます。

• 枝刈り（高速化）: total_w という変数を用意し、それまでに登場したパネルの幅の累積和を保持しています。これにより、あり得ない大きな \(w\) に対して遷移を試みる無駄を省き、実行速度を劇的に向上させています。

  ソースコード

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return

    N = int(data[0])
    L = int(data[1])
    K = int(data[2])

    panels = []
    idx = 3
    for _ in range(N):
        panels.append((int(data[idx]), int(data[idx + 1])))
        idx += 2

    # dp[j][w] : j枚選んで幅wのときの最大価値
    dp = [[-1] * (L + 1) for _ in range(N + 1)]
    dp[0][0] = 0

    total_w = 0
    for i in range(N):
        wi, bi = panels[i]
        limit = min(L - wi, total_w)
        for j in range(i, -1, -1):
            dp_prev = dp[j]
            dp_curr = dp[j + 1]
            for w in range(limit + 1):
                val = dp_prev[w]
                if val != -1:
                    new_val = val + bi
                    if new_val > dp_curr[w + wi]:
                        dp_curr[w + wi] = new_val
        total_w = min(L, total_w + wi)

    ans = -1
    for j in range(N + 1):
        dp_j = dp[j]
        # w の下限条件: (j + 1) * (K - 1) >= L - w  =>  w >= L - (j + 1) * (K - 1)
        min_w = L - (j + 1) * (K - 1)
        if min_w < 0:
            min_w = 0
        for w in range(min_w, L + 1):
            if dp_j[w] > ans:
                ans = dp_j[w]

    print(ans)


if __name__ == "__main__":
    solve()

---

この解説は gemini-3.5-flash-thinking によって生成されました。