以下、何も買わない \(0\) 円の方法を認めるものとします。始めに \(K\) を \(1\) 増やせばよいです。

\(K\) 番目に安い金額として、あるたこ焼きを \(K+1\) 個以上買うことはないためそれぞれの買う個数を \(0\) 個から \(K\) 個で全探索すると \(\mathrm{O}(K^N)\) でこの問題を解くことが出来ますが制限実行時間に間に合いません。探索方法を工夫します。

\(1\) 番目から \(i\) 番目までの安い金額が分かっているとします。\(i+1\) 番目の金額は、これら \(i\) 個の方法のいずれかに \(1\) 個いずれかのたこ焼きを加えたものとなります。そうでないならば、追加したものを \(1\) 個だけ残しそれ以外を消すことでより安い買い方を作れるためです。

よって、以下の探索方法によってこの問題を解くことが出来ます。

• 始め、\(0\) だけが入っている集合を管理するデータ構造 \(Q\) と答えを格納する長さ \(K\) の配列 \(\mathrm{ans}\) を持つ。\(i=2,3,\dots,K\) の順に以下を行う。
  • \(Q\) に入っている一番小さい値 \(v\) を取り出し、\(\mathrm{ans}[i]=v\) とする。ただし、\(\mathrm{ans}[i-1]=v\) の場合は次の要素を見る。
  • \(j=1,2,\dots,N\) に対して、\(Q\) に \(v+A_j\) を加える。

\(\mathrm{ans}[i-1]=v\) の時に次の要素を見るのは、答えとして重複している金額は \(1\) 回しかカウントしないからです。

計算量は、\(K \times N\) 回 \(Q\) にアクセスするため、\(\mathrm{O}(K N \log (NK))\) です。これは十分高速です。

\(Q\) のサイズが \(K\) を超えている間 \(Q\) の最大値を削除することで、\(\mathrm{O}(K N \log K)\) でこの問題を解くこともできます。

また、上記の探索方法はダイクストラ法に酷似しており、頂点をたこ焼きの買い方、辺をたこ焼きを \(1\) 個追加する操作かつ重みはたこ焼きの金額としたグラフ上で何も買わない頂点からダイクストラ法をしているとも見ることが出来ます。ただし、同じ金額となる買い方は同じものとみることに注意してください。