# ARC182-B |{floor(A_i/2^k)}|

1049diff
https://atcoder.jp/contests/arc182/tasks/arc182_b

## 解法

任意の非負整数$N$に対して$\lfloor\frac{N}{4}\rfloor = \lfloor\frac{\lfloor\frac{N}{2}\rfloor}{2}\rfloor$が成り立つことに注目する。結局の所以下のような問題に帰着する

> $2^{K} - 1$頂点からなる完全二分木が与えられる。$N$本の根を端点としたパスによってできるだけ沢山の頂点を被覆してください。

左子へ進むパスを優先的に取っていくことにする。取ったパスに隣接している頂点を新たにheapにつっこむ。みたいなことをすれば構築できる。計算量は$\Theta (NK^2\log ^2K)$。多分....

## 実装

#include <bits/stdc++.h>

void solve() {
    int N, K;
    std::cin >> N >> K;
    std::priority_queue<std::pair<int, int>> que;
    que.push(std::pair{ K, 1 });
    std::vector<int> ans;
    auto calc{[&](int i) -> int {
        while ((i << 1) < (1 << K)) i <<= 1;
        return i;
    }};
    while ((int)ans.size() < N and que.size()) {
        auto [score, idx]{que.top()};
        que.pop();
        ans.push_back(calc(idx));
        while ((idx << 1) < (1 << K)) {
            score--;
            assert(score >= 1);
            que.push(std::pair{ score, (idx << 1) | 1 });
            idx <<= 1;
        }
    }
    while ((int)ans.size() < N) {
        ans.push_back(1);
    }
    for (int i{} ; i < N ; i++) std::cout << ans[i] << (i + 1 == N ? '\n' : ' ');
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int T;
    std::cin >> T;
    while (T--) solve();
}

[提出](https://atcoder.jp/contests/arc182/submissions/58422662)

## 感想

CF-Div2みたいな見た目の問題だった。