【関連】 ABC231F - Jealous Two - 競プロはじめました 考え方 回答例 考え方ABC231Fと類似の考え方．ただし，BITで区間和を取るのではなく，区間の最大値を求める．最大値を求めるように，BIT (Binary Indexed Tree (BIT) / Fenwick Tree - 競プロはじめま…

【関連】 F - Valid payments 考え方 回答例 考え方まず，$X$を「$\{A_{i}\}_{i}$を使った進数」で表す．つまり，「$X$を最小の硬貨でピッタリ払うときに必要な各硬貨の枚数」を決める．これは，大きい硬貨から使えるだけ使えば良い．これにより，$X$を\begi…

考え方：公式解説の方法公式解説の方法（Editorial - Exawizards Programming Contest 2021（AtCoder Beginner Contest 222））を考える． まず，各辺を何回通るか求める．頂点$A_{i}$と頂点$A_{i+1}$を結ぶ辺を通る回数を$C_{i}$とする．すると，\begin{ali…

考え方dp[i][j]=「$c_{i} = j$となる方法の数」がわかれば，\begin{aligned} &\mathrm{dp}[i+1][j] \\ & = \begin{cases} \, \displaystyle \sum_{k\leq j} \mathrm{dp}[i][k] & (A_{i + 1} \leq j \leq B_{i+1}) \\ \, 0 & (\text{otherwise}) \end{cases} …

【類題】EDPC - D - Knapsack 1 - 競プロはじめました 考え方 DP - 「ぴったり」で考える方法 貰うDP 考え方まず，制約から何を変数に使えるか考える．D - Knapsack 1とは，制約のみ異なる．これにより，変数に$W$を使うことはできなくなる．代わりに，$v_{i…

【類題】EDPC - E - Knapsack 2 - 競プロはじめました 考え方②：「ぴったり」で考える方法 貰うDP 考え方①：「以下」で考える方法 貰うDP 考え方②：「ぴったり」で考える方法「$W$以下」ではなく，「$W$ぴったり」となるように考えるのがよくあるパターン．…

配るDPでないと，うまく書けない例？ 【類題】 ABC099C - Strange Bank - 競プロはじめました ナップサック問題に雰囲気が似ている：D - Knapsack 1 - 競プロはじめましたDP考え方$N$コの弁当からたこ焼き$X$コ・たい焼き$Y$コ（ぴったり）になるよう選ぶ方…

きっかけ：ABC219Dと次の記事． 貰う DP と配る DP、メモ化再帰、個数制限なしナップサック問題 - Qiita DP 考え方 貰うDP 配るDP メモ化再帰 DP考え方答えを$f(N)$とすると，$x = 0,1,...,N-1$に対して$f(x)$がわかっていれば$f(N)$が計算できる．よって，D…

DPだとわかっていれば，意外とできるものです． 遷移方法を正しく書き下せるかがポイントです．DPだけでなく，メモ化再帰も考えると理解が深まりそうです． 【2021.05.16~】 考え方 DP メモ化再帰 A - Frog 1 B - Frog 2 C - Vacation D - Knapsack 1 E - Kn…