自動 DP
概要
文字から正方行列への写像 $ f とベクトル $ u, vが存在し、与えられた文字列 $ S = S_1 S_2 \dots S_N に対し問題の答えが $ u^T f(S_1) f(S_2) \dots f(S_N) vと書けるような DP の問題がしばしば存在します。
これら $ f,u,v を愚直解によって得られた短い文字列に対する答えから自動で推定できます。
例題
解答
入力が 'a', 'b' からなる文字列、数え上げ問題なのでなんとなく線形性がありそう、本手法を使うチャンスです。
まずは BFS のライブラリを利用して愚直解を書きます（'a', 'b' の代わりに '0', '1' だとします）：
code:naive.cpp
mint naive(const string& s) {
int n = sz(s);
if (n == 0) return 0;
using T = string;
vector<T> res;
rep(i, sz(s) - 1) {
string t = s.substr(0, i);
t += s.substr(i + 2);
res.push_back(t);
}
}
return res;
};
auto reachable_set = get_reachable_set(s, nxt, INF);
return sz(reachable_set);
}
これをテンプレに貼り付け、文字種が 2 なので embed_coefs(2) を実行します。
すると次のような出力が得られました：
code:output.cpp
constexpr int DIM = 12;
constexpr int COL = 2;
{{0,1,0,0,0,0,0,0,0,0,0,0},{0,0,0,1,0,0,0,0,0,0,0,0},{0,0,0,0,0,1,0,0,0,0,0,0},{0,0,0,0,0,0,0,1,0,0,0,0},{0,0,0,0,0,0,0,0,0,1,0,0},{0,0,0,0,0,0,0,0,0,0,1,0},{0,0,0,1,0,0,-1,0,0,0,1,0},{0,0,0,0,0,0,-3,0,1,0,3,0},{0,0,0,1,0,0,-2,0,0,0,2,0},{0,0,0,1,0,0,-2,0,1,0,1,0},{0,0,0,1,0,0,-3,0,1,0,2,0},{0,-1,0,0,0,1,0,0,0,1,0,0}},
{{0,0,1,0,0,0,0,0,0,0,0,0},{0,0,0,0,1,0,0,0,0,0,0,0},{0,0,0,0,0,0,1,0,0,0,0,0},{0,0,0,0,0,0,0,0,1,0,0,0},{0,0,0,1,0,0,-1,0,1,0,0,0},{0,0,0,0,0,0,0,0,0,0,0,1},{0,0,0,0,0,0,0,1,1,0,-1,0},{0,0,0,1,0,0,-3,0,3,0,0,0},{0,0,0,0,0,0,-2,1,2,0,0,0},{0,0,-1,0,1,0,0,0,0,0,0,1},{0,0,0,0,0,0,-1,1,2,0,-1,0},{0,0,0,0,0,0,-1,0,1,0,1,0}} };
VTYPE vecQDIM = { 0,1,1,2,1,1,2,3,3,1,3,1 }; これを solve 内の指定された場所に貼り付けそのまま提出します。
問題なく AC することができました。
提出
応用
ラグランジュ補間で重み付き DP にも対応可能。
FPS の分割統治積で多状態 DP にも対応可能。
テンソルを復元することで木 DP にも対応可能。
係数を 0/1 に制限することでオートマトンを復元可能。
max-plus 代数を考えることで最適化系の DP にも部分的に対応可能。
その他細かい変種が多数。
他の使用例
あまりにも多いので、フォルダ内検索して出てきたファイル一覧と解法メモをそのまま貼っておきます。
一部は元ポストの先に提出コードへのリンクがあります。
RUPC2024 Day1, D - 2xL Minesweeper（自動耳DP, 重ね合わせ）
Tenka1 Programmer Beginner Contest 2019, C - Stones（自動max-plus耳DP）
ABC007, D - 禁止された数字（自動耳DP）
ABC029, D - 1（自動耳DP, メモ化）
ABC050, D - Xor Sum（自動耳DP）
ABC104, D - We Love ABC（自動耳DP, スパース, 重ね合わせ）
ABC114, C - 755（自動耳DP）
ABC122, D - We Like AGC（自動耳DP, 重ね合わせ）
ABC129, C - Typical Stairs（自動耳DP）
ABC129, E - Sum Equals Xor（自動耳DP）
ABC135, D - Digits Parade（自動耳DP）
ABC138, F - Coincidence（自動耳DP）
ABC149, F - Surrounded Nodes（自動木DP）
ABC150, E - Change a Little Bit（自動重み付きDP）
ABC154, E - Almost Everywhere Zero（自動耳DP）
ABC155, E - Payment（自動max-plus耳DP）
ABC155, E - Payment（自動耳DP, 貪欲）
ABC169, F - Knapsack for All Subsets（自動重み付き状態DP, 目視エスパー）
ABC181, B - Trapezoid Sum（自動重み付きDP(2種), 2変数ラグランジュ補間）
ABC181, D - Hachi（自動耳DP）
ABC186, D - Sum of difference（自動重み付きDP, ソート）
ABC189, D - Logical Expression（自動耳DP, 単因子標準形）
ABC189, D - Logical Expression（自動耳DP）
ABC194, C - Squared Error（自動重み付きDP, ラグランジュ補間, CRT）
ABC195, C - Comma（自動桁DP(N以下), 乱択, スパース）
ABC200, F - Minflip Summation（自動耳DP, 重ね合わせ, 行列累乗）
ABC207, F - Tree Patrolling（自動2乗の木DP）
ABC211, C - chokudai（自動耳DP, 乱択）
ABC214, F - Substrings（自動耳DP）
ABC220, D - FG operation（自動耳DP, 非埋め込み）
ABC220, F - Distance Sums 2（自動全方位木DP）
ABC223, G - Vertex Deletion（自動木DP）
ABC224, F - Problem where +s Separate Digits（自動重み付きDP）
ABC230, E - Fraction Floor Sum（自動商列挙）
ABC235, F - Variety of Digits（自動耳DP, 非埋め込み）
ABC237, F - ｜LIS｜ = 3（自動耳DP, 乱択, 重ね合わせ, スパース）
ABC242, C - 1111gal password（自動耳DP）
ABC246, Ex - 01？ Queries（自動耳DP, 圧縮行列積-セグ木）
ABC246, Ex - 01？ Queries（自動耳DP, 行列積-セグ木）
ABC248, F - Keep Connect（自動状態DP, 重ね合わせ）
ABC256, F - Cumulative Cumulative Cumulative Sum（自動重み付きDP, 行列積-セグ木）
ABC269, Ex - Antichain（自動木状態DP, StaticTopTree）
ABC287, F - Components（自動2乗の木DP, 非埋め込み）
ABC287, F - Components（自動2乗の木DP）
ABC288, F - Integer Division（自動耳DP）
ABC295, F - substr = S（自動桁DP(N以下), 乱択, 非埋め込み）
ABC297, C - PC on the Table（自動耳DP, 貪欲, 遅延延長）
ABC297, D - Count Subtractions（自動ユークリッドDP）
ABC301, D - Bitmask（自動耳DP, 貪欲）
ABC308, E - MEX（自動耳DP）
ABC312, G - Avoid Straight Line（自動木DP）
ABC313, E - Duplicate（自動耳DP）
ABC317, F - Nim（自動桁DP(N以下, Mの倍数)）
ABC336, C - Even Digits（自動桁DP(N以下), K番目→二分探索）
ABC336, E - Digit Sum Divisible（自動状態桁DP(N以下, Mの倍数), CRT）
ABC338, G - evall（自動耳DP）
ABC340, G - Leaf Color（自動木耳DP, 木の座圧）
ABC349, C - Airport Code（自動耳DP, 非埋め込み, ピボット指定）
ABC351, G - Hash on Tree（自動重み付き木DP, StaticTopTree(2属性), ラグランジュ補間）
ABC351, G - Hash on Tree（自動重み付き木DP, StaticTopTree(2属性)）
ABC356, D - Masked Popcount（自動耳DP）
ABC359, G - Sum of Tree Distance（自動重み付き木DP, 木の座圧(重み付き), 接続2部グラフ(重み付き)）
ABC369, D - Bonus EXP（自動max-plus重み付きDP, 線形重み）
ABC369, D - Bonus EXP（自動max-plus重み付きDP）
ABC375, D - ABA（自動耳DP, 非埋め込み, ピボット指定）
ABC378, F - Add One Edge 2（自動全方位木DP）
ABC378, F - Add One Edge 2（自動木DP）
ABC379, E - Sum of All Substrings（自動耳DP, 多倍長整数, 分割統治積）
ABC387, C - Snake Numbers（自動桁DP(N以下), 非埋め込み）
ABC397, B - Ticket Gate Log（自動耳DP, 貪欲）
ABC399, F - Range Power Sum（自動重み付きDP, ラグランジュ補間）
ABC403, G - Odd Position Sum Query（自動重み付きDP, 行列積-動的セグ木）
ABC406, C - ~（自動耳DP, 階差）
ABC406, E - Popcount Sum 3（自動状態DP, メモ化, 分母除去）
ABC406, E - Popcount Sum 3（自動状態DP, メモ化, 相似変換）
ABC406, E - Popcount Sum 3（自動状態桁DP(N以下)）
ABC407, C - Security 2（自動耳DP, 貪欲, 前計算）
ABC418, D - XNOR Operation（自動耳DP）
ABC418, G - Binary Operation（自動耳DP, 非埋め込み, 右端固定, 貪欲）
ABC423, E - Sum of Subarrays（自動重み付きDP, 行列積-累積可逆積）
ABC425, G - Sum of Min of XOR（BinaryTrie, 自動耳DP）
ABC426, D - Pop and Insert（自動max-plus耳DP）
ABC429, C - Odd One Subsequence（自動重み付きDP, 多項式補間, CRT）
ABC429, F - Shortest Path Query（自動max-plus耳DP, max-plus行列積セグ木）
ABC429, G - Sum of Pow of Mod of Linear（自動ModSum, 素因数分解, 2元1次不定方程式の解の数え上げ, CRT）
ABC437, D - Sum of Differences（自動重み付き耳DP, ソート）
ABC456, C - Not Adjacent（自動耳DP）
ABC456, D - Not Adjacent 2（自動耳DP）
AGC001, B - Mysterious Light（自動ユークリッドDP）
AGC005, B - Minimum Sum（自動デカルト木DP）
AGC005, B - Minimum Sum（自動重み付きデカルト木DP）
AGC014, D - Black and White Tree（自動木DP）
AGC015, D - A or...or B Problem（自動耳DP, CRT）
AGC015, D - A or...or B Problem（自動耳DP, 単因子標準形）
AGC015, D - A or...or B Problem（自動耳DP, 答えの改変）
AGC015, D - A or...or B Problem（自動耳DP, 遅延除算）
AGC022, E - Median Replace（自動耳DP, 重ね合わせ）
AGC027, E - ABBreviate（自動耳DP, 動的BFS）
ARC025, D - コンセント（自動耳DP, 行列積-セグ木, クエリ先読み, 座標圧縮）
ARC028, C - 高橋王国の分割統治（自動全方位木DP, 部分木）
ARC110, B - Many 110（BMBM, 自動耳DP）
ARC110, E - Shorten ABC（自動耳DP, BFS）
ARC116, B - Products of Min-Max（自動重み付きDP(部分列), ソート, ラグランジュ補間）
ARC121, F - Logical Operations on Tree（自動木DP）
ARC122, A - Many Formulae（自動重み付きDP）
ARC124, E - Pass to Next（自動重み付きDP, ラグランジュ補間）
ARC126, E - Infinite Operations（実験エスパー, 自動重み付きDP, 行列積-セグ木, クエリ先読み, 座標圧縮）
ARC127, A - Leading 1s（自動耳DP, メモ化）
ARC130, A - Remove One Character（自動耳DP, 非埋め込み）
ARC133, D - Range XOR（自動耳DP）
ARC136, A - A ↔ BB（自動耳DP, 貪欲, 前計算, 多倍長整数, 分割統治積）
ARC142, D - Deterministic Placing（自動木DP）
ARC157, C - YY Square（自動格子耳DP）
ARC173, A - Neq Number（自動桁DP(N以下), K番目→二分探索）
ARC173, A - Neq Number（自動耳DP, CRT, メモ化, K番目→二分探索）
ARC191, B - XOR = MOD（自動耳DP, K番目→二分探索）
ARC192, A - ARC Arc（自動耳DP）
ARC193, B - Broken Wheel（自動耳DP）
ARC201, C - Prefix Covering（自動木耳DP, トライ木）
ARC208, C - Mod of XOR（自動耳DP, スパース, CRT）
第6回日本情報オリンピック 予選, F - 通学経路（自動格子耳DP）
第9回日本情報オリンピック 予選, E - 通勤経路（自動格子DP(向き依存)）
第11回日本情報オリンピック 予選, D - パスタ（自動耳DP, 重ね合わせ）
第11回日本情報オリンピック 予選, F - ジグザグ数（自動桁DP(L以上R以下, Mの倍数)）
第13回日本情報オリンピック 予選, D - 部活のスケジュール表 （自動耳DP）
第15回日本情報オリンピック 本選, B - スタンプラリー 2（自動耳DP, 場合分け, 1つ抜き累積積）
Chokudai SpeedRun 001, B - 和（自動重み付きDP）
Educational DP Contest, H - Grid 1（自動格子耳DP）
Educational DP Contest, I - Coins（自動重み付き状態DP）
Educational DP Contest, P - Independent Set（自動木DP）
Educational DP Contest, S - Digit Sum（自動状態DP, メモ化, スパース剰余）
Educational DP Contest, V - Subtree（自動全方位木DP）
FPS 24 題, A - お菓子（自動状態DP, 重ね合わせ, 分割統治積）
FPS 24 題, D - 数列 2（自動ヒストグラムDP(長さ固定, 単調増加, 末項固定)）
FPS 24 題, F - 色紙（自動耳DP, 重ね合わせ, 行列累乗）
Typical DP Contest, A - コンテスト（自動状態DP, 目視エスパー）
Typical DP Contest, E - 数（自動状態DP, メモ化, スパース剰余）
Typical DP Contest, P - うなぎ（自動2乗の木DP, 非埋め込み）
Typical DP Contest, P - うなぎ（自動2乗の木DP）
Typical DP Contest, S - マス目（自動耳DP, 乱択, 重ね合わせ, スパース）
アルゴリズムと数学 演習問題集, 019 - Choose Cards 1（自動耳DP）
アルゴリズムと数学 演習問題集, 031 - Taro's Vacation（自動max-plus重み付きDP, 線形重み）
アルゴリズムと数学 演習問題集, 031 - Taro's Vacation（自動max-plus重み付きDP）
アルゴリズムと数学 演習問題集, 073 - Sum of Maximum（自動重み付きDP）
新エディタテストコンテスト, B - 部分木サイズ（自動木DP）
東京工業大学プログラミングコンテスト2015, F - レシート（自動max-plus耳DP）
競プロ典型 90問, 005 - Restricted Digits（★7 自動桁DP(N以下, Mの倍数), 非埋め込み, BMBM）
競プロ典型 90問, 022 - Cubic Cake（自動ユークリッドDP(3数)）
競プロ典型 90問, 039 - Tree Distance（★5 自動木DP, CRT）
競プロ典型 90問, 039 - Tree Distance（★5 自動木DP, 答えの改変, 基底の乱択）
競プロ典型 90問, 039 - Tree Distance（★5 自動木DP, 遅延除算, 基底の乱択）
競プロ典型 90問, 073 - We Need Both a and b（★5 自動木耳DP）
競技プログラミングの鉄則 演習問題集, A25 - Number of Routes（自動格子耳DP）
競技プログラミングの鉄則 演習問題集, A27 - Calculate GCD（自動ユークリッドDP）
競技プログラミングの鉄則 演習問題集, B27 - Calculate LCM（自動ユークリッドDP）
競技プログラミングの鉄則 演習問題集, B37 - Sum of Digits（自動耳DP, メモ化）
CODE FESTIVAL 2014 予選B, D - 登山家（自動デカルト木DP）
CODE FESTIVAL 2015 予選A, B - とても長い数列（自動重み付きDP）
Donuts プロコンチャレンジ2014, B - 7th（自動桁DP(N以下, Mの倍数)）
START88, 1-3 - Minimize the Bits（自動耳DP, 遅延延長）
START91, 1-4 - XOR & Sum（自動耳DP）
START118, 1-4 - Is it uniquely decodable（自動耳DP, 前計算）
START201, 1 - Huge Grid (Easy Version)（自動耳DP）
START205, 1 - Unreachable（自動耳DP）
START217, 4 - Tree Counting（自動2乗の木DP）
Educational Round50, C - Classy Numbers（自動耳DP, メモ化）
XX Open Cup, Grand Prix of Tokyo, J - Median Replace Hard（自動耳DP, ピボット埋め込み, BFS）
Good Bye 2021：2022 is NEAR, B - Mirror in the String（自動耳DP, 目視エスパー）
Library Checker, Point Set Range Composite（自動重み付きDP(2種), 行列積-セグ木）
Library Checker, Min of Mod of Linear（自動max-plus ModSum）
Library Checker, Sum of Floor of Linear（自動FloorSum）
Library Checker, Point Set Tree Path Composite Sum (Fixed Root)（自動重み付き木DP, StaticTopTree(2属性), 接続2部グラフ）
Library Checker, Tree Path Composite Sum（自動重み付き全方位木DP, 接続2部グラフ）
OUPC2024：Day2 北海道大学セット, F - Blessing of Heaven（自動重み付きDP, 乱択, 非埋め込み, ラグランジュ補間）
TUATPC 2025 Spring, E - ngng 数（自動桁DP(N以下), 乱択, スパース）
東京農工大学MCCプログラミングコンテスト2023, E - TUAT String 3（自動耳DP, 重ね合わせ）
筑波大学プログラミングコンテスト2024, E - Homologous Recombination（自動重み付きDP, 行列積-セグ木）
KMC(Kusirattyo Mini Contest), E - Rock (Easy)（自動耳DP, 重ね合わせ）
KMC(Kusirattyo Mini Contest), G - Rock (Hard)（自動耳DP, 重ね合わせ, 行列累乗）
MoguCoderContest 02, 7 - BAN AI（自動max-plus耳DP）
SKT(Summary of Kusirattyo Tweeted), B - most length（自動重み付きDP, 階差, 右端固定）
The Gray ― Beginner's Algorithmic Competition Vol. 3, E - Sum of Sums of Restricted Sequences（自動ヒストグラムDP, 重ね合わせ）
The Gray ― Beginner's Algorithmic Competition Vol. 3, E - Sum of Sums of Restricted Sequences（自動重み付きDP, ラグランジュ補間）
take44444 Beginner Contest 001, 1 - xxxx00000（自動max-plus耳DP）
お茶コン OchaCon01, 2 - (^^)（自動耳DP）
お茶コン02, 2 - ABAB（自動耳DP(部分列), 乱択）
お茶コン02, 4 - 区間和の和（自動重み付きDP, 行列積-セグ木）
お茶コン03, 5 - XOR Combination（自動耳DP）
しょぼんの橙おめでとうコンテスト, E - Maximize XOR（自動耳DP, CRT）
不快or没問コンテスト2, 5 - Odd Operator（自動耳DP, 非埋め込み, 行列積-セグ木）
Mojacoder, Mod Sum（自動商列挙）
Mojacoder, Divisors（自動商列挙）
Mojacoder, Multiset's Subset's Product Sum Easy（自動重み付きDP）
Mojacoder, Multiset's Subset's Product Sum Hard（自動重み付き状態DP）
Mojacoder, Prefix Permutation（自動状態DP, 重ね合わせ）
Mojacoder, Range Multiplication Sum（自動重み付きDP, 行列積-セグ木）
Mojacoder, Easy Random Product（自動耳DP）
Mojacoder, Random Product（自動耳DP, bitDP）
Mojacoder, Simple Mod Sum（自動商列挙）
Mojacoder, Sum of Averages (subset)（自動重み付き状態DP, 分割統治積）
Mojacoder, Add or Multiply Game（自動耳DP）
Mojacoder, 3 7 10（自動耳DP,乱択）
Advent Calendar Contest 2018, J - Noelちゃんと木遊び（自動max-plus木DP）
Advent Calendar Contest 2025, B - Range Flipping Game（自動耳DP, 延長）
Advent Calendar Contest 2025, D - Max Weighted Floor of Linear（自動max-plus FloorSum, 目視エスパー）
Advent Calendar Contest 2025, S - Christmas Tree Coloring（自動木DP, スパース）
CPCTF 2025：PPC, H - 0→1（自動耳DP）
MMA Contest 016, B - 偶数判定！Nafmoくん（自動耳DP）
MMA Contest 016, F - MMA文字列2（自動耳DP, スパース）
MMA Contest 017, D - MORE! JUMP! MORE!（自動重み付きDP）
QUPC2024, F - Snake Path（自動状態DP, mll）
QUPC2024, H - Linear Reversi（自動耳DP, 前計算）
traP 作問ハッカソンコンテスト 001, N - Fragile Multiples of 11（自動耳DP, メモ化）
traP 作問ハッカソンコンテスト 002(day2), B - Initial fare（自動木DP）
yukicoder April Fool Contest 2025(writer, tester), B - TCP ソート（自動耳DP, 貪欲, 多倍長整数）
yukicoder contest MMA Contest 020, K - INCREASE decrease（上位と下位で独立, 自動耳DP, 乱択）
yukicoder contest YNUCPC Contest 2, N - popcount & sum (Hard)（自動状態DP, ラグランジュ補間(多項式復元, 等比数列)）
作問ハッカソンコンテスト 003 Day1, C - AAB Game（自動耳DP）
作問ハッカソンコンテスト 003 Day1, D - Distance Sum of Large Tree（自動木DP, 行列累乗）
問題文一行コンテスト, E - Substring Sum（自動耳DP, 乱択, 部分列）
第2回 岩井星人アンソロジープログラミングコンテスト Div.1, A - Make 81181819 with only 0, 1, or 8（自動耳DP, スパース, 逐次復元）
第2回 岩井星人アンソロジープログラミングコンテスト Extra, F - 岩井ツリーグラフ （自動木DP, 行列累乗）
第2回 岩井星人アンソロジープログラミングコンテスト Extra, F - 岩井ツリーグラフ （自動重み付きDP, 多項式補間）
第2回緑以下コンテスト, L - 列辞書順列列（自動重み付きDP, 行列積-セグ木, 目視エスパー）
第3回緑以下コンテスト, H - Botaoshi（自動耳DP, 重ね合わせ）
緑以下コンテスト Extra, C - 列辞書順列（自動重み付きDP, 行列積-セグ木, FindSequenceFunction）
緑以下コンテスト Extra, F - Defect-free Rectangles（下辺を固定, 自動重み付きデカルト木DP）
yukicoder contest 99, B - SUPER HAPPY DAY（自動状態DP, メモ化, mll）
yukicoder contest 239, C - Point Add and Array Add（自動重み付き耳DP, 行列積-双対セグ木）
yukicoder contest 242, B - 三目並べ（自動耳DP）
yukicoder contest 253, E - 桁和の桁和（自動耳DP, 非埋め込み, 重ね合わせ）
yukicoder contest 258, F - Earthquake Safety（自動木DP）
yukicoder contest 261, D - Runs in Subsequences（自動耳DP(部分列), 乱択, スパース）
yukicoder contest 261, D - Runs in Subsequences（自動耳DP, スパース）
yukicoder contest 267, D - Multiplication -2（自動耳DP）
yukicoder contest 276, B - Random Array Score（自動重み付きDP, 目視エスパー）
yukicoder contest 284, B - Kindness（自動耳DP, メモ化）
yukicoder contest 314, B - +-＊（自動重み付きDP）
yukicoder contest 322, F - Alone 'a'（自動重み付きDP）
yukicoder contest 343, C - Rational Approximation（自動SBTDP）
yukicoder contest 344, M - ８（自動耳DP, メモ化, 答えで二分探索）
yukicoder contest 353, F - Digits Filling for All Substrings（自動耳DP）
yukicoder contest 356, B - Tunnel（自動max-plus耳DP）
yukicoder contest 357, G - Path Factory（自動木DP, スパース）
yukicoder contest 358, E - AND Sequence（自動状態DP, メモ化）
yukicoder contest 359, E - ±2^k operations（自動耳DP, 前計算）
yukicoder contest 366, C - Sum of Diff（自動重み付きDP）
yukicoder contest 368, C - MEX Game（度数分布, 自動重み付きDP）
yukicoder contest 368, D - Mod, Sum, Sum, Mod（自動商列挙, 非埋め込み）
yukicoder contest 369, B - Concon Substrings (COuNt Version)（自動耳DP, 重ね合わせ）
yukicoder contest 375, E - Lights Out on Christmas Tree（自動木耳DP）
yukicoder contest 376, G - Products on Tree（自動木DP）
yukicoder contest 377, D - Re：010（自動耳DP, 重ね合わせ）
yukicoder contest 386, B - Prohibit Three Consecutive（自動耳DP, 重ね合わせ）
yukicoder contest 388, F - Carry X Times（自動状態DP, メモ化, mll）
yukicoder contest 394, D - Path to Integer（自動重み付き木DP）
yukicoder contest 396, G - SUM AND XOR on Tree（自動木耳DP, bit毎に独立）
yukicoder contest 410, J - Stripes（自動状態DP, 分割統治積）
yukicoder contest 415, E - Count 01（自動耳DP, テンソル積-セグ木）
yukicoder contest 415, E - Count 01（自動耳DP, 圧縮行列積-セグ木）
yukicoder contest 415, E - Count 01（自動耳DP, 行列積-セグ木）
yukicoder contest 424, E - FizzBuzz Letter Counting（自動耳DP, メモ化, 行列累乗-ベクトル積）
yukicoder contest 426, D - Sum of Subarray of Subsequence（自動ヒストグラムDP）
yukicoder contest 426, D - Sum of Subarray of Subsequence（自動重み付きDP）
yukicoder contest 430, F - Counting and Deleting（自動耳DP, テンソル積-セグ木, 区間からの写像）
yukicoder contest 430, F - Counting and Deleting（自動耳DP, 圧縮行列積-セグ木, 区間からの写像）
yukicoder contest 430, F - Counting and Deleting（自動耳DP, 行列積-セグ木, 区間からの写像）
yukicoder contest 442, D - A + B Problem（自動耳DP）
yukicoder contest 442, E - -1 Subsequence（自動max-plus重み付きDP）
yukicoder contest 443, F - NOT FOUND 404 Again（自動耳DP, メモ化）
yukicoder contest 450, C - Sigma Popcount Problem（自動耳DP）
yukicoder contest 451, E - Product on Tree（自動重み付き全方位木DP）
yukicoder contest 451, E - Product on Tree（自動重み付き木DP）
yukicoder contest 456, C - Maximize eval（自動耳DP, 遅延延長）
yukicoder contest 467, A - Weird Parentheses Game（自動括弧列DP）
yukicoder contest 473, H - Periodic Alternating Subsequence（自動耳DP, 行列累乗）
yukicoder contest 474, F - Parse AND OR Affection（自動耳DP, 行列積-セグ木）
yukicoder contest 479, C - Count 8 Included Numbers (Hard)（自動耳DP）
yukicoder contest 479, D - Multiplication 8 1（自動耳DP, 行列累乗, 重ね合わせ）
yukicoder contest 479, H - Multiplication 8 2（主客転倒, 畳込み, 自動耳DP, 左右からの累積積）
yukicoder contest 483, C - Make Smaller Popcount（自動耳DP, 単因子標準形）
yukicoder contest 486, A - One-time Changed Formula（自動耳DP）
yukicoder contest 489, B - Partial Complement Tree（自動木DP）
yukicoder contest 489, C - Caesar Shift Game（自動耳DP, 延長）
元ポスト
など