Day 162-Q3 — 2026-09-27 — 凹関数との (max,+) 畳み込みで「重さの種類が少ない」ナップサックを解く

📋 コピーimport sys


def maxplus_concave(A, P):
    """B[i] = max_{0<=i-j<len(P)} A[j] + P[i-j]  (P は凹、A は任意)。len(B) = len(A)。
    最適な j は i について単調非減少なので、分割統治で O(L log L)。"""
    L, m = len(A), len(P) - 1
    B = [0] * L
    stack = [(0, L - 1, 0, L - 1)]
    while stack:
        lo, hi, jlo, jhi = stack.pop()
        if lo > hi:
            continue
        mid = (lo + hi) >> 1
        a = mid - m if mid - m > jlo else jlo          # i-j <= m
        b = mid if mid < jhi else jhi                  # j <= i
        best, arg = A[a] + P[mid - a], a
        for j in range(a + 1, b + 1):
            v = A[j] + P[mid - j]
            if v > best:                               # 同点は小さい j を残す（左端の argmax）
                best, arg = v, j
        B[mid] = best
        stack.append((lo, mid - 1, jlo, arg))
        stack.append((mid + 1, hi, arg, jhi))
    return B


def main():
    data = sys.stdin.buffer.read().split()
    n, W = int(data[0]), int(data[1])
    groups = {}
    for i in range(n):
        w, v = int(data[2 + 2 * i]), int(data[3 + 2 * i])
        groups.setdefault(w, []).append(v)
    dp = [0] * (W + 1)                                 # dp[c] = 重さ c 以下での最大価値
    for w, vs in groups.items():
        if w > W:
            continue
        vs.sort(reverse=True)                          # 同じ重さなら価値の大きい順に取るのが最善
        vs = vs[:W // w]                               # 入りきらない分は捨てる
        P = [0]
        for v in vs:
            P.append(P[-1] + v)                        # P[k] = 上位 k 個の和（凹）
        for r in range(w):                             # 重さ w で割った余りごとに独立
            A = dp[r::w]
            dp[r::w] = maxplus_concave(A, P)
    print(dp[W])


main()