C++で解く「K逆ペア配列」問題 ― 動的計画法による効率的な解法

問題概要

2つの整数 n と k が与えられます。1 から n までの数字をそれぞれ1回ずつ使って構成される配列のうち、逆ペア（転倒ペア）がちょうど k 個含まれるものが何通り存在するかを求めてください。ここで、逆ペアとは配列中の i 番目と j 番目の要素について、i < j かつ a[i] > a[j] が成り立つペアのことを指します。答えは非常に大きな値になる可能性があるため、10⁹ + 7 で割った余りを返します。

例えば、n = 3、k = 1 の場合、出力は 2 になります。これは [1, 3, 2] と [2, 1, 3] の2つの配列が、それぞれちょうど1つの逆ペアを持つためです。

解法のアプローチ

この問題は動的計画法（DP）を用いて効率的に解くことができます。dp[i][j] を「長さ i の配列のうち、逆ペアがちょうど j 個含まれるものの個数」と定義します。長さ i の配列に最大値 i を挿入する位置によって、新たに 0 ～ i-1 個の逆ペアが生じるため、単純な漸化式では計算量が膨大になります。そこで累積和（スライディングウィンドウ）の考え方を活用し、漸化式を変形することで O(n × k) の計算量で求められます。

具体的な手順は以下の通りです。

• サイズ (n + 1) × (k + 1) の2次元配列 dp を定義する
• dp[0][0] := 1 と初期化する
• i を 1 から n まで繰り返す：
  • dp[i][0] := 1 とする
  • j を 1 から k まで繰り返す：
    • dp[i][j] := dp[i][j - 1] + dp[i - 1][j]
    • dp[i][j] := dp[i][j] mod m
    • j >= i の場合：
      • dp[i][j] := (dp[i][j] - dp[i - 1][j - i] + m) mod m
• dp[n][k] を返す

実装例（C++）

以下にC++による実装を示します。

#include <bits/stdc++.h>
using namespace std;
const int m = 1e9 + 7;
class Solution {
public:
    int kInversePairs(int n, int k) {
        vector < vector <int> > dp(n + 1, vector <int>(k + 1));
        dp[0][0] = 1;
        for(int i = 1; i <= n; i++){
            dp[i][0] = 1;
            for(int j = 1; j <= k; j++){
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
                dp[i][j] %= m;
                if(j >= i){
                    dp[i][j] = (dp[i][j] - dp[i - 1][j - i] + m) % m;
                }
            }
        }
        return dp[n][k];
    }
};
main(){
    Solution ob;
    cout << (ob.kInversePairs(4,2));
}

入力

4
2

出力

5

n = 4、k = 2 の場合、逆ペアをちょうど2つ持つ配列が5通り存在するため、出力は 5 となります。