考察
Aを降順に並べ、各種類の枚数C=(C_1,…,C_N)を状態にする。和が最大なのは(K,0,…,0)。種類iの一枚をi+1へ移すと、和はA_i−A_{i+1}だけ減るので、最大heapで妥協を小さい順に辿れば上位X個を列挙できる。
全種類への移動を毎回生成すると、一状態あたりN個の子と、その重複検査が必要になる。ここでは各状態に親を一意に定めて、子を高々二個へ減らす。根以外の状態で、枚数が正の最大添字をrとすると、「種類rの一枚をr−1へ戻す」状態を親とする。枚数の添字和が減るので、この親を辿れば必ず根へ戻る。
この親規約に対応する子は次の二つだけ。
- r<Nなら、現在最も右の種類rから一枚をr+1へ移す。
- r>1かつC_{r−1}>0なら、種類r−1から一枚をrへ移す。
後者では現在の種類rの枚数が既に正であることが必要。根ではr=1なので最初の子だけである。例えばK=2,N=3では(2,0,0)→(1,1,0)、そこから(1,0,1)と(0,2,0)の二子が生じる。(0,1,1)の親は(0,2,0)だけなので、別の移動順から重複生成しない。
各子の和は親の和以下。この木の未出力最大状態をheapから取り出し、二子を挿入する操作をX回行う。visitedは不要で、同じ金額でも枚数vectorが異なる状態は別々に出力する。heapには和、r、長さNの枚数vectorを持つ。
典型の発動条件
一意な親を持つ状態列挙
発動条件: 最良状態から全候補へ到達でき、各状態に一つの親を定められるとき。
親を逆にした子だけをheapへ入れれば、同一状態の重複生成を防げる。
優先度付き最良先探索
発動条件: 状態辺を進むほど目的値が悪化し、上位X件だけを知りたいとき。
未出力状態の最大値をheapから取り出して子を追加する。
問題固有の要素
「妥協」を一枚だけ右隣へ移す操作に限定しても、弱合成 C の任意状態へ到達でき、A の降順性により評価値の単調性も同時に得られる。
別の問題へ持ち帰る視点: 上位解列挙では、最良解から全解を生成できる局所変形と、その変形で目的値が単調になる順序を探す。
正当性
各枚数vectorは一意な親を持ち、その添字和が減るので全状態は根から到達できる。親を逆にした子は最大添字を一つ進めるか、現在の最大添字へ直前種類を移すかの二形に限られ、列挙した二子が全てである。辺を下ると金額が非増加なので、heapにまだ現れていない状態の祖先は、それ以上の金額でheap内に残っている。従ってheap最大の取り出しは未出力状態全体の最大と一致する。一意な親により同一vectorは一度だけ生成され、同額の別vectorは残る。
実装上の注意
- 同額のvectorを一つにまとめない。親規約でvectorの重複だけを防ぐ。
- 最大の正枚数添字rを状態とともに保持し、rとr−1からの高々二遷移だけを生成する。
- 金額和は負値も含み、K|A_i|は10^14に達するため64 bitを使う。
復習の核
- 上位列挙へ進む前に、局所変形の到達可能性と評価値の単調性を別々に証明する。同じ和を持つ別状態が出力から消えないことも小例で確かめる。
計算量と制約
時間
O(N log N+X(N+log(X+1)))。一出力につき高々二子を生成し、vectorのコピーはO(N)、heap操作は和の比較でO(log(X+1))。全種類へのN個の遷移やvectorをキーとするvisited比較は行わない。
空間
O(NX+N)。生成状態は高々2X+1個で各vectorはN整数。N=50,X=10^5でも枚数保存はO(5×10^6)整数規模。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1\leq N \leq 50; 1 \leq K \leq 10^5; 1 \leq X \leq \min\left(10^5, \binom{N+K-1}{K}\right); -10^9 \leq A_i \leq 10^9; All input values are integers.
出典