E - Cut in Half Editorial by MMNMM

操作の途中のどの瞬間においても、棒の長さはたかだか \(N+1\) 種類しかありません。 同じ長さの棒を適切にまとめて管理し、操作もまとめて行うことでこの問題を十分高速に解くことができます。

優先度付きキューなどで長さと本数の組を管理することで、現在最も長い棒をすべて（もしくは一部を）半分にすることが \(O(\log N)\) 時間で行えます。

最も長い棒をすべて半分にする操作がたかだか \(N\lfloor\log _ 2(K+1)\rfloor\) 回しか行われないことが示せます。

証明

すべての棒の長さにわずかな摂動を加えたとすることで、どの棒の長さおよびそれらの \(2 ^ k\) 倍もすべて異なると仮定して構いません。

初期状態における棒をひとつ選び、その長さを \(L\) とします。\(L\) 由来の長さ \(L,\dfrac L2,\dfrac L4,\ldots\) に対して行われた操作が \(n\) 回であるとすると、実際に半分にした回数は \(2 ^ n-1\) 回となります。 これが \(K\) 以下でなければならないので、\(n\le\lfloor\log _ 2(K+1)\rfloor\) となります。

初期状態の \(N\) 本の棒についてこれを足すことで、合計の操作回数が \(N\lfloor\log _ 2(K+1)\rfloor\) 回以下と評価できます（より精密に評価を行うことで \(O(N(\log K-\log N))\) 回と評価することができます）。

よって、同じ長さの棒に対する操作をまとめて行うことで \(O(N\log N\log K)\) 時間で最終的な棒の長さの分布が得られます。 あとは得られた分布に対して探索を行えばよく、\(O(N)\) 時間や \(O(N\log N)\) 時間などで可能です。

実装例は以下のようになります。

#include <iostream>
#include <iomanip>
#include <queue>

int main() {
    using namespace std;
    cout << setprecision(15);
    unsigned T;
    cin >> T;
    for (unsigned t{}; t < T; ++t) []{
        unsigned N, K, X;
        cin >> N >> K >> X;
        // (長さ, 本数) を管理する priority_queue
        priority_queue<pair<double, unsigned>> pq;
        for (unsigned i{}; i < N; ++i) {
            double a;
            cin >> a;
            pq.emplace(a, 1); // はじめ、長さ a が 1 本ある（重複があっても気にしない）
        }

        // 操作を行う
        while (K) {
            const auto [a, count]{pq.top()};
            pq.pop();
            if (K <= count) { // ここで終わりなら
                pq.emplace(a / 2, K * 2); // 途中まで操作して
                pq.emplace(a, count - K); // いくつか残る
                K = 0;
                break;
            } // そうでなければ
            pq.emplace(a / 2, count * 2); // 全部半分になる
            K -= count;
        }

        // 大きいほうから X 番目を求める
        while (X) {
            const auto [a, count]{pq.top()};
            pq.pop();
            if (X <= count) {
                cout << a << '\n';
                break;
            }
            X -= count;
        }
    }();
    return 0;
}

posted:
last update: