C++でグリッド上の点から別の点への移動経路の総数を求める方法

この記事では、グリッド上の2つの固定された点の間を移動する経路の総数を求める問題を取り上げます。具体的には、点Aはグリッドの左上、点Bは右下に固定されており、AからBへ移動する方法が何通りあるかを計算します。

問題の入出力例

入力 : N = 5
出力 : 252

入力 : N = 4
出力 : 70

入力 : N = 3
出力 : 20

この問題は、シンプルな観察によって数式として定式化できます。

解法のアプローチ

グリッド上をAからBへ移動するためには、右方向にちょうどn回、下方向にちょうどn回移動する必要があります。つまり、合計2n回の移動のうち、どの順番で右方向・下方向に進むかを選ぶ組み合わせの総数を求めればよいことになります。

これは数学で有名な二項係数であり、次の公式で表されます。

C(2n, n) = (2n)! / (n! × n!)

C++での実装例

#include<bits/stdc++.h>

using namespace std;
int fact(int n){ // 階乗を計算する関数
    if(n <= 1)
        return 1;
    return n * fact(n-1);
}
int main() {
    int n = 5; // 与えられたn
    int answer = 0; // 答えを格納する変数
    answer = fact(n+n); // 2*n の階乗を計算
    answer = answer / (fact(n) * fact(n)); // (2*n)! / (n! × n!)
    cout << answer << "\n";
}

出力

252

コードの解説

このコードでは、まず再帰的な階乗関数 fact() を定義し、それを使って組み合わせの公式 (2n)! / (n! × n!) を計算しています。AからBへの移動には、右方向にn回・下方向にn回の合計2n回の操作が必要となるため、これらの操作の並べ方の総数、すなわち2n個の中からn個の場所を選ぶ組み合わせ C(2n, n) が答えになります。

計算量についても確認しておきましょう。階乗の計算にO(n)かかるため、プログラム全体の計算量はO(n)程度です。動的計画法を用いるO(n²)のアプローチと比べて非常に効率的ですが、nが大きくなると階乗の値が急激に増大してオーバーフローする恐れがあるため、競技プログラミングなどでは適切なデータ型の選択やmod演算の活用を検討してください。

まとめ

この記事では、グリッド上のある点から別の点への移動経路の数を求める問題について解説しました。組み合わせの公式 C(2n, n) を使うことで、シンプルかつ高速に答えを求められることを学びました。同じロジックはC、Java、Pythonなど他の言語でも同様に実装できます。この記事が皆さんのお役に立てば幸いです。