競技プログラミングにおける挿入DP問題まとめ

挿入DP

• 順列などに挿入することで遷移を進めていくDP

問題

• HR Permutation Happiness
• SRM694 Div2 Hard UpDownNess 解説
• CSA Restricted Permutations
• TDPC 文字列 解説1 解説2 解説3
• CF429 On the Bench
• yukicoder No.93 ペガサス 解説1 解説2
• http://kmjp.hatenablog.jp/search?q=挿入DP
• SRM582 Div1 Med ColorfulBuilding 解説1 解説2 解説3
• TCO2018 Gangsters 解説
• AOJ 座席 (Seats) 解説

挿入DPとは逆に抜いていくDP（抜去DP）

• ARC097 Sorted and Sorted 解説

【発展的話題】挿入DPの更新最適化

挿入DPの時に掛け算を遅延評価して、上手くやる

rep(i, 0, N) rep(k, 0, N) rep(col, 0, N) {
    dp[i + 1][k][col] = dp[i][k][col] * (k + 1);
    if(c[i] == col) dp[i + 1][k][c[i]] += dp[i][k][col];
    else dp[i + 1][k + 1][c[i]];
}

を掛け算を遅延評価することでO(N^3)からO(N^2)へ削減可能

• これ 解説1 解説2 解説3