すべての部分配列が条件を満たすサイズnの完全配列を見つけるC++プログラム

問題概要

整数 n が与えられます。まず、「良い（good）配列」とは、要素の合計がその配列の長さで割り切れる配列 B のことです。さらに、n 個の要素からなる配列 A が「完全（perfect）」であるとは、A の空でないすべての部分配列が「良い」配列であり、かつ A の各要素が 1 以上 100 以下の範囲に収まっていることを指します。

この問題では、与えられた n に対して、上記の条件を満たす「完全な配列」A を構築することが求められます。

たとえば入力が n = 4 の場合、出力の一例は [7, 37, 79, 49] となります。ただし、これ以外にも条件を満たす配列は無数に存在するため、別の回答でも正解となります。

解法のポイント

一見複雑そうに見えるこの問題ですが、実は非常にシンプルなアイデアで解決できます。それは「すべての要素を同じ値にする」という発想です。

配列の全要素が同じ値 k で構成されている場合、長さ L の任意の部分配列の合計は必ず L × k になります。この値は明らかに L で割り切れるため、どの部分配列も「良い」配列の条件を自動的に満たします。また、値として 1 を選べば、要素が 1〜100 の範囲内にあるという制約も同時にクリアできます。

したがって、答えとしては「1 を n 個並べた配列」を出力するだけで十分です。

アルゴリズムの手順

以下の手順に従って問題を解きます。

i := 0 で初期化し、i < n の間、以下を繰り返す（i を 1 ずつ増加）：
   1 を出力する

C++での実装例

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

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

void solve(int n){
   for(int i=0;i<n;i++){
      cout<<"1"<<", ";
   }
}
int main(){
   int n = 4;
   solve(n);
}

入力

4

出力

1, 1, 1, 1,

計算量について

この解法は配列の各要素を一度だけ処理するため、時間計算量は O(n)、追加のメモリ使用量は O(1) となり、非常に効率的です。n が大きくなっても高速に動作する点が魅力です。