目次
はじめに
こんにちは。てくますプロジェクトのYukkinです！ この記事では、ABC382のD問題を解説していきます。
ABC（AtCoder Beginner Contest）とは、AtCoderが開催している、競技プログラミングコンテストです。
本記事は、数学・情報・論理パズルを楽しむ Techmath Project Advent Calendar 2024 の2日目の記事でもあります。アドベントカレンダーの応援や購読をしていただけると嬉しいです。
ABC382 D – Keep Distance
問題
整数 \(N\) と \(M\) が与えられます。
以下の条件をすべて満たす長さ \(N\) の整数列 \(A_1, A_2, \cdots, A_N\) を辞書順にすべて出力してください。
- \(1 \leqq A_i \)
- 2 以上 \(N\) 以下の各整数 \(i\) に対して \(A_{i-1}+10 \leqq A_i\)
- \(A_N \leqq M \)
制約
- \(2 \leqq N \leqq 12\)
- \(10N-9 \leqq M \leqq 10N\)
思考の筋道
具体例をもとに考えていきましょう。
具体例：\(N=3, M=23\)
ここまで具体例で考えてきましたが、一般的にも上記の考え方で解くことができます。この解法の発想は、「上限Mが厳しく、答えがかなり絞られるのでは？」というところから来ています。
重複組合せについて知りたい方は、【参考】重複組合せの公式と例題 などを参考にしてください。
なお、Pythonでは重複組合せの列挙は、ライブラリを使って行うことができます。
コード
import itertools
N, M = map(int, input().split())
ans = []
for c in itertools.combinations_with_replacement(range(1, M - (10 * (N - 1)) + 1), N):
l = list(c)
for i in range(1, N):
l[i] += 10 * i
ans.append(l)
print(len(ans))
for i in ans:
print(*i)ちなみに、AtCoderの解説 では、10の部分を9にすることで、重複組合せを回避し、ただの組合せを使って解いています。頭いいですね！
また、深さ優先探索で再帰的に解くこともできます。そちらのコードも載せておきます。
N, M = map(int, input().split())
l = []
def dfs(depth, current):
if depth == N:
l.append(list(current))
return
start = current[-1] + 10 if current else 1
end = M - (N - depth - 1) * 10
for i in range(start, end + 1):
dfs(depth + 1, current + [i])
end = M - (N - 1) * 10
for i in range(1, end + 1):
dfs(1, [i])
print(len(l))
for s in sorted(l):
print(*s)
以上、ABC382のD問題の解説でした！
では、またね。
整数列は、隣り合う項の差が10以上となるように単調増加します。また、初項は1以上であり、末項である第3項は23以下でなければなりません。
例えば、次のような例は条件を満たします。
一方で、4, 14, 24 などは条件を満たさないため不適です。
では、どのように条件を満たす数列を探すか考えてみましょう。
数列 0, 10, 20 をベースの数列として用意します。この数列に各項へ加算する数を決めることで、条件を満たす数列を構築します。
この際、後ろの項に加える数は前の項に加えた数以上である必要があります。また、加える数は4以下でなければなりません。
つまり、足す数の決め方は、1から3までの数のうち重複を許して3つの数を選ぶ組合せ（重複組合せ）で得られます。
◯ 3 つ、｜ 2 つ の重複組合せなので、\({}_5 \mathrm{ C }_2=10\) 通り、答えがあることが分かります。