DEGwerさんの数え上げテクニック集問題まとめ

数え上げ問題のテクニックを紹介した金字塔として、DEGwerさんの数え上げテクニック集という資料がある。
この資料に書かれたテクニックが用いられた問題を以下にまとめる。

• 1. はじめに
• 2. 状態をまとめる
• 3. 探索順の変更
  • 3.1. 大きい順に並べる = 動的計画法のテク2
  • 3.2. 順列は挿入DP = 挿入DP
  • 3.3. 区画は終点でソート
• 4. 条件の言い換え
  • APC001 Antennas on Tree
  • 条件の言い換えとして不変量が用いられる場合がある
• 5. greedyからの帰着
  • 部分列DP
  • 部分文字列で文字列が重複しないように数え上げる場合によく使うイメージ
  • TopCoderOpen 2018 Wildcard Round Hard CommonPalindromicSubsequences 解説
  • AGC027 ABBreviate
  • AOJ 回文部分列 (Palindromic Subsequences) 解説
  • TDPC 辞書順
  • HR 何でもダガー打ちゃいいってもんじゃねぇぞ†2020 解説
• 6. 場合分けのテクニック
• 7. 線形和への分解
• 8. 部分群のテクニック
• 9. 再帰的な定義の利用
• 10. 桁DPについて = 桁DP
• 11. 高速化のテクニック
  • 11.1. 累積和の利用 = 動的計画法更新最適化
  • 11.2. データ構造の利用 = 動的計画法更新最適化
  • 11.3. 配列の使いまわし = インラインDP
  • 11.4. 高速フーリエ変換 = 畳み込み
  • 11.5. 高速ゼータ変換 = 畳み込み
  • 11.6. AndとAddの畳み込み = 畳み込み
  • 11.7. 簡単な枝刈り
• 12. 行列を用いたテクニック
  • 12.1. 二分累乗 = 動的計画法更新最適化
  • 12.2. 行列式のテクニック = 無向グラフ上での特殊な数え上げ問題
• 13. 小さい確率を無視する
• 14. 二項係数のテクニック
  • 14.1. 頻出公式集
  • 14.2. 経路数への帰着
  • 14.3. 45度回転
  • 14.4. カタラン数 = 数学的問題
• 15. 包除原理 = 包除原理
  • 15.1. 対称性を用いる場合
  • 15.2. DPを用いる場合
  • 15.3. 約数系包除
• 16. 「解けない問題」を見極める
• 17. おわりに