7K12 blog

猫でも分かるアルゴリズム解説

BIT_DP

ABC142 E - Get Everything

https://atcoder.jp/contests/abc142/submissions/11902212 初期値はdp[0]=0 繰り返しは rep(i, 0, M) rep(j, 0, Pow2(N)) 遷移は dp[next] = min(dp[next], dp[j] + key[i].a); 出力は dp[Pow2(N) - 1]; 制約からbitDPと分かる。 各鍵key[i]と宝箱の空き状…

Educational DP Contest M - Candies

https://atcoder.jp/contests/dp/submissions/10545854 子供たちが飴を分け合うと言うと重複組み合わせっぽく見えるが、重複組み合わせだとDPが書きづらいので子供i-1から子供iに遷移するとき飴jがどうなるかというDPで実装する。このとき、K個の飴を配ると…