코드 복사/붙여넣기 하는 당신이 아름답습니다.

대회 정보: https://www.acmicpc.net/contest/view/457
문제 목록: 추가 예정

출제 및 검수 : edenooo, jh05013, tonyjjw, wookje

문제 A B C D E
출제자 wookje tonyjjw tonyjjw wookje wookje

A. 비트가 넘쳐흘러

풀이

17419: 비트가 넘쳐흘러

서브태스크1: 주어진 이진수를 입력 받아서 시키는대로 짜면 됩니다.

서브태스크2: 주어진 연산은 fenwick tree 구현에 대표적으로 사용되는 연산입니다. 주어진 문자열에서 1의 개수를 세면 됩니다.

코드

# python3
input()
print(input().count('1'))

B. 깊콘이 넘쳐흘러

풀이

17420: 깊콘이 넘쳐흘러

서브태스크1: 사실 생각 안 해 봤습니다. 아무 풀이나 짜면 됩니다.

서브태스크2: (B[i], A[i]) pair를 오름차순으로 정렬하고, 스위핑 하는 느낌으로 그리디하게 풀 수 있습니다. 대부분의 구현에서, 아래와 같은 반례가 있을 수 있습니다.:

2
1 30
30 30

코드

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <functional>

using namespace std;

typedef pair<int, int> pii;

const int MN = 100000 + 5;

int A[MN], B[MN];

int main() {
    int N;
    scanf("%d", &N);
    for(int i = 0; i < N; i++) scanf("%d", &A[i]);
    for(int i = 0; i < N; i++) scanf("%d", &B[i]);

    long long ans = 0;

    for(int i = 0; i < N; i++) {
        if (A[i] < B[i]) {
            int x = (B[i] - A[i] + 29) / 30;
            A[i] += x * 30;
            ans += x;
        }
    }
    vector<int> order;
    for(int i = 0; i < N; i++) order.push_back(i);

    auto cmp = [](const int i, const int j) {
        if (B[i] != B[j]) return B[i] < B[j];
        
        return A[i] < A[j];
    };
    
    sort(order.begin(), order.end(), cmp);

    int a_lb = 0;

    for(int p = 0; p < order.size(); p++) {
        int p2 = p+1;
        while(p2 < order.size() && B[order[p2-1]] == B[order[p2]]) p2++;

        int dst = max(a_lb, B[order[p]]);

        for(int kk = p; kk < p2; kk++) {
            if (A[order[kk]] < a_lb) {
                int x = (a_lb - A[order[kk]] + 29) / 30;
                ans += x;
                A[order[kk]] += 30*x;
            }
        }

        sort(order.begin() + p, order.begin() + p2, cmp);

        a_lb = max(a_lb, A[order[p2-1]]);

        p = p2 - 1;
    }

    printf("%lld\n", ans);

    return 0;
}

C. 빗물이 넘쳐흘러

풀이

17421: 빗물이 넘쳐흘러

서브태스크1: K = 2 이므로, 언덕이 ㅅ 모양으로 꺾이는 위치를 찾는 등 문제에서 시키는대로 짜면 됩니다.

서브태스크2: 물을 하나(한 칸)씩 시뮬레이션 해 보는 O(N*max_depth) 풀이가 있을 수 있습니다. 혹은 O(N^3) 또는 O(N^2) 정도의 시간에, 모든 i에 대해 시뮬레이션을 해 볼 수 있습니다. O(N^2) 풀이는 링크드리스트 같은 느낌으로 구현할 수 있습니다.

서브태스크3: stack을 이용하여 관리하면 O(N) 정도의 시간에 문제를 해결할 수 있습니다.

코드

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MN = 100000 + 5;

int N, K;
int A[MN];

struct Segment {
    int left, right, height, water; 

    Segment() {}
    Segment(int left, int right, int height, int water): left(left), right(right), height(height), water(water) {}

    void print() {
        printf("segment %d %d %d\n", left, right, height);
    }
};

vector<Segment> stack;

int dcnt = 0;

int main() {
    scanf("%d%d", &N, &K);

    ll ans = 0;
    int cnt = 0;

    for(int i = 1; i <= N + 1; i++) {
        if(i <= N)
            scanf("%d", &A[i]);

        int left = i;
        bool first = true;
        int remain = 0;

        while(!stack.empty() && stack.back().height >= A[i]) {
            left = stack.back().left;

            int delta = stack.back().height - A[i];
            if(delta > 0) {
                if (first) {
                    cnt++;
                    first = false;
                    remain++;
                }
                cnt -= stack.back().water;
            }
            else {
                remain += stack.back().water;
            }

            if(cnt == K) {
                printf("%lld\n", ans);
                return 0;
            }

            ans += (ll)delta * (stack.back().right - stack.back().left + 1);
            stack.pop_back();
        }

        stack.emplace_back(left, i, A[i], remain);
    }

    puts("-1");
    return 0;
}

D. 지폐가 넘쳐흘러

풀이

17422: 지폐가 넘쳐흘러

서브태스크1: 주어진 w[i]의 합을 출력하면 됩니다.

서브태스크2: 모든 i에 대해, i가 루트인 트리에서 가장 먼 노드를 찾는 시뮬레이션을 하면 됩니다. 가장 먼 노드는 해당 노드까지의 w[i] 합이 가장 큰 노드를 의미합니다. O(N^2) 정도에 풀 수 있습니다.

서브태스크3: 서브태스크2 풀이에서 조금 생각해 보면, 서브태스크2 풀이는 곧 트리의 지름을 구하는 것임을 알 수 있습니다. 트리의 지름은 O(N) 풀이가 잘 알려져 있습니다.

서브태스크4: 트리의 지름을 dp로 구하는 풀이를 조금 응용합니다. dp[i] = i를 루트로 하는 서브트리에 대한 정답(최대 지폐 개수), mx[i] = i를 루트로 하는 서브트리에서, i로부터의 거리가 가장 먼 잎까지의 거리. 쿼리에서 어떤 노드가 갱신되면, 그 노드를 관리하는 배열은 많아야 O(logN)개입니다. 세그먼트 트리를 구현하는 느낌으로 짜면, O(N+QlogN)의 시간에 해결할 수 있습니다. 저는 귀찮아서 map으로 O(Qlog^2N) 했습니다.

코드

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

ll n, q;
ll a[666666];
ll d[666666];
map<ll, ll> mp;

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);

    cin >> n;
    bool flag = 0;
    for (int i = 1; i <= 18; i++) {
        flag |= (n == (1<<i)-1);
    }
    assert(flag);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = n; i >= 1; i--) {
        d[i] = max(d[i*2], d[i*2+1]) + a[i];
        mp[d[i*2]+d[i*2+1]+a[i]]++;
    }
    cout << mp.rbegin()->first << "\n";

    cin >> q;
    assert((1 <= q && q <= 100000 || q == 0);
    while (q--) {
        ll i, v;
        cin >> i >> v;
        ll j = i;
        while (j) {
            mp[d[j*2]+d[j*2+1]+a[j]]--;
            if (mp[d[j*2]+d[j*2+1]+a[j]] == 0) {
                mp.erase(d[j*2]+d[j*2+1]+a[j]);
            }
            j >>= 1;
        }
        a[i] = v;
        while (i) {
            d[i] = max(d[i*2], d[i*2+1]) + a[i];
            mp[d[i*2]+d[i*2+1]+a[i]]++;
            i >>= 1;
        }
        cout << mp.rbegin()->first << "\n";
    }

    return 0;
}

E. 민원이 넘쳐흘러

풀이

17423 : 민원이 넘쳐흘러

서브태스크1: (가장 가까운 두 점의 거리)/2가 답입니다. 모든 N^2쌍에 대해서 이를 계산하면 됩니다.

서브태스크2: 서브태스크1에서 조금 더 생각하면, 모든 (i, j)쌍에 대해서 distance(i, j)/(s[i]+s[j])가 답임을 알 수 있습니다. 혹은 뇌절하고 파라메트릭 서치를 해도 됩니다.

서브태스크3: 원래 서브태스크3은 1점짜리였는데, 어려운 문제로 만들려고 배점을 높였습니다. 좌표계를 45도 회전((x, y) -> (x+y, x-y)) 시켜서 마름모->직사각형으로 만들어 놓고, 파라메트릭+좌표압축+스위핑+세그트리로 풀면 됩니다. 까다로운 반례가 꽤 있는데, The solution is left as an exercise for the competitor.

코드

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

const int MAXN = (1<<21);

int n;
int s[111111];
int x[111111], y[111111];

int tree[MAXN+5], lazy[MAXN+5];

void propagate(int x, int y, int node) {
    if (!lazy[node]) return;
    tree[node] += (y-x+1)*lazy[node];
    if (x != y) {
        lazy[node*2] += lazy[node];
        lazy[node*2+1] += lazy[node];
    }
    lazy[node] = 0;
}

