C++で解く子どもの席決め問題：条件を満たす椅子の割り当てアルゴリズム

問題の概要

整数 n が与えられ、サイズ n の配列 A を求めることを考えます。ここには n 個のテーブルがあり、それぞれのテーブルには椅子が4脚ずつ用意されています。椅子には 1 から 4n までの番号が振られています。

番号 a と b（a ≠ b）の椅子に座った2人の子どもは、以下のいずれかの条件を満たすとき、騒ぎ出してしまう（悪さをしてしまう）ことが分かっています。

• gcd(a, b) = 1（a と b が互いに素）である場合
• a が b を割り切る、または b が a を割り切る場合

私たちの目標は、悪さをするペアが一つも発生しないように子どもたちを着席させることです。言い換えると、条件を満たす椅子の割り当て（配列 A）を見つける必要があります。

例として、入力が n = 4 の場合、出力は [14, 10, 12, 8] となります（これ以外の正しい答えも存在します）。

解法のアプローチ

この問題は、実は非常にシンプルな方法で解くことができます。手順は以下の通りです。

for initialize i := (2 * n), when i < 4 * n, update i = i + 2, do:
   print i

なぜこの解法が正しいのか

2n 以上 4n 未満の範囲にある偶数は、すべて共通の約数「2」を持っています。そのため、この中からどの2つの数を選んでも、最大公約数は必ず 2 以上となり、gcd(a, b) = 1 となることはありません。

また、範囲内の最小値 2n を2倍すると 4n となり範囲の外に出るため、ある数が別の数を割り切る関係も成立しません。以上の理由から、この範囲の偶数 n 個を選べば、常に条件を満たす安全な席配置が得られます。

C++による実装例

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

#include <bits/stdc++.h>
using namespace std;
void solve(int n){
   for (int i = (2 * n); i < 4 * n; i = i + 2){
      cout << i << ", ";
   }
}
int main(){
   int n = 4;
   solve(n);
}

入力

4

出力

8, 10, 12, 14,

このように、n = 4 の場合は 8、10、12、14 が出力され、これらの椅子に子どもを座らせれば、誰も悪さをすることなく平和に席につくことができます。計算量は O(n) と効率的で、大きな n に対しても高速に動作します。