数値 n の分割における重みの種類数を求めるC++プログラム

整数 n が与えられたとき、n を正整数の非増加列(前の要素が後の要素以上となる並び)に分解することを考えます。このとき、各要素の合計は必ず n と一致します。分割の「重み」とは、その分割の中で最初の要素と同じ値を持つ要素の個数のことです。例えば、分割 [1, 1, 1, 1, 1] の重みは 5、分割 [5, 5, 3, 3, 3] の重みは 2、そして分割 [9] の重みは 1 となります。この記事では、n のあらゆる分割において現れうる「異なる重み」の種類数を求める方法を解説します。

例として、入力が n = 7 の場合を見てみましょう。このときの出力は 4 になります。これは、次の 4 つの分割に対応する重みが存在するためです。

• [7] → 重み 1
• [3, 3, 1] → 重み 2
• [2, 2, 2, 1] → 重み 3
• [1, 1, 1, 1, 1, 1, 1] → 重み 7

解法のアプローチ

この問題は一見複雑そうに見えますが、実は非常にシンプルな数式で O(1) で解くことができます。

なぜ n / 2 + 1 で求まるのか

重み w が取り得る値について考えてみます。

• 重みが k になるとき、分割の先頭から k 個の要素がすべて同じ値である必要があります。つまり、n を k で割った商が先頭の値になり、余りはそれ以降の要素で構成されます。
• 重みが 1 になるケースは常に存在します(例:[n])。

ここで重要なのは、重みが n / 2 より大きくなるケースです。重みが n / 2 + 1 以上になるには、先頭の値が 1 でなければなりません。しかし、先頭が 1 なら全要素が 1 になるしかなく、その場合の重みは必然的に n 自身になります。したがって、実際に存在しうる重みは「1 から n / 2 までの n / 2 種類」に「n 自身」を加えた、合計 n / 2 + 1 種類となります。

結論

return (n / 2 + 1)

実装例

以下にC++での具体的な実装を示します。

#include <bits/stdc++.h>
using namespace std;
int solve(int n){
    return (n / 2 + 1);
}
int main(){
    int n = 7;
    cout << solve(n) << endl;
}

入力

7

出力

4

このように、n = 7 の場合、7 / 2 + 1 = 4 となり、期待通りの結果が得られました。計算量は定数時間なので、n がどれほど大きくても瞬時に答えを求められるのがこの解法の魅力です。