KOI 2nd Round Mock 1 (DOJ) 후기

KOI 2nd Round Mock 1 [High]

KOI 2nd Round Mock 1 [Middle]

KOI 2nd Round Mock 1 [Elementary]

 

 

72번 히스토그램 ([High] A번) ([Middle] C번) 100 / 100

정답수열에서의 최대 직사각형의 높이는 기존에 존재하는 N개의 직사각형들중 하나이다. 가능한 모든 높이에 대해 각각 가능한 최대 너비를 구해보자. 

정답 후보 직사각형의 높이가 정해졌다면 그 높이 이상의 직사각형들은 정답 후보 직사각형에 포함이 될 수 있고 정답 후보 직사각형보다 높이가 낮은 직사각형들은 정답 후보 직사각형에 포함이 될 수 없다. 정답 후보 직사각형에 포함될수 있는지 여부로 수열 A를 이진 수열로 만들 수 있다.

어떤 구간 안의 정답 후보 직사각형에 포함될 수 있는 1들을 전부 가지고 정답 후보 직사각형을 만드는데 필요한 연산 횟수는 구간 안의 정답 후보 직사각형 정답 후보 직사각형에 포함될 수 없는 0들을 구간의 가장 왼쪽 또는 가장 오른쪽 1 바깥으로 이동시키는데 필요한 연산의 횟수의 합이고 이때 바깥쪽 0들부터 빼주면 연산 횟수는 이동하면서 거치는 1의 개수와 같다. 따라서 구간의 1들중 가운데(1이 짝수면 아무거나) 1을 기준으로 왼쪽의 0은 왼쪽으로 빼주고 오른쪽 0은 오른쪽으로 빼주면 된다. 이제 X번 이하의 연산으로 정답 후보 직사각형으로 만들 수 있는 구간을 왼쪽 끝, 오른쪽 끝, 가운데 1 세가지 인덱스를 관리하며 투 포인터 를 사용하여 O(N^2)에 구할 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

ll A[7000];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    ll X;
    cin >> N >> X;

    vector<ll> xs;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        xs.push_back(A[i]);
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
    for (int i = 0; i < N; i++) A[i] = lower_bound(xs.begin(), xs.end(), A[i]) - xs.begin();

    ll ans = 0;
    for (int i = 0; i < xs.size(); i++) {
        int l = 1, r = N;
        int mi = -1, ri = -1, lco = 0, rco = 0, lico = 0, mico = 0, rico = 0;
        ll tmp = 0;
        for (int li = 0; li < N;) {
            while (ri + 1 < N) {
                ll ttmp = tmp;
                if (A[ri + 1] >= i) ttmp += rco;
                if (ttmp > X && li <= ri) break;
                if (A[++ri] >= i) {
                    rico++;
                    tmp += rco;
                }
                else rco++;

                while ((mico - lico < ((rico - lico) >> 1) + 1 || mi < li) && mi < ri) {
                    if (A[++mi] >= i) mico++;
                    else {
                        tmp -= ri - mi - --rco;
                        tmp += mi - li - lco++;
                    }
                }
            }

            //cout << xs[i] << " : " << li + 1 << " <- " << mi + 1 << " -> " << ri + 1 << '\n';
            //cout << "tmp lco rco : " << tmp << ' ' << lco << ' ' << rco << '\n';
            //cout << '\n';
            if (tmp <= X) ans = max(ans, xs[i] * (rico - lico));
            if (A[li++] >= i) {
                lico++;
                tmp -= lco;
            }
            else lco--;
            while ((mico - lico < ((rico - lico) >> 1) + 1 || mi < li) && mi < ri) {
                if (A[++mi] >= i) mico++;
                else {
                    tmp -= ri - mi - --rco;
                    tmp += mi - li - lco++;
                }
            }
        }
    }

    cout << ans << '\n';
}

 

73번 경기장 ([High] B번) ([Elementary] D번) 100 / 100

