JPRSプログラミングコンテスト2026#1（AtCoder Beginner Contest 442）E,F,G問題メモ

以下は、180度で分けると大丈夫な確証が持てなくて、念のため90度ずつに分けてソートしてる。

from collections import defaultdict
from functools import cmp_to_key
from itertools import accumulate
from math import gcd, atan2


def angle_sort(p0, p1):
    if p0[0] * p1[1] == p0[1] * p1[0]:
        return 0
    return 1 if p0[0] * p1[1] < p1[0] * p0[1] else -1


sort_key = cmp_to_key(angle_sort)


def solve(n, q, monsters, queries):
    angles1 = set()
    angles2 = set()
    angles3 = set()
    angles4 = set()
    count = defaultdict(int)
    normalized = []
    for i, (x, y) in enumerate(monsters):
        g = gcd(x, y)
        x //= g
        y //= g
        if x > 0 and y >= 0:
            angles1.add((x, y))
        elif x >= 0 and y < 0:
            angles2.add((-y, x))
        elif x < 0 and y <= 0:
            angles3.add((-x, -y))
        else:
            angles4.add((y, -x))
        normalized.append((x, y))
        count[x, y] += 1

    def sort_angle(angles):
        thetas = list(angles)
        thetas.sort(key=sort_key, reverse=True)
        return thetas

    angles = []
    angles.extend((x, y) for x, y in sort_angle(angles1))
    angles.extend((y, -x) for x, y in sort_angle(angles2))
    angles.extend((-x, -y) for x, y in sort_angle(angles3))
    angles.extend((-y, x) for x, y in sort_angle(angles4))

    m = len(angles)
    acc = [0] * (m * 2)
    mapping = {}
    for i in range(m):
        x, y = angles[i]
        acc[i] += count[x, y]
        acc[i + m] += count[x, y]
        mapping[x, y] = i
    acc = [0] + list(accumulate(acc))

    buf = []
    for a, b in queries:
        x1, y1 = normalized[a - 1]
        x2, y2 = normalized[b - 1]
        i1 = mapping[x1, y1]
        i2 = mapping[x2, y2]
        if i2 < i1:
            i2 += m
        buf.append(acc[i2 + 1] - acc[i1])
    return buf


n, q = list(map(int, input().split()))
monsters = [list(map(int, input().split())) for _ in range(n)]
queries = [list(map(int, input().split())) for _ in range(q)]
ans = solve(n, q, monsters, queries)
print('\n'.join(map(str, ans)))

def solve(n, grid):
    dp = [0] * (n + 1)
    for i in range(n):
        row = grid[i]
        lll = [0]  # k=i とするために黒を白に変える必要があるマスの数
        rrr = [0]  # k=N-i とするために白を黒に変える必要があるマスの数（後で反転）
        for j in range(n):
            lll.append(lll[-1] + int(row[j] == '#'))
        for j in range(n - 1, -1, -1):
            rrr.append(rrr[-1] + int(row[j] == '.'))
        rrr.reverse()
        ndp = list(map(sum, zip(lll, rrr, dp)))
        for j in range(n - 1, -1, -1):
            ndp[j] = min(ndp[j], ndp[j + 1])
        dp = ndp
    return dp[0]


n = int(input())
grid = [input() for _ in range(n)]
ans = solve(n, grid)
print(ans)

密度が高い方から採用している以上、

• $A$: 最適解には含まれず、貪欲解に含まれるアイテムの集合（貪欲解から取り除くべきもの）
• $B$: 貪欲解には含まれず、最適解に含まれるアイテムの集合（貪欲解に追加すべきもの）

とした時、「$A$ からいくつか選んだアイテムの重さの合計」と「$B$ から以下同」が同じになるアイテムの組があると、 そのアイテム群は交換しない方がよい（して得しない）ので、矛盾する。

例えば、$A$ と $B$ の間に同じ重さのアイテムは無いし、重さ $\{2,2\}$ を出して $\{1,3\}$ を入れる、みたいなこともない。

また密度が低いアイテムが価値を上回るためには、（$A$ の重さの総和）$\lt$（$B$ の重さの総和）でなければならない。 つまり、$A$ の方に重さ $w$ のアイテムが $3$ 個以上含まれる時、$B$ の重さの総和は $3w+1$ 以上でなければならない。
だが、$B$ で重さの和 $w,2w,3w$ を作らず $3w+1$ 以上を作ることはできないことが、$w=1,2,3$ の場合それぞれ全探索でわかる。 （$A$ 側に $w$ 以外のアイテムがあったとしても、更に条件が厳しくなるだけである）
よって $A$ の方は示せた。

