分割統治法の核心と逆数対カウント

問題解決の効率性は、基本となる論理構成に基づいています。特に、時間計算量を低下させるための重要な手法として、分割統治法（Divide and Conquer）が挙げられます。このアプローチでは、大規模な問題を独立した小さなサブプロブレムへと分割し、それぞれを再帰的に処理した後に結果を結合します。

この考え方の具体的な適用例の一つが、「逆数対（Inversion Pairs）」の数を求める問題です。配列内で、順序が逆になっている要素のペアの総数をカウントする場合、単純な暴力検索では O(n^2) の計算量がかかります。しかし、マージソートのプロセスを利用して、並列処理を行うことで、計算量を O(n log n) に軽減することが可能です。

標準的なマージソートにおいて、左右の両側に既に並んだ部分（左側 L と右側 R）を用意し、それらをマージする際、R の要素が L の要素よりも小さい場合、L の残りのすべての要素との間に逆数対が存在することになります。

private void countInversions(int[] arr, int low, int mid, int high) {
    int[] leftPart = new int[mid - low + 1];
    int[] rightPart = new int[high - mid];
    
    // サブセットのコピー
    for (int i = 0; i < leftPart.length; i++)
        leftPart[i] = arr[low + i];
    for (int j = 0; j < rightPart.length; j++)
        rightPart[j] = arr[mid + 1 + j];
        
    int i = 0, j = 0, k = low, invCount = 0;
    
    // マージとカウント実行
    while (i < leftPart.length && j < rightPart.length) {
        if (leftPart[i] <= rightPart[j]) {
            arr[k++] = leftPart[i++];
        } else {
            arr[k++] = rightPart[j++];
            invCount += (mid - low + 1) - i; 
        }
    }
    // 余りの処理
    while (i < leftPart.length) arr[k++] = leftPart[i++];
    while (j < rightPart.length) arr[k++] = rightPart[j++];
}

バックトラック法による制約充足問題

一方、バックトラック（Backtracking）法は、解空間全体を探索する際の基本的な策略です。全ての可能性を試行錯誤しながら進み、条件を満たさないと判断された瞬間に引き返して別のパスを探すため、特定の組み合わせや配置問題に対して極めて強力です。

N 皇后問題はこの代表的な事例です。N x N のチェスボード上に N 体の女王を置く際、互いに攻撃し合わない（同一の行、列、または斜め線上に存在しない）配置を見出す必要があります。これは典型的な制約充足問題（CSP）であり、各行ごとに女王を配置しようと試み、現在の状態が既存の配置と衝突しないかチェックすることで探索樹を剪定します。

以下は、再帰的に現在の行を確認し、安全な位置を見つけるロジックを示しています。各ステップで安全性を判定し、失敗した場合は直前の段階に戻ります。

public void searchSolution(int currentRow, boolean[][] board) {
    if (currentRow == board.length) {
        printBoard(board);
        return;
    }

    for (int col = 0; col < board.length; col++) {
        if (isSafe(board, currentRow, col)) {
            board[currentRow][col] = true;
            
            searchSolution(currentRow + 1, board);
            
            board[currentRow][col] = false; // バックトラック
        }
    }
}

private boolean isSafe(boolean[][] b, int r, int c) {
    // 縦および二つの斜めのチェック
    // ...
    return true;
}