Pythonで解く：分配ルールに従ってキャンディを配れる子どもの人数を求めるプログラム

ここでは、k個のキャンディを子どもたちに分配する問題を考えます。ただし、分配には以下のルールがあります。

• i番目の子どもは、ちょうど i² 個のキャンディを受け取る
• i番目の子どもは、1番目から i−1 番目までの子ども全員に配り終わるまで、キャンディを受け取れない
• i番目の子どもが i² 個を受け取れない場合、その分配は無効とみなされる

例えば、入力が k = 20 の場合、出力は 3 になります。1番目の子どもが1個、2番目の子どもが 2² = 4個、3番目の子どもが 3² = 9個を受け取り、合計14個が消費されます。4番目の子どもには 4² = 16個が必要ですが、残りは6個しかないため、この分配は無効です。したがって、キャンディを配れるのは3人までということになります。

解き方のアプローチ

この問題は二分探索（バイナリサーチ）を使うことで効率的に解けます。ポイントは、n番目までの子どもに配るために必要なキャンディの総数が、平方数の和の公式 n(n+1)(2n+1)/6 で計算できることです。この値が k を超えない最大の n を二分探索で見つけます。

• left := 0、right := k として初期化する
• right − left > 1 の間、次の手順を繰り返す
  • mid := (left + right) / 2 の切り捨て値とする
  • mid × (mid + 1) × (2 × mid + 1) / 6 の切り捨て値が k より大きければ right := mid、そうでなければ left := mid とする
• right × (right + 1) × (2 × right + 1) ≤ k × 6 であれば right を返す
• それ以外の場合は left を返す

この方法により、計算量は O(log k) となり、k が非常に大きな値でも高速に答えを求められます。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

def solve(k):
   left = 0
   right = k
   while (right - left > 1):
      mid = (left + right) // 2
      if (mid * (mid + 1) * (2 * mid + 1) // 6 > k):
         right = mid
      else:
         left = mid
   if (right * (right + 1) * (2 * right + 1) <= k * 6):
      return right
   return left

k = 20
print(solve(k))

入力

20

出力

3

このように、平方数の和の公式と二分探索を組み合わせることで、「何人目までキャンディを配れるか」という問題をシンプルかつ効率的に解くことができます。