はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおける枝刈り問題まとめ

枝刈り

  • たまに枝刈り全探索みたいな解法が想定解の場合がある
  • 「貪欲に枝刈りをしていくとなぜか通ってしまう」とか「validな状態はそんなに無いから実装が楽な枝刈り全探索」とかそういうのがある
  • 枝刈りで計算量が落とせる名前がついている手法
    • 二乗の木DP
      • 木DPをする際にDPの使われていない要素は枝刈りをして更新をしない
    • 分枝限定法
      • 参考
      • 簡単な方針で求めた下界や上界の範囲内で全探索を行うと計算量が減る
      • テストケースに悪意がない(ランダム生成)の場合は特に有効