AtCoder が提供しているABC（AtCoder Beginner Contest）382 D問題をC++とPythonで解いてみました。ABC382は、2024年11月30日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Keep Distance（Difficulty : 685）
問題の詳細は、リンク先をご覧ください。
再帰関数で全探索します。AtCoder Problems による Difficulty は 685 でした。
解答案
制約に $10N -9 \leqq M \leqq 10N$ とあります。長さ $N$ の数列を構成する要素間は、少なくとも $10$ 以上の差があるため、各項の上限と下限が分かります。
この上限と下限の要素を再帰関数で加えていきます。
公式解説によると、条件を満たす数列は最大で $_{21}C_{9} = 293930$ 個となるようです。再帰関数の呼び出し回数は、これに $N=12$ を掛けた数が最大値となるため、十分に間に合います。
C++ プログラム例（ABC382D）
再帰関数は、ラムダ式で実装しました（13ー32行目）。数列の初項は、1 から始まり、次の項は、前の要素に10を加えた数から始まります（20ー24行目）。数列の各要素の上限は26行目をご覧ください。
再帰関数の呼び出し前後で要素を push して、その後に pop するのは定番の処理です（28ー30行目）。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
int n;
ll m;
cin >> n >> m;
vector<vector<int>> result;
auto rec = [&](auto self, vector<int> v) -> void {
if ((int)v.size() == n) {
result.push_back(v);
return;
}
int base;
if (v.size() == 0) {
base = 1;
} else {
base = v.back() + 10;
}
for (int add_value = 0;
base + add_value <= m - 10 * (n - (int)v.size() - 1);
++add_value) {
v.push_back(base + add_value);
self(self, v);
v.pop_back();
}
};
vector<int> v;
rec(rec, v);
cout << result.size() << endl;
for (int i = 0; i < (int)result.size(); ++i) {
for (int j = 0; j < n; ++j) {
cout << result[i][j] << " \n"[j == n - 1];
}
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC382D）
Python版も基本的な考え方は同じです。解のリストを登録するときに copy をする必要があります（11行目）。以下がプログラムです。
"""AtCoder Beginner Contest 382 D"""
import sys
sys.setrecursionlimit(10000000)
def rec(v):
global n, m, result
if len(v) == n:
result.append(v.copy())
return
if len(v) == 0:
base = 1
else:
base = v[-1] + 10
add_value = 0
while True:
if base + add_value <= m - 10 * (n - len(v) - 1):
v.append(base + add_value)
rec(v)
v.pop()
add_value += 1
else:
break
n, m = map(int, input().split())
result = []
v = []
rec(v)
print(len(result))
for i in range(len(result)):
print(*result[i])こちらも「AC」と判定されました。
最後に
解答の最初に行数を出力する必要がありましたが、これを忘れて、WA判定となりました。C問題で1回、D問題で1回と2回分で10分のペナルティを受けました。もったいなかったです。
引き続き ABC の問題を紹介していきます。
