数列を辞書順に並び替えることは最後にソートすることにより達成できるので、条件を満たす数列を単に列挙することを考えます。

説明の簡略化のため、条件を満たす数列の prefix（先頭何項かを順に抜き出して得られる数列）としてあり得る数列を良い数列と呼びます。

良い数列を列挙することを考えます。

長さ \(1\) の数列 \((A_1)\) が良い数列である条件は \(1 \leq A_1 \leq M - 10(N - 1)\) であることです（\(A_1 > M - 10(N - 1)\) とすると、\(A_N\) を最小化しても \(M\) を超えてしまいます）。

\(2 \leq i \leq N\) であり、\((A_1, A_2, \ldots, A_{i - 1})\) が良い数列であるとします。このとき、\((A_1, A_2, \ldots, A_{i - 1}, A_i)\) が良い数列となる \(A_i\) の範囲は \(A_{i - 1} + 10 \leq A_i \leq M - 10(N - i)\) となります（\(A_1\) のときと同じ評価です）。

この規則に従って良い数列を列挙することでこの問題を解くことができます。

条件を満たす数列は最大で \(\binom{21}{9} = 293930\) 個であるため、適切な実装のもとこれは十分高速です。実装方針によっては自然に数列が辞書順になった状態で得られます。

また、個数に関する評価を行わずとも、すべての出力が求められていることから条件を満たす数列はある程度数が少なくなると予想でき、各長さの良い数列は出力する数列の個数を超えることがないことを利用すると、良い数列の個数と同程度のオーダーの計算量であれば実行時間制限に間に合うと予想できます。

\(A_i\) の上からの評価を単に \(M\) 以下とした場合、prefix となり得ない無駄な数列も列挙してしまうため、実行時間制限に間に合わせることはかなり難しいと思われます。

実装例

再帰関数を用いて実装する方法が有名ですが、再帰関数を用いずに素朴に各長さの良い数列を列挙する方法でも自然に実装できます。

非再帰

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> w = { {} };
	for (int i = 1; i <= n; i++) {
		vector<vector<int>> v;
		for (vector<int> a : w) {
			for (int x = (i == 1 ? 1 : a.back() + 10); x <= m - 10 * (n - i); x++) {
				vector<int> na = a;
				na.push_back(x);
				v.push_back(na);
			}
		}
		swap(v, w);
	}
	int X = w.size();
	cout << X << '\n';
	for (int i = 0; i < X; i++) for (int j = 0; j < n; j++) cout << w[i][j] << " \n"[j == n - 1];
}

再帰

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> ans;
	auto dfs = [&](auto dfs, vector<int> v) -> void {
		int sz = v.size();
		if (sz == n) {
			ans.push_back(v);
			return;
		}
		for (int i = (sz == 0 ? 1 : v.back() + 10); i <= m - 10 * (n - sz - 1); i++) {
			vector<int> nxt = v;
			nxt.push_back(i);
			dfs(dfs, nxt);
		}
	};
	dfs(dfs, {});
	int X = ans.size();
	cout << X << '\n';
	for (int i = 0; i < X; i++) for (int j = 0; j < n; j++) cout << ans[i][j] << " \n"[j == n - 1];
}