int update(int s, int e, int x, int y, int node, ll diff) {
    propagate(x, y, node);
    if (e < x || y < s) return tree[node];
    if (s <= x && y <= e) {
        tree[node] += (y-x+1)*diff;
        if (x != y) {
            lazy[node*2] += diff;
            lazy[node*2+1] += diff;
        }
        return tree[node];
    }
    return tree[node] = update(s, e, x, (x+y)/2, node*2, diff) + update(s, e, (x+y)/2+1, y, node*2+1, diff); 
}

int query(int s, int e, int x, int y, int node) {
    propagate(x, y, node);
    if (e < x || y < s) return 0;
    if (s <= x && y <= e) return tree[node];
    return query(s, e, x, (x+y)/2, node*2) + query(s, e, (x+y)/2+1, y, node*2+1); 
}

vector<pii> pl[MAXN+5], mi[MAXN+5];
vector<pii> qry[MAXN+5];
vector<ll> vx, vy;

void init(ll mid) {
    memset(tree, 0, sizeof(tree));
    memset(lazy, 0, sizeof(lazy));
    vx.clear();
    vy.clear();
    for (int i = 0; i <= MAXN; i++) {
        pl[i].clear(); mi[i].clear(); qry[i].clear();
    }
    for (int i = 1; i <= n; i++) {
        ll x1, x2, y1, y2;
        ll m = mid*s[i];
        x1 = x[i]-m; x2 = x[i]+m;
        y1 = y[i]-m; y2 = y[i]+m;
        if (y1 > y2) swap(y1, y2);
        vx.push_back(x1); vx.push_back(x2);
        vy.push_back(y1); vy.push_back(y2);
        vy.push_back(y1+1); vy.push_back(y2-1);
    }
    sort(vx.begin(), vx.end());
    sort(vy.begin(), vy.end());
    vx.erase(unique(vx.begin(), vx.end()), vx.end());
    vy.erase(unique(vy.begin(), vy.end()), vy.end());
    for (int i = 1; i <= n; i++) {
        ll x1, x2, y1, y2;
        ll m = mid*s[i];
        x1 = lower_bound(vx.begin(), vx.end(), x[i]-m)-vx.begin()+1;
        x2 = lower_bound(vx.begin(), vx.end(), x[i]+m)-vx.begin()+1;
        y1 = lower_bound(vy.begin(), vy.end(), y[i]-m)-vy.begin()+1;
        y2 = lower_bound(vy.begin(), vy.end(), y[i]+m)-vy.begin()+1;
        if (y1 > y2) swap(y1, y2);
        pl[x1].push_back({ y1,y2 });
        mi[x2].push_back({ y1,y2 });
        qry[x1].push_back({ y1,y2 });
        qry[x2].push_back({ y1,y2 });
    }
}

bool feasible(ll mid) {
    if (mid == 0) {
        return 1;
    }
    init(mid);
    for (int i = 0; i <= MAXN; i++) {
        while (!mi[i].empty()) {
            auto now = mi[i].back();
            update(now.first, now.second, 1, 444444, 1, -1);
            mi[i].pop_back();
        }
        while (!qry[i].empty()) {
            auto now = qry[i].back();
            qry[i].pop_back();
            if (query(now.first+1, now.second-1, 1, 444444, 1) > 0) {
                if (0) cout << i << " " << now.first << " " << now.second << "\n";
                return 0;
            }
        }
        while (!pl[i].empty()) {
            auto now = pl[i].back();
            update(now.first, now.second, 1, 444444, 1, 1);
            pl[i].pop_back();
        }
    }

    return 1;
}

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    assert(2 <= n && n <= 100000);
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        assert(1 <= s[i] && s[i] <= 1000);
    }
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
        assert(1 <= x[i] && x[i] <= 1000000);
        assert(1 <= y[i] && y[i] <= 1000000);
        int tx = x[i]+y[i];
        int ty = x[i]-y[i];
        x[i] = tx;
        y[i] = ty;
    }

    ll lft = 0, rgt = 1000001, ans = -1;
    while (lft <= rgt) {
        ll mid = (lft+rgt)/2;
        if (feasible(mid)) {
            lft = mid+1;
            ans = mid;
        }
        else {
            rgt = mid-1;
        }
    }

    cout << ans;

    return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, wookje, 욱제, 메시, messi, 풀이, 선린, 선린인터넷고등학교, sunrin, 문제 풀이, 2019 선린 정보 알고리즘경시대회

wookje.kwon's profile image

wookje.kwon

2019-08-26 19:30

Read more posts by this author