C++で最大1回のスワップで得られる不動点の最大数

問題概要

0 から N-1 までの N 個の要素からなる順列が与えられます。不動点（fixed point）とは、その位置にある値がインデックスと一致する箇所、すなわち arr[i] = i を満たすインデックスのことです。ここで、配列に対して最大 1 回のスワップ（要素の入れ替え）を行えるとします。このとき、得られる不動点の数の最大値を求めてください。

例

入力配列が {0, 1, 2, 3, 4, 6, 5} の場合、答えは 7 になります。

• すべての要素を不動点にするには、6 と 5 を入れ替えます。
• スワップ後は配列全体が不動点となり、不動点の最大値は 7 となります。

アルゴリズム

• 入力配列内の各要素がどの位置にあるかを記録する配列 pos を作成します（pos[値] = インデックス）。
• 続いて、配列を先頭から走査し、以下の場合分けを行います。
  • arr[i] == i の場合：すでに不動点なので、count を 1 増やして次へ進みます。
  • swapped == 0 かつ pos[i] == arr[i] の場合：i 番目の要素と arr[i] の位置にある要素を入れ替えることで、i と arr[i] の両方が不動点になるため、count を 2 増やします。ただし、スワップは最大 1 回しか行えないため、フラグ swapped を立てて管理します。
• 走査が終了した時点で一度もスワップを行っていない場合は、「1 回のスワップで count を 2 増やせるペア」が存在しなかったことを意味します。このとき、不動点でない要素が 2 つ以上残っているのであれば、1 回のスワップでそのうち 1 つを不動点にできるため、count を 1 増やします。

このアルゴリズムの時間計算量は O(N)、空間計算量は O(N) であり、非常に効率的です。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
int getMaximumFixedPoints(int arr[], int n) {
    int i, pos[n], count = 0, swapped = 0;
    for (i = 0; i < n; i++)
    pos[arr[i]] = i;
    for (i = 0; i < n; i++) {
        if (arr[i] == i) {
            count++;
        } else if (swapped == 0 && pos[i] == arr[i]) {
            count += 2;
            swapped = 1;
        }
    }
    if (swapped == 0 && count < n - 1) {
        count++;
    }
    return count;
}
int main() {
    int arr[] = {0, 1, 2, 3, 4, 6, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum value of fixed point = " << getMaximumFixedPoints(arr, n) << endl;
    return 0;
}

出力

上記のプログラムをコンパイルして実行すると、以下の出力が得られます。

Maximum value of fixed point = 7

まとめ

本記事では、最大 1 回のスワップで得られる不動点の最大数を求める問題を解説しました。各要素の位置を事前に記録しておく pos 配列を用意することで、配列を 1 回走査するだけで効率的に答えを導ける点がポイントです。「スワップで 2 つの不動点を作れるケース」と「1 つだけ改善できるケース」を正しく区別することが、この種の問題を解く際の重要な思考プロセスといえます。