C - Monotonically Increasing Editorial by kyopro_friends


空の数列から始めて、数列の次の項の値としてありえる最小のものから順に、数列に追加した場合を深さ優先で探索することで問題を解くことができます。

実装例(Python)

def dfs(A):
  if len(A)==N:
    print(*A)
    return
  if len(A)==0: start=1
  else: start=A[-1]+1
  for i in range(start,M+1):
    dfs(A+[i])
 
N,M=map(int,input().split())
dfs([])

深さ優先探索では、まず「1項目が1である場合」を全て探索しきってから「1項目が2である場合」、「1項目が3である場合」……が探索されます。このため、解を見つけた順に出力することで辞書順になっています。
一般に、探索順序が望む順序にならない場合も、見つけた答えを全て記録しておきソートしてから出力する、などのアプローチをとることができます。

計算量は \(O(M 2^M)\) です。(導出は難しいので詳細は割愛)

posted:
last update: