ABC 252 Ex — K-th beautiful Necklace

考察

色cからちょうど1枚選ぶ組合せ数は各色の枚数n_cの積であり、総枚数N≤70の下ではこの積は整数分割の評価により高々およそ3^(N/3)に抑えられる。

採用する候補: 積が均衡する二群へのmeet-in-the-middleとXOR trie

色群を選択数の積がほぼ等しくなるよう分ければ各側のXOR列挙は全体の平方根規模になり、上位ビットからK番目を数えられる。

棄却する候補: 全ネックレスのXORを列挙してソート

組合せ数が最大で10^11級になり、列挙も保存もできない。

棄却する候補: 答え候補を二分探索して各回trie全走査

XOR順序は通常の数値閾値との数え上げが複雑で、判定の反復も必要になるため、ビットごとの候補群絞り込みを直接行う方が適する。

色数ではなく各色の選択肢数の積を重みとして二群を平衡化することで、左右の列挙数をともに約3^(N/6)へ抑える。

答えの上位ビットを一つ固定するごとに、その接頭辞を作れる左右XORの組数をtrieで数え、Kが入る側だけを残せる。

色を選択数の積が均衡する二群へ分け、各群で一色一枚を選ぶ全XORを重複込みで列挙する。右列を二進trieへ入れ、各左値aに対応する節点p_aを根で初期化する。節点のcountは右列の多重度込みの個数。上位bit bから次を繰り返す。

cnt1 = Σ_a count(child(p_a, 1 xor bit_b(a)))
if K ≤ cnt1: answer_bit = 1
else:        answer_bit = 0; K -= cnt1
各p_aをchild(p_a, answer_bit xor bit_b(a))へ進める
空の枝へ進む左要素は以後除外する

p_aは、aとXORした結果が現在までの答えprefixに一致する右要素だけを表す。全左要素について節点を一段だけ進めるので、一bitはO(U)、探索全体はO(BU)。同値の左値も別要素として数え、右側も節点countで多重度を保つ。

典型の発動条件

meet-in-the-middle

発動条件: 独立グループごとの選択肢積は大きいが、全体積の平方根なら列挙できる。

色を積で平衡化し、左右の部分XOR列を生成する。

K番目XORの二進trie

発動条件: 二つの多重集合から一つずつ選んだXORの順位を求めたい。

答え接頭辞に対応するtrie節点群を維持し、各ビットで候補ペア数を数える。

問題固有の要素

N≤70で総組合せ数が小さく見えない制約でも、各色枚数の積には整数分割由来の上界があり、その平方根列挙が成立する。

別の問題へ持ち帰る視点: 直積型の選択問題では、要素数ではなく各群の選択肢数の積を見積もって分割と計算量を設計する。

正当性

左右のXORの組は、全色から一つずつ選ぶ方法に一対一対応する。各bitで1側の個数を数え、大きい順の順位Kを含む側を選ぶ操作は、整列された候補集合を接頭辞ごとに絞る操作である。重複値も多重度を保って数えるため、最後に残る値がK番目になる。

実装上の注意

  • 同じXOR値も別の選び方として重複計数し、組数とKは最大10^18を超えないよう飽和させる。色の分割は色数ではなくn_cの積を基準にする。

復習の核

  • 選択総数が小さい例で全列挙ソートと比較し、同値XORの多重度、各色1枚、積が偏る色分布、K=1とK=総数を確認する。

計算量と制約

時間

O(B(U+V))、B=60、左右選択数U,Vを積で平衡化、trie順位探索。

空間

O(BV+U)、右trieと左XOR list。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq C \leq N \leq 70; 1 \leq D_i \leq C; 0 \leq V_i < 2^{60}; 1 \leq K \leq 10^{18}; There are at least K ways to make a necklace.; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

K-th beautiful Necklace の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: meet-in-the-middle・半分全列挙

主題
追加で学ぶ技能
    なし
    既習技能
    • bit列をTrieで索引化する: 整数を上位bitからTrieへ格納し、部分木情報を保ちながらXOR・大小条件に最適な分岐を選べる。

    主タグ: meet-in-the-middle・半分全列挙

    補助タグ: binary Trieによるbit列索引

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

    学習の位置

    体系上の位置: meet-in-the-middle・半分全列挙

    • 探索空間を独立に列挙できる二集合へ分け、両側の結果を照合・合成できる。

    先に読む単元:

    • bit列をTrieで索引化する — 整数を上位bitから分岐する列として格納し、XOR・大小・最小距離の候補を貪欲に選ぶ。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題