[2019.12.25] JOI spring camp 2018/2019 Day 1

https://oj.uz/problems/source/376

중간에 논 시간을 제외하고 대략 5~6시간 정도 풀었다. 총 229점.

 

1. Examination(시험)

우선 학생들을 두 시험의 합이 큰 순서대로 정렬하자. 그리고 쿼리 또한 C가 큰 순서대로 정렬하면 쿼리를 처리할 때 두 시험의 합이 C 이상인 학생만 고려하면 되기 때문에 스위핑으로 이 조건을 해결할 수 있다. 나머지 A와 B 조건은 평면에서 x>=A이고 y>=B인 구간에서 점의 개수를 세는 것이기 때문에 2D BIT 등을 활용하여 점의 개수를 세줄 수 있다. 2D BIT를 처음으로 짜 봐서 이상하게 짠 것 같은데, 괜찮은 구현을 찾지 못하겠다...

 

코드

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()
 
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
const int MAX = 101010;
const int INF = (1 << 30) - 1;
const ll LINF = 1LL << 60;
 
int ans[MAX], n, q;
pii arr[MAX];
vector <int> S, T[MAX], tree[MAX];
struct Query {
    int a, b, c, idx;
} query[MAX];
 
void update(int x, int y, int val) {
    x = upper_bound(all(S), x) - S.begin();
    while(x <= n) {
        int temp = upper_bound(all(T[x]), y) - T[x].begin();
        while(temp <= T[x].size()) {
            tree[x][temp] += val;
            temp += (temp & -temp);
        }
        x += (x & -x);
    }
}
 
int cal(int x, int y) {
    x = upper_bound(all(S), x) - S.begin();
    int ret = 0;
    while(x > 0) {
        int temp = upper_bound(all(T[x]), y) - T[x].begin();
        while(temp > 0) {
            ret += tree[x][temp];
            temp -= (temp & -temp);
        }
        x -= (x & -x);
    }
    return ret;
}
 
int main () {
    ios::sync_with_stdio(false); cin.tie(nullptr);
 
    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        cin >> arr[i].fi >> arr[i].se;
        S.eb(arr[i].fi);
    }
    sort(all(S));
    for(int i = 1; i <= n; i++) {
        int temp = upper_bound(all(S), arr[i].fi) - S.begin();
        while(temp <= n) {
            T[temp].eb(arr[i].se);
            temp += (temp & -temp);
        }
    }
    for(int i = 1; i <= n; i++) {
        tree[i].resize(T[i].size()+10);
        sort(all(T[i]));
    }
    sort(arr+1, arr+n+1, [](pii a, pii b) {
        return a.fi + a.se > b.fi + b.se;
    });
    
    for(int i = 1; i <= q; i++) {
        cin >> query[i].a >> query[i].b >> query[i].c;
        query[i].idx = i;
    }
    sort(query+1, query+q+1, [](Query X, Query Y) {
        return X.c > Y.c;
    });
    int idx = 1;
    for(int i = 1; i <= q; i++) {
        while(idx <= n && arr[idx].fi + arr[idx].se >= query[i].c) {
            update(arr[idx].fi, arr[idx].se, 1);
            idx++;
        }
        ans[query[i].idx] = cal(1000000000, 1000000000) 
                            - cal(1000000000, query[i].b-1) - cal(query[i].a-1, 1000000000) 
                            + cal(query[i].a-1, query[i].b-1);
    }
    for(int i = 1; i <= q; i++) {
        cout << ans[i] << '\n';
    }
}

 

 

2. Meetings

결론부터 말하자면 못 풀었다. 만약 a, b, c로 회의를 열었는데 모이는 장소가

1. a인 경우 --> b - a - c 순서로 일직선에 존재

2, 3. b 또는 c인 경우 : 마찬가지

4. 다른 점인 경우 : a를 루트로 한 트리에서 b, c의 LCA가 그 점

이기 때문에 루트를 0으로 정하고 정점을 추가하는 방식으로 구했다. 이를 재귀적으로 했는데, a를 루트로 할 때 b를 넣는다 생각하면 (이를 f(a, b)라 하자.)

1. 만약 a에게 자식이 없다면 a 자식에 b를 추가하고 b의 부모를 a로 한다.

2. 만약 a의 다른 자식 c에 대하여 Query(a, b, c)가 a가 아니라면

  1) b일 경우 : a-b-c 순서이므로 b의 부모를 a, c의 부모를 b로 한다. 자식 관계도 적절히 바꿔주고 리턴.

  2) c일 경우 : b가 c의 자식이므로 f(c, b)를 하고 리턴.

  3) 다른 경우 : 그 점을 u라 하면 b, c의 부모를 u로 하고 u의 부모를 a로 한다. u가 b, c의 LCA이기 때문에. 그 후 리턴

