【C++】n枚のコインを階段状に並べたときの完全な段数を求める方法

n枚のコインを階段状に並べることを考えてみましょう。ここでは、k段目には必ずちょうどk個のコインが置かれるというルールがあります。つまり、与えられたn枚のコインから、何段の「完全な階段」を作ることができるかを求めるのがこの問題です。

例えば、入力が5の場合、出力は2になります。5枚のコインで2段目までの完全な階段を作ることができますが、3段目には3枚のコインが必要なところ、残りは2枚しかないためです。図で表すと次のようになります。

*
**
**

公式による解法

この問題は、1段目からk段目までのコインの総数が 1 + 2 + … + k = k(k+1)/2 となることを利用すると、次の公式によって直接計算することができます。

$$\frac{\sqrt{(8n+1)}-1}{2}$$

この式は、「k(k+1)/2 ≤ n」を満たす最大の整数kを求める二次方程式を解くことで導出できます。ループで1段ずつ数える方法よりも計算量が少なく、大きなnに対しても高速に処理できるのが利点です。

C++での実装例

それでは、実際のコードを見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int arrangeCoins(int n) {
      return (sqrt(8*(long long)n+1)-1)/2;
   }
};
main(){
   Solution ob;
   cout << (ob.arrangeCoins(13));
}

なお、8倍する際にint型のオーバーフローを防ぐため、(long long) にキャストしている点に注目してください。

入力

13

出力

4

この出力は、1 + 2 + 3 + 4 = 10 枚で4段目まで完成しますが、5段目を完成させるには合計15枚が必要であり、13枚では足りないためです。公式に当てはめても (√105 − 1) / 2 ≒ 4.65 となり、小数点以下を切り捨てた4という同じ結果が得られます。