問題
長さ N の正数列 A_i と, 大きな数 X (X \geq \sum_i A_i) が与えられる.
A_i から k (0 \leq k \leq N) 個選んでその和を S だとする.
上手に k 個選ぶことで次の自然数 t を最小化せよ:
つまり X-S は k の倍数である必要がある.
N は 100 程度.
解法
N=100 のケースを考えると, すべての選び方は 2^N 通りと膨大なのでそのすべてを試すことは出来ない.
しかし, 各 k についての最適な選び方は試すことが出来る.
k を決めた時, 和 S は大きいに越したことはない（しかも X を超える心配はない）ので最大値を取りながらありえる和を探せばよい.
ただしここで X-S が k の倍数になることが要請されている.
そこで和の最大を取りながら \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}
を得て,
が答えの候補.
k=1,2,\ldots,N 全てについてこの
t を計算して最小値を取れば良い.
Discussion