😺

ABC192/F - Potion

1 min read

問題

長さ N の正数列 A_i と, 大きな数 X (X \geq \sum_i A_i) が与えられる.
A_i から k (0 \leq k \leq N) 個選んでその和を S だとする.
上手に k 個選ぶことで次の自然数 t を最小化せよ:

S + kt = X.

つまり X-Sk の倍数である必要がある.

N100 程度.

解法

N=100 のケースを考えると, すべての選び方は 2^N 通りと膨大なのでそのすべてを試すことは出来ない.
しかし, 各 k についての最適な選び方は試すことが出来る.

k を決めた時, 和 S は大きいに越したことはない(しかも X を超える心配はない)ので最大値を取りながらありえる和を探せばよい.
ただしここで X-Sk の倍数になることが要請されている.
そこで和の最大を取りながら \bmod k も気にすれば良い.

つまり,

\mathrm{dp}^t_m = \left( \text{ t 個の和であって, $\bmod k=m$ なものの最大値 } \right)

を計算する.
このDPテーブルは遷移に N^2 掛かってそれを A_i 全てで舐めるので O(N^3) 掛かるが N が小さいので間に合う.

k について上で述べたDPを行うことで

S = \mathrm{dp}^k_{X \bmod k}

を得て,
t = (X - S) / k

が答えの候補.
k=1,2,\ldots,N 全てについてこの t を計算して最小値を取れば良い.

Discussion

ログインするとコメントできます