C++で連続する2を使わずに1と2でスコアに到達する方法の数を求める

バッティングのスコア(ラン数)が与えられます。バッツマンは1球につき1ランまたは2ランのいずれかしか獲得できないという条件のもとで、そのスコアに到達することを目標とします。ただし重要な制約として、2ランを連続して取ることはできません。例えばスコア6に到達する場合、「1+2+1+2」のようにランを取ることはできますが、「2+2+1+1」のように連続する2を含む方法は認められません。

入出力例

例1

入力:

score=4

出力:

連続する2を使わずに1と2でスコア4に到達する方法の数: 4

説明:

スコア4に到達する方法は以下の4通りです:
1+1+1+1、1+1+2、1+2+1、2+1+1

例2

入力:

score=5

出力:

連続する2を使わずに1と2でスコア5に到達する方法の数: 6

説明:

スコア5に到達する方法は以下の6通りです:
1+1+1+1+1、2+1+1+1、1+2+1+1、1+1+2+1、1+1+1+2、2+1+2

アプローチ

ここでは、直前のランが2であったかどうかを記録するフラグを使用します。直前が2だった場合、次のランは必ず1となり、そうでなければ1と2のどちらも選択できます。

• 整数変数 score を用意します。
• フラグ変数 check を初期値 false で用意します。
• 関数 ways_reach_score(int score, bool check) は、連続する2を使わずに1と2でスコアに到達する方法の数を返します。
• 初期カウントを0とします。
• スコアが0になった場合は、1つの有効な組み合わせが完成したことを意味するため、1を返します。
• check が false(直前のランが1)で、現在のスコアが1より大きい場合は、次に1または2を選べるため、count = ways_reach_score(score - 1, false) + ways_reach_score(score - 2, true) となります。
• それ以外の場合(直前のランが2)は、次のランは1のみ選択できるため、count = ways_reach_score(score - 1, false) となります。
• 最終的に count に方法の総数が格納されるので、これを結果として返します。

コード例

#include <bits/stdc++.h>
using namespace std;
int ways_reach_score(int score, bool check){
    int count = 0;
    if (score == 0){
        return 1;
    }
    if (check == false && score > 1){
        count += ways_reach_score(score - 1, false) + ways_reach_score(score - 2, true);
    } else {
        count += ways_reach_score(score - 1, false);
    }
    return count;
}
int main(){
    int score = 4;
    bool check = false;
    cout<<"連続する2を使わずに1と2でスコアに到達する方法の数: "<<ways_reach_score(score, check);
    return 0;
}

出力

上記のコードを実行すると、以下の出力が得られます。

連続する2を使わずに1と2でスコア4に到達する方法の数: 4

計算量について

この再帰的な実装は、各ステップで最大2つの再帰呼び出しを行うため、最悪の場合 O(2^n) の指数時間計算量となります。スコアが大きくなるケースでは、メモ化(動的計画法)を導入することで計算量を O(n) に削減でき、より効率的に答えを求められます。