센트로이드 분할을 사용하여 해결할 수 있다. 각 분할에서 센트로이드 도시를 포함하여 경기장을 짓는 경우를 보자. 우선 센트로이드를 경기장에 포함시킨 뒤 센트로이드를 루트로 하는 트리에서 각 자식의 서브트리에 포함된 특별 도시들의 개수와 자식 도시까지의 거리의 합을 찾는다. 어떤 자식 도시를 경기장에 포함시키면 그 자식 도시의 서브트리에 포함된 특별 도시들의 개수만큼 불편도가 줄어든다. 자식 도시 하나를 경기장에 포함시킨 뒤에는 그 자식 도시의 자식 도시들 각각에 포함된 특별 도시들의 개수는 더 적거나 같기 때문에 우선순위 큐에 넣어 가장 많은 불편도를 줄어들게 하는 도시부터 보는 그리디가 가능하다. 분할을 할때 현재 센트로이드에 특별 도시 개수와 거리합을 적절히 더해주면 서브트리에서 재귀적으로 답을 구할 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int X;
ll P[200000], Pdist[200000], ans = 1e12;
vector<int> graph[200000];
bool visited[200000];
int subsz[200000];

void szdfs(int node, int par) {
    subsz[node] = 1;
    for (int i : graph[node]) {
        if (visited[i] || i == par) continue;
        szdfs(i, node);
        subsz[node] += subsz[i];
    }
}
int getcent(int node, int par, int halfsz) {
    for (int i : graph[node]) {
        if (visited[i] || i == par) continue;
        if (subsz[i] >= halfsz) return getcent(i, node, halfsz);
    }
    return node;
}

pair<ll, ll> subuncomp[200000];

void uncompdfs(int node, int par) {
    subuncomp[node] = {P[node], Pdist[node]};
    for (int i : graph[node]) {
        if (visited[i] || i == par) continue;
        uncompdfs(i, node);
        subuncomp[node].first += subuncomp[i].first;
        subuncomp[node].second += subuncomp[i].first + subuncomp[i].second;
    }
    //cout << "subuncomp " << node + 1 << " : " << subuncomp[node].first << ' ' << subuncomp[node].second << '\n';
}

