ABC 297 E — Kth Takoyaki Set

考察

買い方の数は膨大でも、求めたいのは安い方から限られた個数の金額だけだ。既に分かった安い金額へたこ焼きを一個足し、次の候補を作ろう。同じ金額の買い方は、その先に作れる金額も同じなので一つにまとめられる。

種類ごとに買う個数を決めると、組合せは指数的に増える。一方、種類数は高々10であり、一つの金額から一個足して作る候補は高々10個しかない。この違いを使い、金額そのものを状態にする。

何も買わない0円から始める。ある到達可能な金額を vv、種類 jj の価格を AjA_j とすると、一個追加して v+Ajv+A_j 円へ進める。Aj>0A_j>0 なので、進むたびに金額は必ず増える。金額を頂点、一個の追加を辺とみなせば、無限にある頂点のうち小さいものから順に調べる探索となる。

例えば価格が A=(2,3)A=(2,3) なら、0円から2円と3円を候補にする。2円を取り出すと4円・5円、3円を取り出すと5円・6円が候補になる。5円は二度現れるが、支払える金額としては一回だけ数える。残っていた候補も含めて最小値を選ぶため、最小値を取り出せる優先度付きキュー(min-heap)を使う。

  1. キューに0を入れ、直前に確定した金額は「なし」、確定した正の金額の個数は0とする。
  2. 最小の金額 vv を取り出す。直前に確定した金額と等しければ、順位を進めず、候補も追加せずに手順2へ戻る。
  3. 新しい金額なら直前の確定値を vv に更新する。v>0v>0 のときだけ個数を一つ増やし、それが KK 個目なら vv を答えて終了する。
  4. 全種類 j=1,…,Nj=1,\ldots,N について v+Ajv+A_j を追加し、手順2へ戻る。

0円は候補生成の出発点としてだけ使い、順位には含めない。上の例で数える金額は 2,3,4,5,6,…2,3,4,5,6,\ldots となり、4番目は5円である。値の異なる金額を昇順に確定するので、重複の判定には直前の確定値だけを覚えればよい。

典型の発動条件

状態を一つ処理すると少数の次候補を作れ、遷移先の値が必ず大きくなるなら、小さい状態から必要な順位まで列挙できる。全状態の範囲を先に確保する必要はない。

重複除去

異なる作り方でも、その後の遷移と数えたい対象が同じなら一つの状態へまとめる。昇順に取り出す場合は、直前の確定値と比較して重複を除ける。重複した状態から子を再生成しないことが、候補数の上限にも必要になる。

問題固有の要素

支払い方法ではなく、支払う金額の種類を数えることが要点となる。例えば6円を 2+2+22+2+2 円で作っても 3+33+3 円で作っても、その後に一個追加して作れる金額は同じである。問題文の「同じ金額は1回だけ数える」という条件から、状態を金額へまとめる。

正当性

まだ確定していない到達可能な最小の金額を x>0x>0 とする。その買い方から一個を取り除いた金額 yy は、価格が正なので 0≤y<x0\leq y<x となる。0円を含め、xx より小さい到達可能な金額はすべて確定済みである。従って yy を処理したときに xx はキューへ追加されている。

キューに入る金額もすべて到達可能なので、既に確定した値の重複を読み飛ばした後の最小値は xx である。これを繰り返すと正の金額を小さい順に漏れなく確定でき、KK 個目が答えとなる。同額の状態では追加できる価格も同じなので、二度目以降の候補生成を省いても到達可能性は変わらない。

実装上の注意

  • 0円は順位に含めず、一度だけ候補生成する。同額を取り出したときは、順位の更新と次候補の生成を両方省く。
  • 最小価格を aa とすると、a,2a,…,Kaa,2a,\ldots,Ka は相異なる候補なので答えは KaKa 以下。この手順で生成する値も高々 Ka+max⁡jAjKa+\max_j A_j であり、最大で 2×1014+1092\times 10^{14}+10^9 となる。加算前から符号付き64 bit整数を使う。
  • 同じ価格の種類が複数あっても、この重複処理で正しく数えられる。

復習の核

  • 作り方を列挙する前に、答えが「方法の数」か「値の種類」かを読む。
  • 無限の状態でも、増える方向と少数の次候補が分かれば先頭だけを列挙できる。
  • 重複した値を数えないだけでなく、そこから候補を増やさない。

計算量と制約

時間

0円と答えより小さい正の金額を合わせて KK 個処理し、それぞれから NN 個の候補を追加する。重複の取り出しを含めても追加・取り出しは O(NK)O(NK) 回で、キューの大きさも O(NK)O(NK)。全体で O(NKlog⁡(NK+1))O(NK\log(NK+1)) 時間となる。

空間

価格配列に O(N)O(N)、キューに O(NK)O(NK) を使うので、合計 O(NK)O(NK)。全金額分の配列は持たない。

制約との対応

1≤N≤101\leq N\leq 10、1≤K≤2×1051\leq K\leq 2\times 10^5、1≤Ai≤1091\leq A_i\leq 10^9。追加する候補は高々 NK≤2×106NK\leq 2\times 10^6 個である。価格が正という条件は、小さい順の確定と、0円を正の金額から区別するために使う。N=1N=1 なら金額は A1,2A1,…A_1,2A_1,\ldots となり、同じ手順で KA1KA_1 を得る。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Kth Takoyaki Set の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: priority queue・best-first列挙

主題
  • priority queue・best-first列挙: 現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能
    • 最短路モデル: 非負重みの距離確定を証明し、一般非負重みでは優先度付きキュー、0・1重みではdeque、単位重みではFIFOを選べる。

    主タグ: priority queue・best-first列挙

    補助タグ: 最短路モデル

    執筆: abc-explanation-author1.1.1 / revision 3

    学習の位置

    体系上の位置: priority queue・best-first列挙

    • 現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    • 最短路モデル — 基本的な明示グラフ探索を土台に、辺重みに応じた緩和・距離確定順を選び、最短距離と計算量を求める。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題