IOI 2015 Day 2 문제 및 해법

티스토리 뷰

IOI/IOI2015

IOI 2015 Day 2 문제 및 해법

전명우 2015. 7. 30. 12:05

0. 표지

1. horses

말을 한 번 팔 때, 모두 팔아버리는 것이 좋음을 알 수 있다. $i$ 번 해에 말을 파는게 제일 좋기 위한 필요조건은 $i < j$ 인 모든 $j$ 에 대해 $Y[i] \geq X[i+1] \times \dots \times X[j] \times Y[j]$ 를 만족해야한다. 여기서 주목해야할 점은 $Y[i] \leq 10^9$ 라는 것이다. $X[i] > 1$ 인 $i$ 들 중 30개 보다 앞에 있는 날에 말을 파는 것은 안좋다는 것을 알 수 있다. 결국 답으로 가능한 구간이 최대 30개 생기는 꼴인데 매 쿼리마다 각 구간 별로 최대 $Y[i]$ 를 인덱스트리나 세그먼트 트리로 구해놓은 다음에 말을 팔고 남은 최대 이익을 계산하면 된다. 그러면 하나의 쿼리를 $30 \lg N$ 에 조금 비례한 회수의 연산으로 해결할 수 있다.

100

101

102

103

104

105

#include <bits/stdc++.h>
using namespace std;
 
#define MAXN 500005
#define TS 1048576
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
typedef long long lld;
 
static const int MOD = 1e9 + 7;
static int N;
static int X[MAXN], Y[MAXN];
static int tree[TS], ptree[TS], ST = TS/2-1;
static priority_queue <int> que;
 
void write(int n, int v)
{
    n += ST;
    tree[n] = v;
    for (n>>=1;n;n>>=1) tree[n] = max(tree[n+n], tree[n+n+1]);
}
 
void write_p(int n, int v)
{
    n += ST;
    ptree[n] = v;
    for (n>>=1;n;n>>=1) ptree[n] = (lld)ptree[n+n] * ptree[n+n+1] % MOD;
}
 
int get_max(int l, int r)
{
    int ret = 0;
    for (l+=ST,r+=ST;l<=r;l>>=1,r>>=1){
        if (l&1) ret = max(ret, tree[l++]);
        if (!(r&1)) ret = max(ret, tree[r--]);
    }
    return ret;
}
 
int get_product(int l, int r)
{
    int ret = 1;
    for (l+=ST,r+=ST;l<=r;l>>=1,r>>=1){
        if (l&1) ret = (lld)ret * ptree[l++] % MOD;
        if (!(r&1)) ret = (lld)ret * ptree[r--] % MOD;
    }
    return ret;
}
 
int calc()
{
    int max_y = 1e9;
    vector <int> arr = {N+1}, y;
    lld product = 1;
    while (!que.empty()){
        int q = que.top(); que.pop();
        if (X[q] == 1) continue;
        product *= X[q];
        arr.pb(q);
        if (product > max_y) break;
    }
    if (product <= max_y && arr.back() != 1) arr.pb(1);
    reverse(all(arr));
    for (int i=1;i<sz(arr);i++) y.pb(get_max(arr[i-1], arr[i]-1));
    lld acc = 1, mx = X[arr[0]]; int t = 0;
    for (int i=0;i<sz(arr)-1;i++){
        acc *= X[arr[i]];
        if (y[t] < acc/mx*y[i])
            mx = acc, t = i;
    }
    int ret = (lld)get_product(1, arr[t]) * y[t] % MOD;
    for (int t: arr) if (X[t] > 1) que.push(t);
    return ret;
}
 
int init(int n, int x[], int y[])
{
    N = n;
    for (int i=1;i<=N;i++) X[i] = x[i-1], Y[i] = y[i-1];
    for (int i=1;i<=N;i++) if (X[i]) que.push(i);
    for (int i=1;i<=N;i++) tree[ST+i] = Y[i], ptree[ST+i] = X[i];
    for (int i=ST;i;i--){
        tree[i] = max(tree[i+i], tree[i+i+1]);
        ptree[i] = (lld)ptree[i+i] * ptree[i+i+1] % MOD;
    }
    return calc();
}
 
