C++で解く「美しいアレンジメント II」：隣接差がk種類になる配列の構築

問題の概要

2つの整数 n と k が与えられます。ここでの目標は、1から n までの範囲に含まれる n 個の異なる正の整数からなるリストを構築することです。ただし、そのリストは次のルールを満たす必要があります。

リストを [a1, a2, a3, ..., an] と表すとき、隣接要素の絶対差からなるリスト [|a1 − a2|, |a2 − a3|, |a3 − a4|, ..., |an−1 − an|] には、ちょうど k 種類の一意な整数が含まれていなければなりません。条件を満たす答えが複数存在する場合は、そのうちのどれか 1 つを出力すれば問題ありません。

入出力例

たとえば、入力が n = 3、k = 2 の場合、出力は [1, 3, 2] などになります。[1, 3, 2] は 1 から 3 までの範囲の 3 つの異なる正の整数を含んでおり、隣接要素の差は [2, 1] となって、ちょうど 2 種類（1 と 2）の異なる整数で構成されています。

解法のアプローチ

この問題は、両端から交互に値を取り出していく貪欲法で効率的に解けます。最小値と最大値を交互に並べると、隣接要素の差は (n−1)、(n−2)、… とすべて異なる値になるため、k 種類の差を簡単に実現できます。その後、残りの数を昇順に並べれば、差はすべて 1 になります。

具体的な手順は以下の通りです。

• 結果を格納するための配列 ret を定義します。
• i := 1、j := n と初期化し、i <= j である限りループを回します。
• k > 1 の場合：
  • k が奇数なら i を、偶数なら j を ret に挿入します。
  • k が奇数なら i を 1 増やし、偶数なら j を 1 減らします。
  • k を 1 減らします。
• それ以外の場合は、i を ret に挿入して i を 1 増やします。
• 最後に ret を返します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<int> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}

class Solution {
   public:
   vector<int> constructArray(int n, int k) {
      vector <int> ret;
      for(int i = 1, j = n; i <= j; ){
         if(k > 1){
            ret.push_back(k % 2 ? i : j);
            if(k % 2 == 1){
               i++;
            }else j--;
            k--;
         } else {
            ret.push_back(i++);
         }
      }
      return ret;
   }
};

main(){
   Solution ob;
   print_vector(ob.constructArray(3, 2));
}

入力

3
2

出力

[3, 1, 2]

まとめ

このアルゴリズムは、2つのポインタ i と j を使い、k が 1 になるまで最小値と最大値を交互に配置することで k 種類の差を生成し、残りを連続する数で埋めていくというシンプルな発想に基づいています。時間計算量は O(n)、空間計算量も O(n) と非常に効率的です。なお、本プログラムの出力 [3, 1, 2] も有効な答えの 1 つです（隣接差は [2, 1] となり、2 種類を満たします）。