ABC335 B問題（Tetrahedral Number）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）335 のB問題をC++とPythonで解いてみました。ABC335は、2024年1月6日21:00に実施されました。

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

B問題 Tetrahedral Number（Difficulty : 52）

問題はリンク先をご覧ください。

ABC335 B問題 Tetrahedral Number

素直に3重ループを使います。AtCoder Problems による Difficulty は 52 でした。

解答案

問題自体は、素直に3重ループを使って解くことができます。

$N$ に対して、いくつの解が存在するのか考えてみます。入力例1の $N=3$ の場合、数字の最大3個（〇）を分割する区切りを △ で表します。少し長いですが、出力例1の解は以下のように表現できます。

$N=3$ の場合は、数字の組み合わせの解と、6個から3個の△の位置を決めることが1対1に対応します。このため、$_{6}C_{3} = (6 \times 5 \times 4) / (3 \times 2 \times 1) = 20$ 通りの組み合わせが存在します。

今回の問題 $N$ の上限は、21 でした。この場合の通り数は、$_{24}C_{3} = (24 \times 23 \times 22) / (3 \times 2 \times 1) = 2024$ 通りとなります。2024にちなんだ上限だと思われます。

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

0以上、N以下の3重ループで条件を満たす組み合わせを出力するだけです。

以下が、C＋＋プログラムとなります。

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

int main()
{
	int n;
	cin >> n;

	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j <=n; ++j) {
			for (int k = 0; k <= n; ++k) {
				if (i + j + k <= n) {
					cout << i << " " << j << " " << k << endl;
				}
			}
		}
	}

	return 0;
}

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

Python プログラム例（ABC335B）

Python 版も基本的な考え方は同じです。以下となります。

"""AtCoder Beginner Contest 335 B"""
n = int(input())

for i in range(n + 1):
    for j in range(n + 1):
        for k in range(n + 1):
            if i + j + k <= n:
                print(i, j, k)

こちらも「AC」と判定されました。

最後に

制約の上限に2024が出てくる問題でした。新年のお祝いも込められていると考えています。

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