C++でグローバル反転とローカル反転の数が一致するか判定する方法

長さNの順列A（[0, 1, ..., N-1]を並び替えた配列）を考えてみましょう。グローバル反転（大域転倒）とは、0 <= i < j < N かつ A[i] > A[j] を満たすインデックスのペア(i, j)の総数を指します。一方、ローカル反転（局所転倒）とは、0 <= i < N かつ A[i] > A[i+1]、つまり隣接する2つの要素が逆順になっている箇所の数です。

この問題では、グローバル反転の総数とローカル反転の総数が一致する場合にのみtrueを返す必要があります。例えば、入力が [1,0,2] の場合、ローカル反転は「1と0」の1箇所だけであり、グローバル反転も同じく1つだけなので、答えはtrueとなります。

解法のアプローチ

ここで重要なポイントがあります。すべてのローカル反転は、必ずグローバル反転にも含まれるということです。したがって、両者の数が等しくなるのは、「ローカル反転ではないグローバル反転（距離2以上離れた要素間の反転）が1つも存在しない」場合に限られます。

この性質を利用すると、以下の手順でO(N)の計算量で効率的に判定できます。

• maxVal := -1、n := 配列Aのサイズとして初期化する
• iを0からn-3までループさせる
  • maxVal := max(A[i], maxVal) として、これまでの最大値を更新する
  • もし maxVal > A[i + 2] ならばfalseを返す（非ローカルなグローバル反転が存在することを意味する）
• ループが完了すればtrueを返す

それでは、以下の実装例を見て理解を深めましょう。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    bool isIdealPermutation(vector<int>& A) {
        int maxVal = -1;
        int n = A.size();
        for(int i = 0; i < n - 2; i++){
            maxVal = max(A[i], maxVal);
            if(maxVal > A[i + 2])
            return false;
        }
        return true;
    }
};
main(){
    vector<int> v = {1,0,2};
    Solution ob;
    cout << (ob.isIdealPermutation(v));
}

入力

[1,0,2]

出力

1