考察
買い方の数は膨大でも、求めたいのは安い方から限られた個数の金額だけだ。既に分かった安い金額へたこ焼きを一個足し、次の候補を作ろう。同じ金額の買い方は、その先に作れる金額も同じなので一つにまとめられる。
種類ごとに買う個数を決めると、組合せは指数的に増える。一方、種類数は高々10であり、一つの金額から一個足して作る候補は高々10個しかない。この違いを使い、金額そのものを状態にする。
何も買わない0円から始める。ある到達可能な金額を 、種類 の価格を とすると、一個追加して 円へ進める。 なので、進むたびに金額は必ず増える。金額を頂点、一個の追加を辺とみなせば、無限にある頂点のうち小さいものから順に調べる探索となる。
例えば価格が なら、0円から2円と3円を候補にする。2円を取り出すと4円・5円、3円を取り出すと5円・6円が候補になる。5円は二度現れるが、支払える金額としては一回だけ数える。残っていた候補も含めて最小値を選ぶため、最小値を取り出せる優先度付きキュー(min-heap)を使う。
- キューに0を入れ、直前に確定した金額は「なし」、確定した正の金額の個数は0とする。
- 最小の金額 を取り出す。直前に確定した金額と等しければ、順位を進めず、候補も追加せずに手順2へ戻る。
- 新しい金額なら直前の確定値を に更新する。 のときだけ個数を一つ増やし、それが 個目なら を答えて終了する。
- 全種類 について を追加し、手順2へ戻る。
0円は候補生成の出発点としてだけ使い、順位には含めない。上の例で数える金額は となり、4番目は5円である。値の異なる金額を昇順に確定するので、重複の判定には直前の確定値だけを覚えればよい。
典型の発動条件
暗黙グラフのbest-first search
状態を一つ処理すると少数の次候補を作れ、遷移先の値が必ず大きくなるなら、小さい状態から必要な順位まで列挙できる。全状態の範囲を先に確保する必要はない。
重複除去
異なる作り方でも、その後の遷移と数えたい対象が同じなら一つの状態へまとめる。昇順に取り出す場合は、直前の確定値と比較して重複を除ける。重複した状態から子を再生成しないことが、候補数の上限にも必要になる。
問題固有の要素
支払い方法ではなく、支払う金額の種類を数えることが要点となる。例えば6円を 円で作っても 円で作っても、その後に一個追加して作れる金額は同じである。問題文の「同じ金額は1回だけ数える」という条件から、状態を金額へまとめる。
正当性
まだ確定していない到達可能な最小の金額を とする。その買い方から一個を取り除いた金額 は、価格が正なので となる。0円を含め、 より小さい到達可能な金額はすべて確定済みである。従って を処理したときに はキューへ追加されている。
キューに入る金額もすべて到達可能なので、既に確定した値の重複を読み飛ばした後の最小値は である。これを繰り返すと正の金額を小さい順に漏れなく確定でき、 個目が答えとなる。同額の状態では追加できる価格も同じなので、二度目以降の候補生成を省いても到達可能性は変わらない。
実装上の注意
- 0円は順位に含めず、一度だけ候補生成する。同額を取り出したときは、順位の更新と次候補の生成を両方省く。
- 最小価格を とすると、 は相異なる候補なので答えは 以下。この手順で生成する値も高々 であり、最大で となる。加算前から符号付き64 bit整数を使う。
- 同じ価格の種類が複数あっても、この重複処理で正しく数えられる。
復習の核
- 作り方を列挙する前に、答えが「方法の数」か「値の種類」かを読む。
- 無限の状態でも、増える方向と少数の次候補が分かれば先頭だけを列挙できる。
- 重複した値を数えないだけでなく、そこから候補を増やさない。
計算量と制約
時間
0円と答えより小さい正の金額を合わせて 個処理し、それぞれから 個の候補を追加する。重複の取り出しを含めても追加・取り出しは 回で、キューの大きさも 。全体で 時間となる。
空間
価格配列に 、キューに を使うので、合計 。全金額分の配列は持たない。
制約との対応
、、。追加する候補は高々 個である。価格が正という条件は、小さい順の確定と、0円を正の金額から区別するために使う。 なら金額は となり、同じ手順で を得る。
出典