/<30326> Heap Structure - TOPC 2023

주간이 아닌 회고록에 쓰던 문제들을 문제 단위로 나눠서 올리게 될거 같습니다. 이유는 몰아서 쓰다 보니 좀 힘든 감도 있었고. 짧게라도 자주 쓰는 습관을 들이고 싶은거도 있고. 분량이 너무 긴가? 에 대한 스트레스도 안 받아도 되고.

 

팀 연습 하다가 만난 문제인데 셋에서 업솔빙 한 문제중 유일하게 마음에 드는 문제였네요.

 

$k$번째로 작은 값이 들어 갈 수 있는 정점에 대해 두가지 성질을 관찰 해야 합니다. 편의를 위해 모든 값이 unique하다고 가정합시다.

1. 루트의 깊이를 $1$이라 했을 때, 깊이가 $k$이하여야 한다. (어떤 정점의 조상들에 속한 값은 전부 그 정점에 속한 값보다 작아야 하기 때문)
2. 그 정점을 루트로 하는 서브트리의 크기를 $s$라 했을때 $s - 1 \le n - k$를 만족해야 한다. (서브트리에 속한 값들이 자기 자신을 제외하면 전부 자신보다 작아야 하기 때문)

따라서 위 두 조건을 만족하는 정점의 개수를 찾아주면 됩니다. 깊이 $k$이하인 정점들 중 답이 될 수 없는 정점의 개수를 $x$, 깊이 $k$이하인 모든 정점의 개수를 $z$라 하면 답은 $z - x$가 됩니다. 다만 단순히 모든 정점을 확인하면 너무 느리기 때문에 한 가지 관찰을 더 해줘야 합니다.

• 정점 번호가 증가함에 따라 그 정점을 루트로 하는 서브트리의 크기는 단조 감소한다.

따라서 우리는 $x$를 이진 탐색으로 구할 수 있습니다. 하지만 여기서 한가지 구현 디테일이 필요한데 바로 $i$번 정점을 루트로 하는 서브트리의 정점 개수를 구하는 과정입니다. (실제로 팀 연습 중 이 부분을 못해서 못 풀었습니다.)

$L = i, R = i$에서 시작해서 $L = L \times 2$, $R = R \times 2 + 1$을 $L$과 $R$이 $n$을 넘지 않는 범위 내에서 반복해 나가면 각 단계에서 $R - L + 1$은 그 레벨에서 $i$번 정점에 속한 서브트리의 정점의 개수입니다. ($L$은 $i$에서 왼쪽으로 쭉 뻗어나가고 $R$은 $i$에서 오른쪽으로 쭉 뻗어나가는 구조임을 생각해보면 됩니다.) $L$, $R$모두 두배씩 늘어남으로 이 단계 또한 $\mathcal{O}(logN)$ 시간이 걸림을 알 수 있습니다.

 

#include <bits/stdc++.h>
#include <ext/rope>

using namespace std;
using namespace __gnu_cxx;

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define endl '\n'

#define PRECISION 69

#define fr first
#define sc second

#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())

using ll = long long;
using ld = long double;

typedef pair<ll,ll> pll;
typedef pair<int,int> pii;

const int INF = 0x3f3f3f3f;
const ll LLINF = 4'500'000'000'000'000'000;
const ll MOD = 1'000'000'007;

bool test(ll N, ll K, ll node){
    if(node == 0) return 1;
    ll L = node, R = node;
    ll ret = 0;
    while(L <= N) {
        ret += min(N, R) - L + 1;
        L = L * 2;
        R = R * 2 + 1;
    }
    return ret - 1 > N - K;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.setf(ios::fixed); cout.precision(PRECISION);

    ll N, K; cin >> N >> K;
    ll l = 0, r = min(N, (1LL << (min(K, 62LL))) - 1);
    ll res = 0; ll mx = r;
    while(l <= r) {
        ll mid = (l + r) / 2;
        if(test(N, K, mid)){
            res = mid;
            l = mid + 1;
        } else r = mid - 1;
    } 
    cout << (mx - res);
}

 

짧은 구현인데도 방법을 못 떠올려서 못 풀었네요. 다시금 구현은 풀이와 발상의 일부라는걸 상기하게 되는 계기였던거 같습니다.