また、貪欲解でも詰められるだけは詰めているので、残容量は $2$ 以下である。 つまり、（$B$ の重さの総和）$\le$（$A$ の重さの総和）$+2$ でなければならない。
$B$ の方に重さ $w$ のアイテムが $3$ 個以上含まれる時、 「$A$ 側で $w,2w,3w$ を作らず、$3w-2$ 以上を作ることができない」ことが全探索でわかるので、$B$ の方も示せる。

各アイテムが、重さ $1～M$ の範囲を取るとする。（今回は $M=3$）
容量 $C$ が $M$ より十分に大きく、本問題と同様、貪欲解からの微調整によって解くことを考える。

この時、貪欲解からどの程度、境界付近を探索すれば十分と言えるか？

これは、採用したものと採用してないもので、容量 $M(M-1)$ のナップサックを行うとよい、、、 ように思うが、ちゃんと証明はできてない。

• $\mathrm{DP}_1$: 貪欲で採用したアイテムだけで、容量 $M(M-1)$ で、価値minのナップサック
  • $\mathrm{DP}_1[i]$ は重さ $i$ ちょうどの価値
• $\mathrm{DP}_2$: 採用してないアイテムだけで、容量 $M(M-1)$ で、価値maxのナップサック
  • $\mathrm{DP}_2[i]$ は重さ $i$ 以下で作れる価値

貪欲で余った容量を $s$ として、$\max(0,\max_{i}\mathrm{DP}_2[i+s]-\mathrm{DP}_1[i])$ だけ、貪欲解から価値を増やせる。

• $A$: 最適解には含まれず、貪欲解に含まれるアイテムの、重さの多重集合
• $B$: 貪欲解には含まれず、最適解に含まれるアイテムの、重さの多重集合
• $S_A$: $A$ からの1個以上の要素の部分和として作れる値の集合
• $S_B$: $B$ からの1個以上の要素の部分和として作れる値の集合

とすると、以下の制約がある。（さっきの略証参照）

• $Sum(A) \lt Sum(B) \lt Sum(A)+M$
• $S_A \cap S_B = \phi$

これを達成できる $\sum B$ の上限が、$M(M-1)$ と考えられる？

• いろんな重さの種類があったらいろんな部分和を作れてしまうので、$A,B$ それぞれ少ない種類からなる方が良さそう
• 一方に $M-1$ のみ、もう一方に $M$ のみいっぱいある場合、重さの総和 $M(M-1)$ ではじめて部分和が一致する。
  • 単一の値同士からなる場合、これが最大
• その直前で止めて、$S_A,S_B$ が被らない範囲で他の重さを少量加えることができたとしても、$M(M-1)$ を超えることはない

だが、複数種類の重さを組み合わせてこれより大きい上限を作ることが本当にできないか、よくわかんない。

def solve(n, c, items):
    items.sort(key=lambda a: a[1] / a[0], reverse=True)
    i = 0
    ans_greedy = 0
    last = None

    while i < n and c > 0:
        w, v, k = items[i]
        if c >= w * k:
            c -= w * k
            ans_greedy += v * k
            i += 1
            continue
        cnt = c // w
        c -= w * cnt
        ans_greedy += v * cnt
        items[i][2] -= cnt
        last = (w, v, cnt)
        break

    LIMIT = 2
    pop_count = [0] * 4
    add_count = [0] * 4
    www = []
    vvv = []
    if last is not None:
        w, v, cnt = last
        cnt = min(cnt, LIMIT)
        pop_count[w] += cnt
        www.extend([w] * cnt)
        vvv.extend([v] * cnt)
        c += w * cnt
        ans_greedy -= v * cnt

    for j in range(i - 1, -1, -1):
        w, v, k = items[j]
        while k > 0 and pop_count[w] < LIMIT:
            pop_count[w] += 1
            www.append(w)
            vvv.append(v)
            c += w
            ans_greedy -= v
            k -= 1

    for j in range(i, n):
        w, v, k = items[j]
        while k > 0 and add_count[w] < LIMIT:
            add_count[w] += 1
            www.append(w)
            vvv.append(v)
            k -= 1

    m = len(www)
    ans = 0
    memo_v = [0] * (1 << m)
    memo_w = [0] * (1 << m)
    for bitset in range(1, 1 << m):
        lsb = bitset & -bitset
        i = lsb.bit_length() - 1
        memo_w[bitset] = memo_w[bitset ^ lsb] + www[i]
        memo_v[bitset] = memo_v[bitset ^ lsb] + vvv[i]
        if memo_w[bitset] <= c:
            ans = max(ans, memo_v[bitset])
    ans += ans_greedy
    return ans


n, c = list(map(int, input().split()))
items = [list(map(int, input().split())) for _ in range(n)]
ans = solve(n, c, items)
print(ans)