【C++】石を渡すことができる最大回数を求めるアルゴリズム

整数 n が与えられた場面を考えてみましょう。Amalは Bimal に対して何度でも石を渡すことができますが、ある手番で k 個の石を渡した場合、その直後の手番で同じく k 個の石を渡すことはできません。つまり、連続する2つの手番では必ず異なる個数の石を渡す必要があるというルールです。

この条件下で、Amalが Bimal に石を渡せる回数は最大で何回になるのかを求めるのが本記事の目的です。

具体例

入力が n = 4 の場合を考えます。

「1個 → 2個 → 1個」の順で石を渡せば、合計4個を3回の手番で渡すことができます。これ以上回数を増やすことはできないため、出力は 3 となります。

解法のアプローチ

この問題を効率的に解くには、次の式を用います。

return (n * 2 + 1) / 3;

なぜこの式で求まるのか？

ポイントは、「1個」と「2個」を交互に渡すのが最も効率的であることです。

• 3回の手番（1個＋2個＋1個）で合計4個の石を消費できる
• つまり、おおよそ3個の石につき2回の手番を確保できる
• 端数の調整を行うと、答えは (2n + 1) / 3（小数点以下切り捨て） となる

この式により、ループ処理などを一切使わず O(1) の定数時間で答えを算出できます。

C++による実装例

以下に、実際のC++コードを示します。

#include <bits/stdc++.h>
using namespace std;

int solve(int n){
    return (n * 2 + 1) / 3;
}

int main(){
    int n = 4;
    cout << solve(n) << endl;
}

入力

4

出力

3

まとめ

「直前の手番と同じ個数は渡せない」という制約がある場合、1個と2個を交互に渡す戦略が最適となります。そのため、答えはシンプルに (2n + 1) / 3 の一つの式で表現でき、非常に高速に求解できる問題です。