C++で解く「美しい配列」問題：等差条件を回避する順列の構築アルゴリズム

固定した値 N に対して、配列 A が「美しい（beautiful）」とは、A が 1, 2, ..., N の順列であり、かつ次の条件を満たすことを意味します。

• 任意の i < j について、i < k < j を満たし、かつ A[k] * 2 = A[i] + A[j] となる k は存在しない。

言い換えると、インデックスの順序において、両端の要素の平均値が中央の要素と一致するような3つの要素の組み合わせが一切現れてはいけない、という制約です。N が与えられたとき、この条件を満たす美しい配列 A を1つ構築するのが本問題の目的です。

たとえば入力が 5 の場合、出力は [3,1,2,5,4] のようになります。

解法のアプローチ

この問題は、配列を「奇数」と「偶数」に分けながら段階的に拡張していく手法で解くことができます。具体的な手順は以下の通りです。

• 配列 ret を作成し、初期値として 1 を挿入します。

• ret のサイズが N 未満である間、次の処理を繰り返します。

  • 新しい配列 temp を用意します。

  • ret の各要素 x に対して、x * 2 - 1（奇数）が N 以下であれば temp に挿入します。

  • 続けて、各要素 x に対して、x * 2（偶数）が N 以下であれば temp に挿入します。

  • ret を temp で更新します。

• 最終的な ret を結果として返します。

なぜこの手法が機能するのか

条件式 A[k] * 2 = A[i] + A[j] が成立するには、A[i] + A[j] が偶数である必要があります。つまり、A[i] と A[j] が同じ偶奇（パリティ）を持つ場合にしか成り立ちません。

上記の構成法では、配列の前半にすべての奇数を、後半にすべての偶数を配置します。そのため、奇数領域と偶数領域をまたぐ i < j のペアでは、2つの値の和が必ず奇数となり、条件を満たすことができません。一方、奇数同士・偶数同士のペアについては、各ステップで元の配列の相対的な順序と構造が保たれるため、帰納的に条件が維持されます。この性質により、全体として美しい配列が得られます。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Solution {
    public:
    vector<int> beautifulArray(int N) {
        vector<int> ret;
        ret.push_back(1);
        while(ret.size() < N){
            vector<int> temp;
            for(int i = 0; i < ret.size(); i++){
                if(ret[i] * 2 - 1 <= N) temp.push_back(ret[i] * 2 - 1);
            }
            for(int i = 0; i < ret.size(); i++){
                if(ret[i] * 2 <= N) temp.push_back(ret[i] * 2);
            }
            ret = temp;
        }
        return ret;
    }
};
main(){
    Solution ob;
    print_vector(ob.beautifulArray(5));
}

入力

5

出力

[1,5,3,2,4]

この実装では、反復のたびに配列のサイズがほぼ2倍に増加していくため、全体の計算量は O(N log N) 程度に収まります。そのため、比較的大きな N に対しても効率的に美しい配列を生成できる点が大きな特徴です。