ABC 382

D - Keep Distance

https://atcoder.jp/contests/abc382/tasks/abc382_d

$1 \leq x \leq y \leq z \leq 6$ を満たす $(x,y,z)$ の組み合わせを求めるのと同じ要領で解ける。

\begin{align} x^\prime &= x \nonumber \\ y^\prime &= y+1 \nonumber \\ z^\prime &= z+2 \nonumber \end{align}

とすると $1 \leq x^\prime < y^\prime < z^\prime \leq 8$ となる。 $(x^\prime, y^\prime, z^\prime)$ が決まると $(x,y,z)$ も一通りに決まるから $(x^\prime, y^\prime, z^\prime)$ の組み合わせを調べれば良い。 やることとしては $1 \sim 8$ までの数字から重複なく3つ選び小さい方から順に $(x^\prime, y^\prime, z^\prime)$ とすれば良い。

実際の問題について考える

\begin{align} &A_1 + 10 \leq A_2 \Rightarrow A_1 \leq A_2 - 10 < A_2 - 9 \nonumber \\ &A_2 + 10 \leq A_3 \Rightarrow A_2 - 9 \leq A_3 - 19 \Rightarrow A_2 - 9 < A_3 - 18 \nonumber \\ &\vdots \nonumber \end{align}

より $A^\prime_k = A_k - 9(k-1)$ とすると

である。この条件を満たす $A^\prime_i$ $(i \in [1, M-9(N-1)])$ の組を見つけ最終的に $A_i$ に戻せばよい。

ll N, M;
vvll ans;

void dfs(vll& v) {
    if (v.size() == N) {
        vll w = v;
        ans.push_back(w);
        return;
    }

    int s = v.back();
    for (ll x = s + 1; x <= M - 9 * (N - 1); x++) {
        v.push_back(x);
        dfs(v);
        v.pop_back();
    }
}

void solve() {
    cin >> N >> M;
    for (ll x = 1; x <= M; x++) {
        vll v = {x};
        dfs(v);
    }

    int sz = ans.size();
    rep(i, sz) rep2(j, 1, N) {
        ans[i][j] += j * 9;
    }

    cout << ans.size() << endl;
    for (auto& v : ans)
        print(v);
}