C++で解く「美しいアレンジメント」問題 ― バックトラッキングによる実装

問題の概要

1からNまでのN個の整数があるとします。「美しいアレンジメント（美しい順列）」とは、これらのN個の数字をすべて使って構成される配列のうち、配列内のi番目の位置（1 <= i <= N）について、次のいずれかの条件が成り立つものと定義されます。

• i番目の位置にある数が、iで割り切れる。
• iが、i番目の位置にある数で割り切れる。

具体例：N = 2 の場合

入力が2のとき、答えは2になります。

1つ目の美しいアレンジメント [1, 2]

• 1番目の位置（i=1）にある数は1で、1はi（=1）で割り切れます。
• 2番目の位置（i=2）にある数は2で、2はi（=2）で割り切れます。

2つ目の美しいアレンジメント [2, 1]

• 1番目の位置（i=1）にある数は2で、2はi（=1）で割り切れます。
• 2番目の位置（i=2）にある数は1で、i（=2）は1で割り切れます。

解法のアプローチ：バックトラッキング

この問題は、すべての順列を試しながら、条件を満たさない組み合わせを途中で切り捨てる「バックトラッキング（探索の枝刈り）」によって効率的に解くことができます。具体的には、以下の手順に従います。

1. visited配列・end・pos を引数に取る再帰メソッド solve() を定義します。pos の初期値は1です。
2. pos が end + 1 になった場合、すべての位置が埋まったことを意味するため、ans を1増やして return します。
3. i を1から end までループさせます。
   • i が未使用で、「pos が i で割り切れる」または「i が pos で割り切れる」場合：
     • i を使用済みとしてマークします。
     • solve(visited, end, pos + 1) を再帰呼び出しします。
     • 探索を戻した後、i を未使用に戻します（バックトラック）。
4. メインメソッドでは、ans を0で初期化し、visited 配列を作成して solve(visited, N, 1) を呼び出し、最後に ans を返します。

割り切りの条件を満たさない数字はその時点で配置を諦めるため、無関係な順列の生成を大幅に省略でき、単純な全列挙よりも高速に動作します。

C++による実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    int ans;
    void solve(vector<bool>& visited, int end, int pos = 1){
       if(pos == end + 1){
          ans++;
          return;
       }
       for(int i = 1; i <= end; i++){
          if(!visited[i] && (pos % i == 0 || i % pos == 0)){
             visited[i] = true;
             solve(visited, end, pos + 1);
             visited[i] = false;
          }
       }
   }
    int countArrangement(int N) {
       ans = 0;
       vector<bool> visited(N);
       solve(visited, N);
       return ans;
    }
};
main(){
    Solution ob;
    cout << (ob.countArrangement(2));
}

入力

2

出力

2

計算量について

最悪の場合の時間計算量は O(N!) ですが、割り切り条件による枝刈りが働くため、実際の探索空間は大きく削減されます。使用しているのは visited 配列と再帰スタックのみなので、空間計算量は O(N) です。