int updateX(int n, int v)
{
    n++;
    if (v > 1 && X[n] == 1) que.push(n);
    X[n] = v;
    write_p(n, v);
    return calc();
}
 
int updateY(int n, int v)
{
    n++;
    Y[n] = v;
    write(n, v);
    return calc();
}

2. sorting

문제: task-2_en-KOR_rev80.pdf

우선 가장 먼저 파라매트릭 서치를 생각할 수 있다. $R$ 라운드 이내에 정렬이 가능하다고 가정하고 답이 되는지 확인한다. 파라매트릭 서치가 되는 이유는 $R$ 라운드에 정렬이 가능하면 $R+1, R+2, \dots, M$ 라운드에도 항상 정렬이 가능하기 때문이다. $R$ 라운드에 정렬이 완료되고 나서 이후 라운드에서는 에르맥이 스왑한 것만 따라 스왑하면 항상 정렬 상태를 유지할 수 있기 때문이다.

파라매트릭 서치로 $R$ 을 정했을 때, $R$ 라운드에 답이 되는지 확인하는 방법을 설명하겠다. 기본적인 아이디어는 아이잔이 앞으로 수열을 전혀 안건드렸을 때, 오직 에르맥의 스왑으로 각 수들이 어느 위치로 가는지 계산한다. 그러면 아이잔은 에르맥의 움직임에 맞춰 최후에 정렬되도록 적절히 스왑해주면 된다.

예제 1번의 경우를 예로 들겠다. $R = 3$ 일 때 가능한지 확인한다.

에르맥	(0, 1)	에르맥의 이동 경로: 0 3 1 2 4 수열: 3 4 2 1 0
아이잔	(1, 0)	에르맥의 이동 경로: 0 3 1 2 4 아이잔 수열: 4 3 2 1 0
에르맥	(1, 2)	에르맥의 이동 경로: 0 1 3 2 4 아이잔 수열: 4 2 3 1 0
아이잔	(0, 4)	에르맥의 이동 경로: 0 1 3 2 4 아이잔 수열: 0 2 3 1 4
에르맥	(2, 3)	에르맥의 이동 경로: 0 1 2 3 4 아이잔 수열: 0 2 1 3 4
아이잔	(1, 2)	에르맥의 이동 경로: 0 1 2 3 4 아이잔 수열: 0 1 2 3 4

위 표에서 에르맥의 이동 경로가 0 3 1 2 4라 함은 아이잔 수열에서 0번 위치에 있는 수가 아이잔이 가만히 있는다고 했을 때 0의 위치로 가고 1번 위치에 있는 수가 3번 위치에, 2번 위치에 있는수가 1번 위치에, 3번 위치에 있는 2번 위치에, 4번 위치에 있는 수가 4번 위치에 간다는 뜻이다. 이후 정렬되어 있으면 $R$ 라운드 안에 마침이 가능하다는 것이고, 아니라면, 불가능하다는 것이다. 방법을 보면 에르맥의 스왑 정보와 상관 없이 적어도 $N-1$ 라운드 안에는 끝남이 보장된다. 시간복잡도는 $O(N \lg N)$ 이다.

#include <bits/stdc++.h>
using namespace std;
 
#define MAXN 200005
#define MAXM 600005
#define mp make_pair
typedef pair<int, int> pii;
 
static int N, M;
static int A[MAXN], B[MAXN], C[MAXN];
static int pos_b[MAXN], pos_c[MAXN];
static int X[MAXM], Y[MAXM];
static int P[MAXM], Q[MAXM];
 
