AtCoder が提供しているABC（AtCoder Beginner Contest）367 C問題をC++とPythonで解いてみました。ABC367は、2024年8月17日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Enumerate Sequences（Difficulty : 234）
問題の詳細は、リンク先をご覧ください。
ABC367 C問題 Enumerate Sequences
再帰関数で多重のループを処理します。AtCoder Problems による Difficulty は 234 でした。
解答案
もし、$N$ が固定なら、$N$ 重ループで処理できます。$N=8, R_i = 5$ の場合に最もループ回数が多くなりますが、それでも $8^5 = 32768$ 通りです。
ただし、制約が $1 \leqq N \leqq 8$ となっていてループを重ねる回数を決めることができません。このような場合、再帰関数がよく使われます。
C++ プログラム例（ABC367C）
関数 dfs は、vector コンテナ num を受け取ります。以下のように処理します。
- num の要素数が $N$ で要素の和が $K$ の倍数になっていれば、要素を出力します（9ー20行目）。
- 要素の最初から値を決めていきます。値を決めて、再帰呼び出しをして、その値を無かったことにします。この3行は、再帰で繰り返すための定番コードとなります。
再帰関数の処理では、結果的に辞書順に出力するため、ソートは必要ありません。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
int n, k;
vector<int> r;
void dfs(vector<int> num)
{
if (num.size() == n) {
int s = 0;
for (int i = 0; i < num.size(); ++i) {
s += num[i];
}
if (s % k == 0) {
for (int j = 0; j < n; ++j) {
cout << num[j] << " \n"[j == n - 1];
}
}
return;
}
for (int i = 1; i <= r[num.size()]; ++i) {
num.push_back(i);
dfs(num);
num.pop_back();
}
return;
}
int main()
{
cin >> n >> k;
r.resize(n);
for (int i = 0; i < n; ++i) {
cin >> r[i];
}
vector<int> num;
dfs(num);
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC367C）
Python版も基本的な考え方は同じです。以下がプログラムです。
"""AtCoder Beginner Contest 367 C"""
def dfs(num):
global n, k, r
if len(num) == n:
if sum(num) % k == 0:
print(*num)
return
for i in range(1, r[len(num)] + 1):
num.append(i)
dfs(num)
num.pop()
return
n, k = map(int, input().split())
r = list(map(int, input().split()))
num = []
dfs(num)
こちらも「AC」と判定されました。
最後に
再帰関数に慣れるための良い問題だと思います。
引き続き ABC の問題を紹介していきます。
