C++で2つの数列を厳密に増加させるための最小スワップ回数を求めるアルゴリズム

同じ非ゼロの長さを持つ2つの整数列 A と B が与えられているとします。ここで、A[i] と B[i] の要素を入れ替える(スワップする)ことができます。ただし、スワップできるのは、それぞれの数列において同じインデックス位置にある要素同士のみです。いくつかのスワップを行った後、A と B の両方が厳密に増加する(strictly increasing)状態にしたいと考えます。このとき、両方の数列を厳密に増加させるために必要な最小のスワップ回数を求めるのがこの問題です。

問題の例

例として、入力が A = [1,3,5,4]、B = [1,2,3,7] の場合を考えてみましょう。このとき答えは 1 になります。A[3] と B[3] を1回スワップすると、A = [1,3,5,7]、B = [1,2,3,4] となり、どちらの数列も厳密に増加している状態になるからです。

解法のアプローチ(動的計画法)

この問題は動的計画法(DP)を用いて効率的に解くことができます。各インデックス i について、「その位置でスワップした場合の最小コスト」と「スワップしなかった場合の最小コスト」の2つの状態を管理します。

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

• n を配列 A のサイズとし、それぞれサイズ n の2つの配列 swapCnt と noSwapCnt を用意します。
• swapCnt[0] に 1 を、noSwapCnt[0] に 0 を設定します。
• i を 1 から n - 1 まで繰り返します。
  • swapCnt[i] := n、noSwapCnt[i] := n で初期化します。
  • A[i] > A[i - 1] かつ B[i] > B[i - 1] の場合(スワップせずにそのまま維持できる場合):
    • noSwapCnt[i] := noSwapCnt[i - 1]
    • swapCnt[i] := swapCnt[i - 1] + 1
  • A[i] > B[i - 1] かつ B[i] > A[i - 1] の場合(スワップによって条件を満たせる場合):
    • swapCnt[i] := min(swapCnt[i], 1 + noSwapCnt[i - 1])
    • noSwapCnt[i] := min(swapCnt[i - 1], noSwapCnt[i])
• 最後に swapCnt[n - 1] と noSwapCnt[n - 1] の小さい方を返します。

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int minSwap(vector<int>& A, vector<int>& B) {
        int n = A.size();
        vector <int> swapCnt(n), noSwapCnt(n);
        swapCnt[0] = 1;
        noSwapCnt[0] = 0;
        for(int i = 1; i < n; i++){
            swapCnt[i] = n;
            noSwapCnt[i] = n;
            if(A[i] > A[i - 1] && B[i] > B[i - 1]){
                noSwapCnt[i] = noSwapCnt[i - 1];
                swapCnt[i] = swapCnt[i - 1] + 1;
            }
            if(A[i] > B[i - 1] && B[i] > A[i - 1]){
                swapCnt[i] = min(swapCnt[i], 1 + noSwapCnt[i - 1]);
                noSwapCnt[i] = min(swapCnt[i - 1], noSwapCnt[i]);
            }
        }
        return min(swapCnt[n - 1], noSwapCnt[n - 1]);
    }
};
main(){
    vector<int> v1 = {1,3,5,4};
    vector<int> v2 = {1,2,3,7};
    Solution ob;
    cout << (ob.minSwap(v1, v2));
}

入力

[1,3,5,4]
[1,2,3,7]

出力

1

計算量について

このアルゴリズムの時間計算量は O(n)、空間計算量も O(n) です。各インデックスごとの状態遷移を一度の走査で処理できるため、非常に効率的な解法となっています。