部分和問題(O(Nmax(A))) - Githubissues

kemuniku / cplib

Creative Commons Zero v1.0 Universal

4 stars 1 forks source link

部分和問題(O(Nmax(A))) #446

Open kemuniku opened 1 month ago

kemuniku commented 1 month ago

数列A_iの部分集合であって合計がXになるようなものが存在するか判定 1 <= X <= N*max(A)

愚直にやると、O(XN) → O(N^2 max(A))だが、O(Nmax(A))で解く方法があるらしい。

https://qiita.com/lowking/items/a9393f6afb9a4e662c38 https://atcoder.jp/contests/abc221/editorial/2741