結果
| 問題 | No.3670 Fast Knapsack |
| コンテスト | |
| ユーザー |
 harurun
|
| 提出日時 | 2026-09-01 22:53:30 |
| 言語 | PyPy3 (7.3.23) |
| 結果 |
AC
|
| 実行時間 | 496 ms / 2,500 ms |
| + 66µs | |
| コード長 | 8,706 bytes |
| 記録 | |
| コンパイル時間 | 542 ms |
| コンパイル使用メモリ | 96,212 KB |
| 実行使用メモリ | 133,392 KB |
| 最終ジャッジ日時 | 2026-09-04 23:03:36 |
| 合計ジャッジ時間 | 6,038 ms |
|
ジャッジサーバーID （参考情報） |
judge1_0 / judge4_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 25 |
ソースコード
import sys
from math import gcd
from bisect import bisect_right
import pypyjit
pypyjit.set_param(
"threshold=1,"
"function_threshold=1,"
"trace_eagerness=1,"
"decay=0"
)
# 63 bit / word
#
# 64 bit にすると 2^63 以上の値が現れて PyPy の多倍長整数に
# 昇格する可能性がある。
W = 63
# r bit 左シフトするとき、
# 下側 word に残る部分だけを先に mask する。
#
# これにより
#
# (x & LOW_MASK[r]) << r < 2^63
#
# が常に成立する。
LOW_MASK = [0] * W
r = 1
while r < W:
LOW_MASK[r] = (1 << (W - r)) - 1
r += 1
def solve():
data = list(map(int, sys.stdin.buffer.read().split()))
pos = 0
T = data[pos]
pos += 1
out = [""] * T
tc = 0
while tc < T:
n = data[pos]
S0 = data[pos + 1]
pos += 2
end = pos + n
freq = {}
g = 0
total = 0
while pos < end:
a = data[pos]
pos += 1
if a <= S0:
total += a
g = gcd(g, a)
freq[a] = freq.get(a, 0) + 1
if not freq:
out[tc] = "0"
tc += 1
continue
if total <= S0:
out[tc] = str(total)
tc += 1
continue
# 全ての部分和は g の倍数なので問題を縮約する。
S = S0 // g
pairs = []
capped_sum = 0
min_a = S + 1
max_a = 0
for aa, c in freq.items():
a = aa // g
# これを超える個数は、どの feasible subset にも入らない。
lim = S // a
if c > lim:
c = lim
pairs.append((a, c))
capped_sum += a * c
if a < min_a:
min_a = a
if a > max_a:
max_a = a
# 使用可能個数まで削った後、全部入る。
if capped_sum <= S:
out[tc] = str(capped_sum * g)
tc += 1
continue
# ------------------------------------------------------------
# 値域が狭い場合の高速処理
#
# k = floor(S / max_a)
#
# k 個なら最大値だけを k 個選んでも S 以下。
#
# 一方、
#
# (k + 1) * min_a > S
#
# なら k+1 個は絶対に選べない。
#
# よって「大きい順に k 個」が最適。
# ------------------------------------------------------------
k = S // max_a
if (k + 1) * min_a > S:
pairs.sort(reverse=True)
need = k
ans = 0
i = 0
m = len(pairs)
while need and i < m:
a, c = pairs[i]
if c < need:
take = c
else:
take = need
ans += a * take
need -= take
i += 1
out[tc] = str(ans * g)
tc += 1
continue
# ------------------------------------------------------------
# bounded subset sum
#
# c 個の同じ値 a を
#
# a, 2a, 4a, ...
#
# に二進分解する。
# ------------------------------------------------------------
chunks = []
for a, c in pairs:
p = 1
while c:
if p < c:
take = p
else:
take = c
chunks.append(a * take)
c -= take
p <<= 1
chunks.sort()
# 二進分解後にも同じ判定を入れる。
min_c = chunks[0]
max_c = chunks[-1]
k = S // max_c
if (k + 1) * min_c > S:
out[tc] = str(sum(chunks[-k:]) * g)
tc += 1
continue
# ------------------------------------------------------------
# S/2 より大きい chunk は、解に高々 1 個しか入らない。
#
# したがってこれらは bitset に投入しない。
# ------------------------------------------------------------
split = bisect_right(chunks, S >> 1)
top_word = S // W
# +2 にして carry の境界判定を削除する。
bits = [0] * (top_word + 2)
bits[0] = 1
# 処理済み chunk の総和。
# reachable bit の上限として使う。
cap = 0
target_word = top_word
target_bit = S - target_word * W
i = 0
# ------------------------------------------------------------
# 固定長 bitset DP
# ------------------------------------------------------------
while i < split:
a = chunks[i]
# shift 元として見る必要がある最大 bit。
#
# x > S-a なら x+a > S なので無視できる。
lim = cap
sa = S - a
if lim > sa:
lim = sa
src = lim // W
q = a // W
r = a - q * W
if r == 0:
while src >= 0:
x = bits[src]
if x:
bits[src + q] |= x
src -= 1
else:
low_mask = LOW_MASK[r]
rr = W - r
while src >= 0:
x = bits[src]
if x:
dst = src + q
# 下側
#
# shift 前に mask することで
# 多倍長整数への昇格を防ぐ。
bits[dst] |= (x & low_mask) << r
# 上側 carry
bits[dst + 1] |= x >> rr
src -= 1
cap += a
if cap > S:
cap = S
# S が作れた時点で終了。
if (bits[target_word] >> target_bit) & 1:
out[tc] = str(S * g)
break
i += 1
else:
# --------------------------------------------------------
# 各 word より前にある非零 word を記録する。
#
# S/2 より大きい chunk に対する
#
# max reachable <= S-a
#
# を O(1) 近くで求めるため。
# --------------------------------------------------------
prev = [-1] * (top_word + 1)
last = -1
j = 0
while j <= top_word:
if bits[j]:
last = j
prev[j] = last
j += 1
# small chunks のみで作れる最大値。
wi = top_word
rb = S - wi * W
x = bits[wi]
if rb != W - 1:
x &= (1 << (rb + 1)) - 1
if x:
best = wi * W + x.bit_length() - 1
else:
wi -= 1
if wi >= 0:
wi = prev[wi]
if wi >= 0:
best = wi * W + bits[wi].bit_length() - 1
else:
best = 0
# --------------------------------------------------------
# 大きい chunk を 1 個だけ加える。
# --------------------------------------------------------
i = split
m = len(chunks)
while i < m:
a = chunks[i]
limit = S - a
wi = limit // W
rb = limit - wi * W
x = bits[wi]
if rb != W - 1:
x &= (1 << (rb + 1)) - 1
if x:
small_best = wi * W + x.bit_length() - 1
else:
wi -= 1
if wi >= 0:
wi = prev[wi]
if wi >= 0:
small_best = (
wi * W
+ bits[wi].bit_length()
- 1
)
else:
small_best = 0
v = a + small_best
if v > best:
best = v
if best == S:
break
i += 1
out[tc] = str(best * g)
tc += 1
sys.stdout.write("\n".join(out))
if __name__ == "__main__":
solve()