hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング 枝刈り たまに枝刈り全探索みたいな解法が想定解の場合がある 「貪欲に枝刈りをしていくとなぜか通ってしまう」とか「validな状態はそんなに無いから実装が楽な枝刈り全探索」とかそういうのがある 枝刈りで計算量が落とせる名前がついている手法 二乗の木DP 木DPをする際にDPの使われていない要素は枝刈りをして更新をしない 分枝限定法 参考 簡単な方針で求めた下界や上界の範囲内で全探索を行うと計算量が減る テストケースに悪意がない（ランダム生成）の場合は特に有効 問題 全探索+枝刈り AtCoder すぬけそだて――ごはん―― 解説 AOJ Dragon Fantasy 解説 Unit Fracti… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2017%2F12%2F23%2F155922" title="競技プログラミングにおける枝刈り問題まとめ - はまやんはまやんはまやん" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2017-12-23 15:59:22 rich https://blog.hamayanhamayan.com/entry/2017/12/23/155922 1.0 100%