bool proc(int m)
{
    for (int i=1;i<=N;i++){
        B[i] = pos_b[i] = i;
        C[i] = A[i], pos_c[C[i]] = i;
    }
    for (int i=m;i;i--){
        swap(B[X[i]], B[Y[i]]);
        swap(pos_b[B[X[i]]], pos_b[B[Y[i]]]);
    }
    queue <int> que;
    for (int i=1;i<=N;i++) if (B[i] != C[i])
        que.push(B[i]);
    for (int i=1;i<=m;i++){
        swap(B[X[i]], B[Y[i]]);
        swap(pos_b[B[X[i]]], pos_b[B[Y[i]]]);
        swap(C[X[i]], C[Y[i]]);
        swap(pos_c[C[X[i]]], pos_c[C[Y[i]]]);
        while (!que.empty() && pos_b[que.front()] == pos_c[que.front()]) que.pop();
        if (!que.empty()){
            int q = que.front(); que.pop();
            int x = pos_b[q], y = pos_c[q];
            swap(C[x], C[y]);
            swap(pos_c[C[x]], pos_c[C[y]]);
            P[i] = x, Q[i] = y;
        }else{
            P[i] = Q[i] = 1;
        }
    }
    for (int i=1;i<=N;i++) if (C[i] != i) return 0;
    return 1;
}
 
int findSwapPairs(int n, int S[], int m, int x[], int y[], int to_p[], int to_q[])
{
    N = n, M = m;
    for (int i=1;i<=M;i++) X[i] = x[i-1]+1, Y[i] = y[i-1]+1;
    for (int i=1;i<=N;i++) A[i] = S[i-1]+1;
    bool sw = 0;
    for (int i=1;i<=N;i++) if (A[i] != i) sw = 1;
    if (!sw) return 0;
    int s = 1, e = N-1, ret;
    while (s <= e){
        int m = (s+e)>>1;
        if (proc(m)) e = m-1, ret = m;
        else s = m+1;
    }
    proc(ret);
    for (int i=1;i<=ret;i++) to_p[i-1] = P[i]-1, to_q[i-1] = Q[i]-1;
    return ret;
}

3. towns

문제: task-3_en-KOR_rev87.pdf

0번 도시에서 제일 먼 도시를 찾는다. 그 도시의 번호가 $X$ 번이라 하자. $X$ 번 도시에 대해 제일 먼 도시를 찾는다. 그 도시의 번호가 $Y$ 번이라 하자. 트리의 지름이 $dist(X, Y)$ 임을 알 수 있다. 지금까지 질의 회수는 $2N - 3$ 이다.

여러 가지 증명이 필요한 명제들이 있다. 글에서 증명은 생략하겠다.

1) 트리의 지름이 여러가지일 수 있다. 그러나 허브는 임의의 한 지름의 위에만 존재한다.

2) 허브는 최대 2개다.

3) 1번에서 더 확장하여 허브는 0번 도시와 X번 도시 사이의 경로 위에만 존재한다. (즉, 아래 그림에서 빨간색 대도시는 허브가 될 수 없다.)

$dist(0, i)$ 와 $dist(X, i)$ 를 이용해서 $i$ 번 도시에서 0번 도시에서 $X$ 번 도시로 가는 경로 상에 위치한 가장 가까운 대도시와의 거리를 구할 수 있다. (그림에서 파란색 가상 간선의 길이) 마찬가지로 $X$ 번 도시에서 경로 상에 위치한 대도시 와의 거리들(그림에서 초록색 선에 해당)도 구할 수 있다. 이 정보로 경로상에 위치한 대도시의 개수, 허브, 그리고 $R$ 값을 알 수 있다. 이 때 추가 질의 회수는 없다.

구한 허브에 대해서 그 허브가 균형 잡힌 허브인지 확인하는 것이 까다롭다. 그림에서 검정색 대도시들 중 허브가 있을 텐데, 허브에 딸린 파란색 도시들의 개수가 $\frac{N}{2}$ 보다 많다면, 추가적으로 질의를 하여 $\frac{N}{2}$ 보다 큰 파란색 도시 그룹이 나오는지 확인을 해주어야한다. 위에서 말한대로 최대 2개의 허브가 있을 수 있는데, 이러한 추가 확인 작업은 최대 한 개의 허브에 대해서만 해주면 된다. 그 이유는 파란색 도시들을 $\frac{N}{2}$ 개 보다 많게 가지고 있는 허브는 최대 한 개이기 때문이다.

