はじめに

この問題は、俗に挿入 DP と言われる動的計画法を用いる問題です。また、この問題をより簡単にした問題として、EDPC-T Permutation という問題があります。もしこの問題が分からなかった場合、まずは先述の問題を考えてみると良いでしょう。

解説

動的計画法で解きます。 \(\mathrm{dp}[i][j][k][l] = (\)\(i\) 番目まで決めた時、現在の類似度が \(j\) であって、\(A_i\) より大きいものが \(k\) 個、\(B_i\) より大きいものが \(l\) 個残っているものの個数\()\) と定義します。

この動的計画法を愚直に行うと、状態数が \(\mathrm{O}(N^4)\) 、遷移が \(\mathrm{O}(N^2)\) であり到底実行時間制限に間に合いません。

ここで、貰う DP を考えます。このとき、\(\mathrm{dp}[i][j][k][l]\) への遷移元は \(\mathrm{dp}[i-1][j]\) のある長方形区間及び \(\mathrm{dp}[i-1][j-1]\) のある長方形区間の和として表されます。

これを用いると、二次元累積和を用いることで遷移を \(\mathrm{O}(1)\) に高速化できます。以上の工夫により、この問題を \(\mathrm{O}(N^4)\) で解くことができました。

また、配る DP でも解くことができます。遷移先が長方形区間になっていることを用いると、二次元 imos 法を使えば良いです。

貰う DP による実装例(c++)