atcoder.jp 解法 愚直に解こうとするとO(2N)で絶対間に合わない。 Aはmax、Bは総和が条件として示されているため、A[i] ≦ 5000という制約が気になる。 この制約があることで、Bの和が5000より大きい数になるような集合は考えなくて良いことになる。 Bの要素…

atcoder.jp この問題は下の問題とほぼ同じだった。 atcoder.jp ↓自分の記事 nizi-24.hatenablog.com 解法 絶対値によってiとjが分かれている問題は、絶対値を外してiとjを独立に計算すると良いことが多い。 $ x_i ≧ x_j $としても一般性を失わない($ x_i < x…

atcoder.jp 解法 香辛料の消費量は、整数以外も選択できるがどこかで調整すればすべて整数にすることができるので、最初から整数で考えてよい。 ナップザックDP感があるので、普通にDPするしようとすると、 dp[i][w] ← i番目までの料理を作った時、香辛料をw…