추가 확인 작업은 $n$ 개의 원소가 있고, 원소끼리 비교하는 질의만 가능할 때 같은 값을 가지는 원소의 개수가 $\frac{n}{2}$ 보다 많이 있는지, 있다면 몇 개인지 계산하는 문제로 바꾸어 풀 수 있다. 최대 $\frac{3}{2} n$ 질의 만에 할 수 있다. Majority Vote Algorithm 포스트에 자세히 적혀있다.

#include <bits/stdc++.h>
using namespace std;
 
#define pb push_back
#define sz(v) ((int)(v).size())
 
int getDistance(int i, int j);
 
static int N, X, Y;
static int w[111][111];
static int L[111], P[111];
 
inline int get(int a, int b)
{
    if (a == b) return 0;
    if (!w[a][b])
        w[a][b] = w[b][a] = getDistance(a, b);
    return w[a][b];
}
 
inline bool is_in_same_group(int a, int b)
{
    return P[a] + P[b] - get(a, b);
}
 
bool is_over_size(vector <int> cand)
{
    vector <int> arr[7], chk[7];
    arr[0] = cand;
    for (int i=0;i<7;i++){
        chk[i].resize(sz(arr[i]), 0);
        for (int j=0;j+1<sz(arr[i]);j+=2){
            if (is_in_same_group(arr[i][j], arr[i][j+1])){
                arr[i+1].pb(arr[i][j]);
                chk[i][j] = chk[i][j+1] = 1;
            }
        }
    }
    int rep = -1, sum = 0;
    for (int i=7;i--;) if (sz(arr[i]) & 1){
        rep = arr[i].back();
        break;
    }
    if (rep == -1) return 0;
    for (int i=0;i<7;i++){
        for (int j=0;j<sz(arr[i]);j++) if (!chk[i][j]){
            if (is_in_same_group(arr[i][j], rep))
                sum += (1 << i);
        }
    }
    return sum > N/2;
}
 
int hubDistance(int leafs, int sub)
{
    N = leafs;
    for (int i=0;i<N;i++){
        for (int j=0;j<N;j++) w[i][j] = 0;
        P[i] = L[i] = 0;
    }
    X = 1, Y = 0;
    for (int i=2;i<N;i++){
        if (get(0, X) < get(0, i))
            X = i;
    }
    for (int i=1;i<N;i++) if (get(X, Y) < get(X, i)) Y = i;
    int R = 2e9;
    for (int i=1;i<N;i++) if (i != X){
        P[i] = (get(0, i) + get(X, i) - get(0, X)) / 2;
        L[i] = get(X, i) - P[i];
        R = min(R, max(L[i], get(X, Y)-L[i]));
    }
    int t = 0, cnt = 0, small = 0;
    L[0] = get(0, X);
    for (int i=0;i<N;i++){
        if (L[i] == R) cnt++;
        if (L[i] < R) small++;
    }
    if (cnt && small <= N/2 && N-cnt-small <= N/2){
        if (cnt > N/2) t = R;
        else return R;
    }
    cnt = small = 0;
    for (int i=0;i<N;i++){
        if (L[i] == get(X, Y) - R) cnt++;
        if (L[i] < get(X, Y) - R) small++;
    }
    if (cnt && small <= N/2 && N-cnt-small <= N/2){
        if (cnt > N/2) t = get(X, Y) - R;
        else return R;
    }
    if (!t) return -R;
    vector <int> cand;
    for (int i=0;i<N;i++) if (L[i] == t)
        cand.pb(i);
    if (is_over_size(cand)) return -R;
    return R;
}

저작자표시

'IOI > IOI2015' 카테고리의 다른 글

IOI 2015 Day 1 문제 및 해법 (0)	2015.07.28
IOI2015 개막 . 연습 세션 문제 설명 (0)	2015.07.28

공유하기 링크

페이스북
카카오스토리
트위터

공지사항

최근에 올라온 글

최근에 달린 댓글

Total

Today

Yesterday

링크

TAG more

« 2025/03 »
일	월	화	수	목	금	토
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

글 보관함

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

PS 이야기

티스토리 뷰