部分和DP

ABC015D 解法 ナップザック問題の DPと同じで，部分和問題の DP. 状態数が少ない様に DP の定義域と値域を選ぶと， 空間計算量と時間計算量が小さくできる． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll w; cin >> w; ll n,k; cin >> n >> k; vll a(n), b(n); rep(i,n){ cin >> a[i] >> b[i]; } const ll c = n * 100 + 5; vvll dp(c+1, vll(…

ABC192F 簡単な問題から考える． 取り方 \(s \in 2^{N}\) を固定 \(t := sum(s)\) とおく． \(s\) に対する答えは， \(x-t \equiv 0 \ mod \ |s|\) のとき \(\frac{x-t}{|s|}\) となる． それ以外のときは不可能． 取った個数 \(k \in [1,N]\) を固定 これも同様． \(k = |s|\) となる \(s \in 2^{N}\) を考える． \(\frac{x-t}{k}\) を最小にしたいから， 和 \(t\) を最大にすればよい． 答えは \(max_{s \in 2^{N} \\ |s| …

ABC317D 計算量を見ると，\(O(N * sum(Z))\) は間に合う． ここから DP を考えるというよりは，まずは自然に考える． 簡単に思いつくのは，\(i\) を固定したときの様子を探ること． \(i \in N\) を固定したとき何人を鞍替えさせれば良いかを考える． 鞍替えさせる人数を \(d \in \mathbb{N}\) 人とする． \(y_{i} < x_{i}\) のときは\(d = 0\) \(y_{i} > x_{i}\) のときは \(y_{i} - d < x_{i} + d \) を満たせばよい． よって，\(d > (y_{i} - x_{i})/2\) …

ABC310F 部分和 DP. \(M := 10\) とおく． \(s \subset [0,M] \) を作れる数全体とする． 今のさいころの出目 \(x\) によって場合分け． \(x \in [1,min(a_{i}, M)]\) の場合:作れる数の集合が \(t := s \cup \{y+x \ \vert \ y \in s\}\) に変わる． \(dp_{t} \text{+=} old_{s}\)． \(x \in (min(a_{i},M), a_{i}]\) の場合:サイコロの目を採用することはないので， \(s\) は変わらない． \(a_{i}\) が大きいので，まと…

ABC159F O(NS)は間に合うので，次の二つが考えられる． 今見ている index を \(i \in N\)，部分和をとる区間を \([l,r)\) とする． (i): \(i \in N,\ s \in S\) を全探索， (ii): \(r \in N,\ s \in S\) を全探索， (iii): 多項式を使った数え上げ． 解法(i)まず，簡単のために通常の部分和問題を考えると， 今調べている \(i \in N\) に対して，使うか使わないかの2択を全探索． ここで，今までの和だけ決まっていれば，今までの選び方は区別する必要がなかったので， 状態をまとめることで高速化していた…

ABC289D 部分和DP. 移動出来ない場合に注意． 実装するときには，使ってない条件がないか確認しよう． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n, m, k, q; cin >> n; vll a(n); rep(i,n) { cin >> a[i]; } cin >> m; set<ll> b; rep(i,m){ ll y; cin >> y; b.insert(y); } ll x ; cin >> x; vector<bool> dp(x+1);…