C++で方程式 x + y + z ≤ n を満たす解の個数を求める方法

本記事では、方程式 x + y + z ≤ n を満たす解の個数を求めるアルゴリズムについて解説します。この問題では、変数 x・y・z と上限値 n からなる方程式が与えられ、その条件を満たす解が全体でいくつ存在するかを求めることが課題となります。まずは具体的な入力例と出力例を見てみましょう。

入力: X = 1, Y = 1, Z = 1, n = 1
出力: 4

入力: X = 1, Y = 2, Z = 3, n = 4
出力: 3

この問題は、各変数を式から分離しながら (x, y)、(y, z)、(x, z) のすべての値の組み合わせを走査し、それぞれが方程式を満たしているかどうかを確認するというシンプルな方法で解くことができます。

解法のアプローチ

ここでは、与えられた問題を解くために全探索（ブルートフォース）のアプローチを採用します。

全探索（ブルートフォース）による解法

このプログラムでは、方程式を満たす (x, y)、(y, z)、(x, z) のすべての可能な組み合わせを、ネストされた for ループを用いて走査します。具体的には、ある変数（例えば z）を式から分離し、「z ≤ n − x − y」かつ「0 ≤ z ≤ Z」という条件を満たすかどうかを判定します（他の変数についても同様の処理を行います）。条件を満たす組み合わせが見つかるたびに、答えを格納するカウンターをインクリメントしていきます。

C++ 実装例

#include<bits/stdc++.h>
using namespace std;
int main(){
    int X = 1, Y = 2, Z = 3, n = 4; // x, y, z の上限値と n の値
    int answer = 0; // 解を数えるカウンター変数
    for(int i = 0; i <= X; i++){
        for(int j = 0; j <= Y; j++){
            int temp = (n - i) - j; // temp = n - x - y
            if(temp >= Z){ // n - x - y >= z を満たすなら answer を増やす
                answer++;
            }
        }
    }
    for(int i = 0; i <= X; i++){
        for(int j = 0; j <= Z; j++){
            int temp = (n - i) - j; // temp = n - x - z
            if(temp >= Y){ // n - x - z >= y を満たすなら answer を増やす
                answer++;
            }
        }
    }
    for(int i = 0; i <= Z; i++){
        for(int j = 0; j <= Y; j++){
            int temp = (n - i) - j; // temp = n - y - z
            if(temp >= X){ // n - y - z >= x を満たすなら answer を増やす
                answer++;
            }
        }
    }
    cout << answer << "\n";
}

実行結果

17

プログラムの解説

このプログラムでは、二重ループを用いて 3 組のペア (x, y)、(x, z)、(y, z) の組み合わせをすべて列挙し、残りの変数が「n − a − b ≥ c」という条件を満たすかどうかを順番にチェックしています。条件を満たす組み合わせが見つかるたびにカウントを 1 ずつ増やし、最終的な合計値を出力します。

まとめ

本記事では、方程式 x + y + z ≤ n を満たす解の個数を O(X×Y) の計算量で求める問題を取り上げました。C++ による実装例を通じて、全探索に基づく具体的な解き方を学びました。なお、同じロジックは C、Java、Python など他のプログラミング言語でも同様に実装することが可能です。