C++で最初のN個の自然数を差Dとなる2つの集合に分割できるか判定する方法

問題概要

この問題では、2つの整数 N と D が与えられます。求めるのは、1からNまでの最初のN個の自然数を、合計値の差がちょうど D となる2つの集合に分割できるかどうかを判定することです。

具体例で理解する

入力: N = 5, D = 3

出力: Yes(可能)

説明:

1, 2, 3, 4, 5 の中から、
set1 = {1, 2, 3}、set2 = {4, 5} と分けると、その差は 3 になります。
{4+5} − {1+2+3} = 9 − 6 = 3

解法のポイント:数学的なアプローチ

この問題は、実際に集合を組み立てる前に、数学的な計算だけで判定できます。

まず、N個の自然数全体の総和は次の公式で表されます。

sum(s1) + sum(s2) = (n × (n+1)) / 2

一方、問題の条件より次の式が成り立ちます。

sum(s1) − sum(s2) = D

この2つの式を辺々加えると、

2 × sum(s1) = ((n × (n+1)) / 2) + D

ここで重要なのは、sum(s1) は整数でなければならないため、右辺が偶数である必要があるという点です。つまり、「N個の自然数の総和 + D」が偶数の場合に限り、条件を満たす分割が存在します。

C++での実装例

上記の考え方を実装したプログラムが以下の通りです。

#include <iostream>
using namespace std;
bool isSetPossible(int N, int D) {
   int set = (N * (N + 1)) / 2 + D;
   return (set % 2 == 0);
}
int main() {
   int N = 10;
   int D = 7;
   cout<<"Creating two set from first "<<N<<" natural number with difference "<<D<<" is ";
   isSetPossible(N, D)?cout<<"possible":cout<<"not possible";
   return 0;
}

実行結果

Creating two set from first 10 natural number with difference 7 is possible

まとめ

この問題の鍵となるのは、等差数列の総和公式と連立方程式の考え方です。「(N × (N+1) / 2 + D) が偶数であるか」という条件一つで判定できるため、集合を実際に構築する必要がなく、O(1) の計算量で非常に高速に答えを求められます。競技プログラミングでも頻出するテクニックなので、ぜひ覚えておきましょう。