C++で合計がnとなる連続する整数列の個数を数えるプログラム

問題概要

ある整数 n が与えられたとき、合計がちょうど n になる「正の連続する整数からなるリスト」の個数を求めます。

例えば、入力が n = 15 の場合、出力は 4 になります。条件を満たすリストは次の4つです。

• [1, 2, 3, 4, 5]
• [4, 5, 6]
• [7, 8]
• [15]

解法のアプローチ(スライディングウィンドウ)

この問題はスライディングウィンドウ(尺取り法)を使うことで効率的に解けます。区間 [begin, end] 内の合計を管理しながら、ウィンドウを伸縮させていくのがポイントです。

具体的な手順は以下の通りです。

1. begin := 1、end := 1、x := (n + 1) / 2 で初期化します。
2. sum := 0 とします。
3. end <= x の間、以下を繰り返します。
   • sum := sum + end としてウィンドウを右に広げます。
   • sum >= n の間、以下を繰り返します。
     • sum == n であれば、カウントを1増やします。
     • sum := sum - begin として先頭を取り除き、begin を1増やします。
   • end を1増やします。
4. 最後に count + 1 を返します。これは単一要素のリスト [n] 自身を答えに含めるためです。

なお、探索範囲を (n + 1) / 2 までに絞れるのは、2つ以上の連続する正の整数の和が n になるとき、その最大値は高々 (n+1)/2 であるためです。これにより無駄な探索を省けます。

C++での実装例

#include <iostream>
using namespace std;

int solve(int n) {
    int begin = 1, end = 1, x = (n + 1) / 2, count = 0;
    long int sum = 0;
    while (end <= x) {
        sum += end;
        while (sum >= n) {
            if (sum == n)
                count++;
            sum -= begin;
            begin++;
        }
        end++;
    }
    return count + 1;
}

main() {
    cout << (solve(15));
}

入力

15

出力

4

計算量

このアルゴリズムの時間計算量は O(n)、空間計算量は O(1) です。各要素の追加・削除がそれぞれ高々1回ずつ行われるため、全体でも線形時間で処理が完了します。