이런 방식으로 끼워넣으면 한 정점에서 연결된 간선이 최대 18개라 대략 호출 횟수랑 시간복잡도 모두 n^2 * 18 정도라고 생각했는데, 마지막 섭테에서 49점이 아니라 TLE로 0점이 뜨는 것을 보고 조금 의아했다. 아무튼 만점 풀이는 아니니까...

 

코드

#include "meetings.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 2020;
const int INF = (1 << 30) - 1;
const ll LINF = 1LL << 60;

int p[MAX];
vector <int> c[MAX];

void add(int a, int b) {
    bool flag = false;
    for(int i = 0; i < c[a].size(); i++) {
        int mid = Query(a, c[a][i], b);
        if(mid == a) continue;
        flag = true;
        if(mid == c[a][i]) {
            add(c[a][i], b);
            break;
        }
        else if(mid == b) {
            p[b] = a;
            p[c[a][i]] = b;
            c[b].eb(c[a][i]);
            c[a][i] = b;
            return;
        }
        else {
            p[c[a][i]] = mid;
            p[b] = mid;
            p[mid] = a;
            c[mid].eb(c[a][i]);
            c[mid].eb(b);
            c[a][i] = mid;
            return;
        }
    }
    if(!flag) {
        p[b] = a, c[a].eb(b);
        return;
    }
}

void Solve(int n) {
    for(int i = 1; i < n; i++) p[i] = -1;
    for(int i = 1; i < n; i++) {
        if(p[i] == -1) add(0, i);
    }
    for(int i = 1; i < n; i++) {
        Bridge(min(i, p[i]), max(i, p[i]));
    }
}

 

3. Naan(난)

처음에는 그리디하게 현재 남은 조각에서 가장 적게 자를 수 있도록 하는 사람을 선택해서 계속 짜르도록 시키는 방법을 생각했다. 증명은... 음 못하겠는데 생각해보면 맞는 것 같아서 짰는데 29점이 나왔다. 보니까 분모가 10^9을 넘어간단다... 당연한 것이 분모가 최대 n * 10^9라 당연히 넘는다. 그리고 사실 이 방법을 할 때 각 사람에 대해 다음 자르는 위치를 구하는 것을 이분탐색으로 해야 하기 때문에 시간도 매우 타이트해서 에라 모르겠다 하고 다른 사람 코드를 봤다. 잘 생각해보니 -1인 경우는 있을 수 없었다. 각 사람마다 처음부터 n등분 한다 생각했을 때의 분할점을 생각하자. 1번째 분할 점 중 가장 작은 것, 2번째 분할 점 중 가장 작은 것, ... 를 고르면 항상 각 조각에 대해 해당 사람이 먹는 양이 조건을 만족시킨다는 것을 알 수 있다. 해당 분할을 가져가기 전 분할점은 항상 자신의 이전 분할점보다 전에 있으니까... 꽤 멋있는 그리디 문제였으나 분수 계산을 해야한다는 점이 화나긴 했다. 아무튼 디버깅 하는데 애를 많이 썼던 문제.

 

코드

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 2020;
const int INF = (1 << 30) - 1;
const ll LINF = 1LL << 60;

int n, k, p[MAX];
ll v[MAX][MAX], sum[MAX][MAX];
pll X[MAX], dv[MAX][MAX];
bool chk[MAX];

bool small(pll x, pll y) {
    if(x.fi / x.se == y.fi / y.se) return (x.fi % x.se) * y.se > (y.fi % y.se) * x.se;
    else return x.fi / x.se > y.fi / y.se;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= k; j++) {
            cin >> v[i][j];
            sum[i][j] = sum[i][j-1] + v[i][j];
        }
        int idx = 0;
        for(int j = 1; j < n; j++) {
            while(sum[i][idx+1] * n <= sum[i][k] * j && idx < k) idx++;
            dv[i][j] = make_pair(sum[i][k] * j - sum[i][idx] * n, n * v[i][idx+1]);
            dv[i][j].fi += dv[i][j].se * idx;
        }
        dv[i][n] = make_pair(k, 1);
    }
    for(int i = 1; i <= n; i++) {
        int idx = -1;
        for(int j = 1; j <= n; j++) {
            if(chk[j]) continue;
            if(idx == -1 || small(dv[idx][i], dv[j][i])) {
                idx = j;
            }
        }
        chk[idx] = true;
        p[i] = idx;
        X[i] = dv[idx][i];
    }

    for(int i = 1; i < n; i++) {
        cout << X[i].fi << ' ' << X[i].se << endl;
    }
    for(int i = 1; i <= n; i++) {
        cout << p[i] << ' ';
    }
}