ABC473 D - Coefficient Stair

考え方

それぞれ、$i$ を $A_i$ 個用意して、合計 $K$ になるようにせよ、という意味である。
これは再帰による深さ優先探索で調べればよい。

例えば「3以下で8の和を作る」となったら、以下を調べる。

• 3を0個にして、「2以下で合計8を作る」
• 3を1個にして、「2以下で合計5を作る」
• 3を2個にして、「2以下で合計2を作る」

使える最大数を $1$ つずつ小さくしていき、「1以下で $x$ を作る」になったら $1$ を $x$ 個用意すればよい。

もちろんこれでは見つける順序がぐちゃぐちゃだが、辞書順は出力前に普通にソートすればよい。

計算量は、文字式で示すのは難しいが、答えが $M=3\times 10^5$ 個以下である保証がある。
それの $N$ 倍くらいと考えると、解生成は C++ なら十分間に合う確認ができる（pythonだとやや厳しい）。
全体としてはソート部分が支配的で、$O(MN\log M)$。

入力例1での動作

入力を受け取る。

n: 3
k: 8

$A_1+2A_2+3A_3=8$ を満たす列をすべて求める。

まず、最も大きい $3$ を何個使うか決める。

• $A_3=0$ とすると、残りは $8$。
  • $A_2=0,1,2,3,4$ とでき、それぞれ残りを $1$ で埋めると $(8,0,0),(6,1,0),(4,2,0),(2,3,0),(0,4,0)$ を得る。
• $A_3=1$ とすると、残りは $5$。
  • $A_2=0,1,2$ とでき、$(5,0,1),(3,1,1),(1,2,1)$ を得る。
• $A_3=2$ とすると、残りは $2$。
  • $A_2=0,1$ とでき、$(2,0,2),(0,1,2)$ を得る。

こうして得た $10$ 個の列を辞書順にソートすると、次のようになる。

0 1 2
0 4 0
1 2 1
2 0 2
2 3 0
3 1 1
4 2 0
5 0 1
6 1 0
8 0 0

注意点

探索は、大きい方からやること。
小さい方からやると、ハズレの枝が多すぎて間に合わない。
大きい方からやれば、探索の枝刈りは不要である。
というか、この探索方法ならどう進んでも必ず最後に $1$ での帳尻合わせが可能。
よって、刈れる枝がなく、無駄が一切ない最速の探索になっている。

別解

特になし。