ABC034 C問題（経路）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）034 C問題をC++で解いてみました。ABC034は、2016年3月12日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

C問題 経路（Difficulty : 1440（参考値））

問題の詳細は、リンク先をご覧ください。

ABC034 C問題 経路

組み合わせの個数を求めます。AtCoder Problems による Difficulty は 1440（参考値）でした。

解答案

高校数学の組み合わせでも出題される典型問題です。経路の個数は、$(H-1)+(W-1)$ 個の移動の中から、$(H-1)$ 個の縦方向の移動を選ぶ組み合わせ個数となります。

つまり、以下の値を求める必要があります。

$$_{H+W-2}C_{H-1} = \frac{(H+W-2)!}{(H-1)! (W-1)!}$$

値が大きくなるため、1,000,000,007 で割った余り（剰余）を求めます。

C++ プログラム例（ABC034C）

組み合わせの個数を返す関数 nCr を用意します。剰余付きの累乗関数 power も使います（7ー17行目）。これは、以前から自作のライブラリとして用意していました。

• $n!$ を配列 fact に計算して格納しておきます（40ー43行目）。
• $1/n!$ を配列 fact_i に計算して格納しておきます。フェルマーの小定理を使って、剰余を取る $1000000007-2$ 乗を計算します（44ー47行目）。
• 配列 fact と fact_i を用いて、目的の値をもとめます（26、27行目）。

後は、上記の関数を呼び出すだけです。h と w は、入力時に 1 を引いています。以下が、C++プログラムです。

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

typedef unsigned long long int ull;
#define MOD 1000000007

ull power(ull n, ull p, ull mod)
{
	if (p == 0) {
		return 1;
	}
	if (p % 2 == 0) {
		ull t = power(n, p / 2, mod);
		return t * t % mod;
	}
	return (n * power(n, p - 1, mod)) % mod;
}

vector<ull> fact;
vector<ull> fact_i;

ull nCr(ull n, ull r, ull mod)
{
	ull result;

	result = (fact[n] * fact_i[r]) % mod;
	result = (result * fact_i[n - r]) % mod;

	return result;
}

int main()
{
	ull h, w;
	cin >> h >> w;
	--h;
	--w;

	fact.resize(h + w + 1);
	fact[0] = 1;
	for (ull i = 1; i <= h + w; ++i) {
		fact[i] = i * fact[i - 1] % MOD;
	}
	fact_i.resize(h + w + 1);
	for (ull i = 0; i <= h + w; ++i) {
		fact_i[i] = power(fact[i], MOD - 2, MOD);
	}

	cout << nCr(h + w, h, MOD) << endl;

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

最後に

この問題を通じて、組み合わせ計算に関するコードを整理することができました。

引き続き ABC の問題を紹介していきます。