EDPC - D - Knapsack 1

考え方② 貰うDP 考え方① 貰うDP 考え方②「$W$以下」ではなく,「$W$ぴったり」となるように考えるのがよくあるパターン.また,ぴったりを考えたほうが,遷移が考えやすい(勘違いしにくい). 【例】 ABC219D - Strange Lunchbox - 競プロはじめました $N$…

ABC219D - Strange Lunchbox

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

ABC099C - Strange Bank

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

ABC218F - Blocked Roads

考え方 回答例 考え方 辺を除かない状態で,最短距離dを求める.また,最短経路につかう辺の集合routeを求める. 辺を順に除いていき,その辺がrouteに含まれないならdが答え.routeに含まれるなら,もう一度最短距離を求める(※). (※)routeの数≦$N-1$で…

ABC218E - Destruction

クラスカル法クラスカル法.コストの小さい順に辺を見ていき,閉路・二重辺でなければ追加する.UnionFindを使う.バラバラの状態からはじめ,辺の頂点が同じグループに属していないなら追加すれば良い.UnionFindコストが負の辺は取り除く意味がない(すべ…

ABC218D - Rectangles

対角線上の2点を決める 対辺の数を求める 対角線上の2点を決める長方形は,対角線上の2点により一意に決まる.よって, 左上と右下の座標を決めたとき, 左下と右上の座標が集合に含まれるか判定する setのinなら$O(1)$で計算できるのがポイント.【参考】Su…

ABC218C - Shapes

不要部分を削った行列が一致するか判定する numpyによる解法 numpyなし #の座標の集合で見る 不要部分を削った行列が一致するか判定する行列の不要な部分を削除した上で,片方の行列を回転させてもう一方と一致するかを調べれば良い.numpyによる解法ちょっ…

ABC217D - Cutting Woods

C++ ではこんなに簡単にかけるのに... Editorial - AtCoder Beginner Contest 217一般的な話は次が役立ちそう: std::setを使わない代替テクニック [いかたこのたこつぼ] 【Python】平衡二分木が必要な時に代わりに何とかするテク【競プロ】 - Qiita 考え…

ABC216E - Amusement Park

考え方 二分探索 貪欲法 考え方$1 \leq K, A_{i} \leq 2\times 10^{9}$と,大きな値を取り得る.二分探索公式解説の方法:Editorial - AtCoder Beginner Contest 216初期値が$A_{i}$のアトラクションは,最大$A_{i}$回利用できる.利用回数の視点で考えるの…

ABC216D - Pair of Balls

考え方言われたとおりにやって間に合うというのに気付けるか,言われた通りのことが実装できるかがポイント.一番上を毎回すべてスキャンする必要はなく,取り除いた次のボールの状態だけ更新すれば良いから間に合う. 一番上に2個同じ色があれば取り除く. …