アルゴリズムと数学 演習問題集 019 - Choose Cards 1

記事概要

アルゴリズムと数学 演習問題集 019 - Choose Cards 1のとりあえず動くコードと説明．
https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_s

注意

アルゴリズム初心者が書いています．時間内の動作は確認してますが、必ずしも最適解ではないです．

とりあえずコード

019_main.cpp

//////////////////////////
// 019 - Choose Cards 1 //
//////////////////////////

#include <iostream>
#include <vector>

#define ULL unsigned long long

using std::vector;


ULL combination(ULL n, ULL r) {
	if (n < r) {
		return 0;
	}

	r = std::min(r, n - r);
	std::vector<std::vector<ULL>> v(n + 1, std::vector<ULL>(r + 1, 0));

	for (auto i = 0ULL; i < (ULL)v[0].size(); ++i) {
		v[i][i] = 1;
	}

	for (auto i = 0ULL; i < (ULL)v.size(); ++i) {
		v[i][0] = 1;
	}

	/*
	for (int i = 0; i < v.size(); ++i) {
		for (int j = 0; j < v[0].size(); ++j) {
			std::cout << v[i][j] << " ";
		}
		std::cout << std::endl;
	}
	*/

	for (auto i = 1ULL; i < (unsigned long long)v.size(); ++i) {
		for (auto j = 1ULL; j < std::min(i, (unsigned long long)v[0].size()); ++j) {
			v[i][j] = v[i - 1][j - 1] + v[i - 1][j];
		}
	}

	/*
	for (int i = 0; i < v.size(); ++i) {
		for (int j = 0; j < v[0].size(); ++j) {
			std::cout << v[i][j] << " ";
		}
		std::cout << std::endl;
	}
	*/

	return v[n][r];
}

int main(void)
{
	//============================= 入力 =============================//
	unsigned long long N;
	std::cin >> N;

	unsigned long long num_redCards = 0;
	unsigned long long num_yellowCards = 0;
	unsigned long long num_blueCards = 0;

	for (auto i = 0ULL; i < N; ++i) {
		int num;
		std::cin >> num;

		switch (num) {
			case 1:
				num_redCards += 1;
				break;
			case 2:
				num_yellowCards += 1;
				break;
			case 3:
				num_blueCards += 1;
				break;
		}
	}

	//============================= 計算 =============================//

	unsigned long long ans = combination(num_redCards, 2ULL) + combination(num_yellowCards, 2ULL) + combination(num_blueCards, 2ULL);

	//============================= 出力 =============================//
	std::cout << ans << std::endl;
}

説明

この問題の注意点は、組み合わせ nCr はC++では直接計算することができないという点です．

階乗の増加速度はすごく速いためint型であれば確か 13! の時点でオーバーフローします．

そこで nCr を計算するためにしたの公式を使います．

関数combination

nCrがv[n][r]に格納されている配列vを作成します．
まず、n < r の場合は0であるため、0を返します．

次に nCr = nCr-1であるため r と n-r から小さい方をrに格納します．

そのあと、上で説明した式を使い nCr を計算します．

問題の解法

赤青黄のいずれかのN枚のカードから同じ色のカードを2枚取り出す組み合わせの個数を計算します．

説明するまでもなく、n枚のx色のカードから2枚を取り出す組み合わせを計算すればいいので、上で説明した関数combinationを使い、combination(n, 2)を全ての種類のカードに対しての結果の和が求める答えです．

関数combinationの改善

combination.cpp

#define ULL unsigned long long

ULL combination(ULL n, ULL r) {
	if (n < r) {
		return 0;
	}

	r = std::min(r, n - r);
	std::vector<std::vector<ULL>> v(n + 1, std::vector<ULL>(r + 1, 0));

	for (auto i = 0ULL; i < (ULL)v[0].size(); ++i) {
		v[i][i] = 1;
	}

	for (auto i = 0ULL; i < (ULL)v.size(); ++i) {
		v[i][0] = 1;
	}

	for (auto i = 1ULL; i < (unsigned long long)v.size(); ++i) {
		for (auto j = ((signed long long)(r - n + i) < 1 ? 1 : r - n + i); j < std::min(i, (unsigned long long)v[0].size()); ++j) {
			v[i][j] = v[i - 1][j - 1] + v[i - 1][j];
		}
	}

	/*
	for (int i = 0; i < v.size(); ++i) {
		for (int j = 0; j < v[0].size(); ++j) {
			std::cout << std::setw(3) << v[i][j] << " ";
		}
		std::cout << std::endl;
	}
	*/
	
	return v[n][r];
}

改善前のcombinationで、combination(10, 4)を実行すると、配列vは下のようになる．

しかし、赤く塗りつぶした部分はv[n][r]を計算するために必要のない部分である．この部分の計算をしないようにプログラムを改良した．これにより、n(n-1)/2回の和算分実行速度が速くなった．微々たる差ではあるが、nが十分大きくなった時に有効である(と信じている)．