void centdcmp(int node) {
    szdfs(node, -1);
    node = getcent(node, -1, subsz[node] >> 1);
    visited[node] = true;

    ll psum = P[node], pdistsum = Pdist[node];
    int leftX = X - 1;
    ll curuncomp = Pdist[node];
    priority_queue<pair<ll, pii>> pq;
    for (int i : graph[node]) {
        if (visited[i]) continue;
        uncompdfs(i, node);
        psum += subuncomp[i].first;
        pdistsum += subuncomp[i].first + subuncomp[i].second;
        curuncomp += subuncomp[i].first + subuncomp[i].second;
        pq.push({subuncomp[i].first, {i, node}});
    }
    //cout << node + 1 << " : " << curuncomp << '\n';

    while (!pq.empty() && leftX--) {
        pair<ll, pii> tmp = pq.top();
        pq.pop();
        curuncomp -= tmp.first;
        for (int i : graph[tmp.second.first]) {
            if (visited[i] || i == tmp.second.second) continue;
            pq.push({subuncomp[i].first, {i, tmp.second.first}});
        }
    }
    if (leftX <= 0) ans = min(ans, curuncomp);
    //cout << leftX << ' ' << curuncomp << "\n\n";

    for (int i : graph[node]) {
        if (visited[i]) continue;
        P[i] += psum - subuncomp[i].first;
        Pdist[i] += pdistsum - subuncomp[i].second - (subuncomp[i].first << 1) + psum;
        centdcmp(i);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K >> X;
    while (K--) {
        int Pi;
        cin >> Pi;
        P[--Pi]++;
    }
    for (int i = 1; i < N; i++) {
        int U, V;
        cin >> U >> V;
        graph[--U].push_back(--V);
        graph[V].push_back(U);
    }

    centdcmp(0);
    cout << ans << '\n';
}

 

74번 중앙값 ([High] C번) ([Middle] D번) 100 / 100

A가 이진수열인 7번 서브테스크를 손으로 잘 시뮬레이션 해보면 규칙을 찾을 수 있다. 00 또는 11등 같은 수가 두번 이상 연속해서 나온다면 단계를 거듭할수록 연속한 같은 수의 범위가 좌우로 한칸씩 늘어나며 연속한 0들과 연속한 1들의 경계가 만나면 더이상 확장되지 않는다. 또한 0과 1이 번갈아가며 나오는 구간은 단계를 거듭할때마다 홀짝성이 바뀌며 연속한 00 또는 11의 범위보다 우선순위가 낮아 덮어씌워질 수 있다.따라서 연속한 00과 11을 채운 뒤 남은 부분에 01이 번갈아 나오게 된다.

어떤 특정 수 이하를 1로 초과를 0으로 바꾸어 A를 이진수열로 만든 뒤 정답을 구한다면 고른 수 이하인 수들의 정답에서의 위치를 전부 알 수 있다. A의 원소들을 정렬한 뒤 작은 수부터 하나씩 0에서 1로 바꾸어가며 최종 결과에서 새로 생기는 1의 위치에 많조분과 함께 홀수 인덱스, 짝수 인덱스를 관리하는 세그먼트 트리에 구간쿼리를 날려 답을 구할수 있다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

pii A[500000];
int ans[500000];
bool oseg[1048576], eseg[1048576], smallflag[500000];
#define lidx (idx << 1)
#define ridx (idx << 1 | 1)

void init(int t1, int t2, int idx) {
    if (t1 == t2) {
        if (t1 & 1) oseg[idx] = true;
        else eseg[idx] = true;
        return;
    }
    int mid = (t1 + t2) >> 1;
    init(t1, mid, lidx);
    init(mid + 1, t2, ridx);
    oseg[idx] = oseg[lidx] | oseg[ridx];
    eseg[idx] = eseg[lidx] | eseg[ridx];
}

void update(int t1, int t2, int q1, int q2, int val, bool isodd, int idx) {
    if (q2 < t1 || t2 < q1 || (isodd && !oseg[idx]) || (!isodd && !eseg[idx])) return;
    if (t1 == t2) {
        //cout << "updated " << t1 + 1 << " : " << val << '\n';
        ans[t1] = val;
        oseg[idx] = eseg[idx] = false;
        return;
    }
    int mid = (t1 + t2) >> 1;
    update(t1, mid, q1, q2, val, isodd, lidx);
    update(mid + 1, t2, q1, q2, val, isodd, ridx);
    oseg[idx] = oseg[lidx] | oseg[ridx];
    eseg[idx] = eseg[lidx] | eseg[ridx];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;
    init(0, N - 1, 1);

    set<int> conbig, consmall;

    for (int i = 0; i < N; i++) {
        cin >> A[i].first;
        A[i].second = i;
        conbig.insert(i);
    }
    sort(A, A + N);

    for (int i = 0; i < N; i++) {
        //cout << "A : " << A[i].first << ' ' << A[i].second + 1 << '\n';
        int l = A[i].second, r = A[i].second;
        bool conbigsur = false;
        if (conbig.find(A[i].second) != conbig.end()) conbigsur = true;
        conbig.erase(A[i].second);
        smallflag[A[i].second] = true;
        if (A[i].second) {
            if (smallflag[A[i].second - 1]) {
                l = A[i].second - 1;
                consmall.insert(A[i].second - 1);
                consmall.insert(A[i].second);
            }
            else if (A[i].second == 1 || smallflag[A[i].second - 2]) conbig.erase(A[i].second - 1);
        }
        if (A[i].second + 1 < N) {
            if (smallflag[A[i].second + 1]) {
                r = A[i].second + 1;
                consmall.insert(A[i].second);
                consmall.insert(A[i].second + 1);
            }
            else if (A[i].second + 2 == N || smallflag[A[i].second + 2]) conbig.erase(A[i].second + 1);
        }
        auto it = conbig.lower_bound(A[i].second);

        //cout << "l/r : " << l + 1 << ' ' << r + 1 << '\n';


        int lsm = -1, rsm = N, lbi = -1, rbi = N;
        auto sit = consmall.lower_bound(A[i].second);
        if (sit != consmall.begin()) lsm = *prev(sit, 1);
        if (sit != consmall.end()) rsm = *sit;
        if (it != conbig.begin()) lbi = *prev(it, 1);
        if (it != conbig.end()) rbi = *it;

        int lb = A[i].second - K, rb = A[i].second + K;
        if (l == r) {
            if (it != conbig.begin()) lb = *prev(it, 1) + K;
            if (it != conbig.end()) rb = *it - K;
            //cout << "lb/rb : " << lb + 1 << ' ' << rb + 1 << '\n';
            //cout << "lsm/rsm : " << lsm + 1 << ' ' << rsm + 1 << '\n';
            //cout << "lbi/rbi : " << lbi + 1 << ' ' << rbi + 1 << '\n';
            update(0, N - 1, max(lb, max(lsm, lbi) + 1), min(rb, min(rsm, rbi) - 1), A[i].first, (A[i].second + K) & 1, 1);
            if (conbigsur) {
                if (lbi < lsm) {
                    if (rbi < rsm) {
                        update(0, N - 1, lsm, min(lsm + K, lsm + ((rbi - lsm) >> 1)), A[i].first, true, 1);
                        update(0, N - 1, lsm, min(lsm + K, lsm + ((rbi - lsm) >> 1)), A[i].first, false, 1);
                    }
                    else {
                        update(0, N - 1, lsm, min(lsm + K, rsm), A[i].first, true, 1);
                        update(0, N - 1, lsm, min(lsm + K, rsm), A[i].first, false, 1);
                    }
                }
                if (rsm < rbi) {
                    if (lsm < lbi) {
                        update(0, N - 1, max(rsm - K, rsm - ((rsm - lbi) >> 1)), rsm, A[i].first, true, 1);
                        update(0, N - 1, max(rsm - K, rsm - ((rsm - lbi) >> 1)), rsm, A[i].first, false, 1);
                    }
                    else {
                        update(0, N - 1, max(rsm - K, lsm), rsm, A[i].first, true, 1);
                        update(0, N - 1, max(rsm - K, lsm), rsm, A[i].first, false, 1);
                    }
                }
            }
        }
        else {
            lb = l - K;
            rb = r + K;
            int llb = lb, rrb = rb;
            if (it != conbig.begin()) {
                lb = max(lb, l - ((l - *prev(it, 1)) >> 1));
                llb = max(llb, *prev(it, 1) + K);
            }
            if (it != conbig.end()) {
                rb = min(rb, r + ((*it - r) >> 1));
                rrb = min(rrb, *it - K);
            }
            //cout << "lb/rb : " << lb + 1 << ' ' << rb + 1 << '\n';
            //cout << "llb/rrb : " << llb + 1 << ' ' << rrb + 1 << '\n';

            lsm = -1;
            rsm = N;
            lbi = -1;
            rbi = N;
            if (it != conbig.begin()) lbi = *prev(it, 1);
            if (it != conbig.end()) rbi = *it;

            sit = consmall.lower_bound(l);
            if (sit != consmall.begin()) lsm = *prev(sit, 1);
            sit = consmall.lower_bound(r + 1);
            if (sit != consmall.end()) rsm = *sit;

            //cout << "lsm/rsm : " << lsm + 1 << ' ' << rsm + 1 << '\n';
            //cout << "lbi/rbi : " << lbi + 1 << ' ' << rbi + 1 << '\n';

            //update(0, N - 1, lb, rb, A[i].first, true, 1);
            //update(0, N - 1, lb, rb, A[i].first, false, 1);
            //update(0, N - 1, max(llb, max(lsm, lbi) + 1), min(rrb, min(rsm, rbi) - 1), A[i].first, (A[i].second + K) & 1, 1);
            update(0, N - 1, max(lb, max(lsm, lbi) + 1), min(rb, min(rsm, rbi) - 1), A[i].first, true, 1);
            update(0, N - 1, max(lb, max(lsm, lbi) + 1), min(rb, min(rsm, rbi) - 1), A[i].first, false, 1);
            //cout << "con to sep\n";
            update(0, N - 1, max(llb, max(lsm, lbi) + 1), min(rrb, min(rsm, rbi) - 1), A[i].first, (A[i].second + K) & 1, 1);
        }

        //cout << "conbig : ";
        //for (int j : conbig) cout << j + 1 << ' ';
        //cout << '\n';
    }

    assert(!oseg[1] && !eseg[1]);
    for (int i = K; i < N - K; i++) cout << ans[i] << ' ';
    cout << '\n';
}

/*

1 1 2 2 1
  1 2 2

1 2 1 2 1 2 1
  1 2 1 2 1
    1 2 1
      1

1 2 1 2 1 2 2 2 1 2 1
  1 2 1 2 2 2 2 2 1
    1 2 2 2 2 2 2
      2 2 2 2 2

00001111
 000111
  0011

00001011
 000011
  0001

10 3
10 1 9 2 8 3 7 4 6 5
   9 2 8 3 7 4 6 5
     8 3 7 4 6 5
       7 4 6 5

1010101010
1010101000
1010100000

0001111000

 */

 

 

 

 

 

KOI 2nd Round Mock 1 [High] 스코어보드

KOI 2nd Round Mock 1 [Middle] 스코어보드

KOI 2nd Round Mock 1 [Elementary] 스코어보드