互いに値の異なる $n$ 個の要素からなる数列があります。
転倒数が $K$ 以下となるように並べる方法は何通りありますか。
・$1 \le n \le 300$
・$0 \le K \le n(n-1)/2$
与えられる数列の値は全て異なり、今回は大小関係にのみ興味があるので、[0, n) の数列が来ていると考えることができる。
要するに、与えられる数列は必要がない。
ここで、数字を小さいものから順に挿入していくことで数列を作るようにする。
一例をあげる。$n = 5$ のとき。
0 ... 0 を挿入した。 転倒数 +0
1 0 ... 1 を挿入した。 転倒数 +1 (1, 0) ... 1の挿入場所に応じて、転倒数 +0 から +1 までありえる。
1 2 0 ... 2 を挿入した。 転倒数 +1 (2, 0) ... 2の挿入場所に応じて、転倒数 +0 から +2 までありえる。
1 2 0 3 ... 3 を挿入した。 転倒数 +0 ... 3の挿入場所に応じて、転倒数 +0 から +3 までありえる。
1 2 4 0 3 ... 4 を挿入した。 転倒数 +2 (4, 0), (4, 3) ... 4の挿入場所に応じて、転倒数 +0 から +4 までありえる。
そこで、数字 $i$ を挿入することによって、転倒数が $k$ から $k+j$ に変化することを表現する次のような動的計画法が書ける。
#include <iostream>
#include <algorithm>
using namespace std;
constexpr int mod = int(pow(10, 9)) + 7;
int main(void) {
int n, K; scanf("%d%d", &n, &K);
// dp[転倒数 k] := パターン数
vector<int> dp(K+1);
dp[0] = 1;
for(int i=0; i<n; ++i) { // 数字 i を挿入する
vector<int> ndp(K+1);
for(int j=0; j<=i; ++j) { // 数字 i を挿入することで増やせる転倒数
for(int k=0; k+j<=K; ++k) { // 数字 i を挿入する前の転倒数
// 転倒数は k => k+j に変化する
ndp[k+j] += dp[k];
ndp[k+j] %= mod;
}
}
dp = ndp;
}
int res = 0;
for(int k=0; k<=K; ++k) {
res += dp[k];
res %= mod;
}
printf("%d\n", res);
return 0;
}
だが、計算量が $O(n^{2}K)$ で間に合わない。
計算量を落とす前にひとまず、「値を色んな添字に渡すのではなく、色んな添字から貰うように変形する」ことを考える。
$k$ が $[0, K-j]$ で動いていて、このとき $k + j = x$ とすると $x$ は $[j, K]$ を動くことになる。
この $x$ を新たな $k$ にして書き直す。
#include <iostream>
#include <algorithm>
using namespace std;
constexpr int mod = int(pow(10, 9)) + 7;
int main(void) {
int n, K; scanf("%d%d", &n, &K);
// dp[転倒数 k] := パターン数
vector<int> dp(K+1);
dp[0] = 1;
for(int i=0; i<n; ++i) {
vector<int> ndp(K+1);
for(int j=0; j<=i; ++j) {
for(int k=j; k<=K; ++k) {
ndp[k] += dp[k-j];
ndp[k] %= mod;
}
}
dp = ndp;
}
int res = 0;
for(int k=0; k<=K; ++k) {
res += dp[k];
res %= mod;
}
printf("%d\n", res);
return 0;
}
ndp[k] は dp[k-0] + dp[k-1] + ... + dp[k-i]
すなわち、$[k-i, k]$ の範囲の dp の和であり、ここは累積和で高速化が図れる。
つまり、
acc[k] := [0, k) の dp の和
とすると、
ndp[k] = "[0, k+1) の dp の和" - "[0, k-i) の dp の和"
= acc[k+1] - acc[k-i]
となる。
#include <iostream>
#include <algorithm>
using namespace std;
constexpr int mod = int(pow(10, 9)) + 7;
int main(void) {
int n, K; scanf("%d%d", &n, &K);
// dp[転倒数 k] := パターン数
vector<int> dp(K+1);
dp[0] = 1;
for(int i=0; i<n; ++i) {
vector<int> acc(K+2);
for(int k=0; k<=K; ++k) {
acc[k+1] = acc[k] + dp[k];
acc[k+1] %= mod;
}
vector<int> ndp(K+1);
for(int k=0; k<=K; ++k) {
ndp[k] += acc[k+1];
ndp[k] %= mod;
ndp[k] -= acc[max(0, k-i)];
ndp[k] %= mod;
ndp[k] += mod;
ndp[k] %= mod;
}
dp = ndp;
}
int res = 0;
for(int k=0; k<=K; ++k) {
res += dp[k];
res %= mod;
}
printf("%d\n", res);
return 0;
}
(ΦωΦ)＜おしまい