D - Keep Distance Editorial by hiro1729

Pythonで楽な解法

Pythonのitertools.combinations(p, r)は、リストpの長さrの部分列をソートして重複なしで返す関数です。

\(B_i=A_i-9(i-1)\) とすると、問題の条件は \(1\le B_1, B_{i-1}<B_i, B_N \le M-9(N-1)\) となり、\(B\)itertools.combinationsで簡単に取り出せます。

実装例 (Python) :

from itertools import combinations

N, M = map(int, input().split())
ans = []
for c in combinations(list(range(1, M - 9 * (N - 1) + 1)), N):
    l = list(c)
    for i in range(1, N):
        l[i] += 9 * i
    ans.append(l)
print(len(ans))
for i in ans:
    print(*i)

posted:
last update: