2017-12-23 競技プログラミングにおける枝刈り問題まとめ 競技プログラミング 枝刈り たまに枝刈り全探索みたいな解法が想定解の場合がある 「貪欲に枝刈りをしていくとなぜか通ってしまう」とか「validな状態はそんなに無いから実装が楽な枝刈り全探索」とかそういうのがある 枝刈りで計算量が落とせる名前がついている手法 二乗の木DP 木DPをする際にDPの使われていない要素は枝刈りをして更新をしない 分枝限定法 参考 簡単な方針で求めた下界や上界の範囲内で全探索を行うと計算量が減る テストケースに悪意がない（ランダム生成）の場合は特に有効 問題 全探索+枝刈り AtCoder すぬけそだて――ごはん―― 解説 AOJ Dragon Fantasy 解説 Unit Fraction Partition 解説 AOJ 全チームによるプレーオフ 解説 ABC123 Cake 123 解説 yukicoder No.847 Divisors of Power 解説 LC1240. Tiling a Rectangle with the Fewest Squares 分枝限定法 ABC032 ナップサック問題 解説 kimiyukiさんのタグ CF102 Help Caretaker 解説 yukicoder No.617 Nafmo、買い出しに行く CF103 Competition CF44 Safe その他 CF406 Till I Collapse 解説1 解説2 （答えが広義単調減少するので飛び飛びに計算すると、間の計算を枝刈りできる）
