C++で数をa=c・b=dとなる4つの部分に分割する方法の総数を求める

問題の概要

整数 n が与えられたとき、この数を4つの部分(a、b、c、d)に分割する方法のうち、a = c かつ b = d を満たす組み合わせが何通りあるかを求めます。

例として n = 20 の場合を考えてみましょう。答えは4通りになり、具体的には以下の組み合わせが該当します。

• [1, 1, 9, 9]
• [2, 2, 8, 8]
• [3, 3, 7, 7]
• [4, 4, 6, 6]

解法のアプローチ

c = a、d = b であるため、この問題は実質的に「a + b = n / 2 となる正整数のペア (a, b) の個数」を求める問題に帰着できます。これにより、次のようなシンプルなルールが導かれます。

• n が奇数の場合： 2(a + b) = n を満たす整数の組は存在しないため、答えは 0 になります。
• n が4で割り切れる場合： 答えは n / 4 − 1 になります。4つすべてが同じ値になってしまうケースを除外する必要があるためです。
• 上記以外(偶数だが4では割り切れない)の場合： 答えは n / 4 になります。

C++での実装例

#include <iostream>
using namespace std;
int countPossiblity(int num) {
    if (num % 2 == 1)
        return 0;
    else if (num % 4 == 0)
        return num / 4 - 1;
    else
        return num / 4;
}
int main() {
    int n = 20;
    cout << "Number of possibilities: " << countPossiblity(n);
}

出力結果

Number of possibilities: 4

まとめ

この問題は、条件式を整理することで剰余演算による場合分けだけで答えを導き出せる好例です。ループや再帰を使わず O(1) の計算量で処理できるため、非常に効率的なアルゴリズムと言えます。