C++で階段の段数を求める方法｜二分探索によるO(log N)の効率的な解法

問題概要

この問題では、階段の建設に使えるレンガの数を表す整数 N が与えられ、そのレンガで何段の階段を作れるかを求めます。

階段は与えられたレンガを使って下から順に組み上げていきます。各段は直前の段より1個多くのレンガを必要とし、最初の段は2個のレンガで作られます。つまり、1段目＝2個、2段目＝3個、3段目＝4個という具合です。残りのレンガが次の段を積むのに足りなくなった時点で構築を終え、それまでに完成した段数が答えとなります。

入出力例

入力

N = 40

出力

7

動作の解説

N = 40 のとき、段を積むごとにレンガの消費数と残数は次のように変化します。

8段目を作るには9個のレンガが必要ですが、残りは5個しかありません。したがって、これ以上段を積むことはできず、答えは7段となります。

解法アプローチ

1. ループによるシンプルな解法

最も素直な解法は、必要レンガ数を2から始めて1個ずつ増やしながらループを回し、累計使用数がNを超えた時点で停止して、その直前の段数を返す方法です。

この手法はシンプルで分かりやすい一方、段数に比例して繰り返しが増えるため、時間計算量は O(N) となります。

2. 総和公式と二分探索による高速な解法

k段の階段に必要なレンガの総数は、等差数列の和の公式から次のように表せます。

2 + 3 + … + (k + 1) = k(k + 3) / 2

この累積必要数はkの増加に対して単調に増えていくため、「k(k + 3) / 2 ≤ N」を満たす最大のkを二分探索で効率よく絞り込めます。実装では探索を整理するため T = 2N と置き、「m × (m + 1) ≤ T」となる最大のmを求めたうえで答えを導出しています。これにより、時間計算量を O(log N) まで抑えられます。

C++での実装例

以下は、二分探索を用いた解法の動作を示すプログラムです。

#include <iostream>
using namespace std;

int findStairCount(int T){
    int low = 1;
    int high = T/2;
    while (low <= high) {
        int mid = (low + high) / 2;
        if ((mid * (mid + 1)) == T)
            return mid;
        if (mid > 0 && (mid * (mid + 1)) > T && (mid * (mid - 1)) <= T)
            return mid - 1;
        if ((mid * (mid + 1)) > T)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;
}

int main(){
    int N = 60;
    int stepCount = findStairCount(2*N);
    if (stepCount != -1)
        stepCount--;
    cout<<"作成できる階段の段数："<<stepCount;
    return 0;
}

出力

作成できる階段の段数：9

この例では N = 60 が与えられており、2 + 3 + … + 10 = 54 となるので9段まで積めますが、10段目に必要な11個のレンガは残っていないため、答えは9段となります。

計算量のまとめ

・時間計算量：O(log N)（二分探索の反復回数に依存）
・空間計算量：O(1)（追加のメモリは不要）