[2020.1.1] IOI 2014 Day 2

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

 

1. gondola

코딩 노가다 문제. 3번을 제일 빨리 짠 것 같다.... 어째 가면 갈수록 쉬운 문제를 더 못 푸는 것 같다. 코포 포함

아무튼 문제는 간단하다. 곤돌라 수열은 그냥 1, 2, ... , n인 수열을 회전시킨 수열이다. 그런데 대신 원소를 하나씩 뽑아 n+1, n+2, ... 로 대체할 수 있는 것이다. 1번 문제는 해당 수열이 곤돌라 수열인지 확인하는 문제로, n이하인 숫자 사이의 순서 관계와 중복 원소에 대한 것만 잘 처리해주면 된다. 중복원소 처리를 안 한 상태로 모두 n보다 클 경우 바로 1을 리턴하는 실수를 저질러 시간을 많이 뺏겼다...

2번은 해당 곤돌라 수열을 만드는 방법에 대해 알아내는 것이다. 이 역시 n보다 큰 원소들에 대해 적당히 잘 바꿔주면 된다.

3번이 핵심 문제이다. 3번은 주어진 곤돌라 수열을 만드는 방법의 가짓수를 세는 것이다. 잘 생각해보면 현재 곤돌라 수열에 속한 수들은 이전에 그 자리에 어떤 수가 와도 상관이 없었다가 그 곤돌라가 추가되는 순간에 그 곤돌라를 추가하면 된다. 때문에 어떤 k번째 곤돌라에 대해 이 곤돌라로 대체할 때 그 위치의 가짓수는 아직 최종 곤돌라 수열에서 숫자가 나타나지 않은 것들의 개수라는 것을 알 수 있다. 그리고 이 개수는 어떤 구간에 대해 계속 같다. (정확히는 수열에 존재하는 n보다 크고 크기 관계가 인접한 것 사이에서) 때문에 a^b를 log만에 구하는 것을 잘 이용하여 경우의 수를 구해주면 된다. 자세한 것은 코드 참고.

 

코드

#include "gondola.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 = 101010;
const int INF = INT_MAX >> 1;
const ll LINF = LLONG_MAX >> 1;
const ll mod = 1e9+9;
 
int valid(int n, int arr[]) {
    vector <bool> chk(250050);
    int idx = -1;
    for(int i = 0; i < n; i++) {
        if(arr[i] <= n && idx == -1) {
            idx = i;
        }
        else if(arr[i] <= n) {
            int temp = arr[idx] + i - idx;
            temp %= n;
            if(temp == 0) temp = n;
            if(temp != arr[i]) return 0;
        }
    }
    sort(arr, arr+n);
    for(int i = 1; i < n; i++) {
        if(arr[i] == arr[i-1]) return 0;
    }
    return 1;
}
 
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
    int l = 0;
    vector <int> ori(n, -1);
    for(int i = 0; i < n; i++) {
        l = max(gondolaSeq[i] - n, l);
        if(gondolaSeq[i] <= n && ori[0] == -1) {
            ori[i] = gondolaSeq[i];
            for(int j = 1; j < n; j++) {
                ori[(i+j)%n] = (ori[i] + j) % n;
                if(ori[(i+j)%n] == 0) ori[(i+j)%n] = n;
            }
        }
    }
    if(ori[0] == -1) {
        for(int i = 0; i < n; i++) ori[i] = i + 1;
    }
    vector <pii> temp;
    for(int i = 0; i < n; i++) {
        temp.eb(gondolaSeq[i], i);
    }
    sort(all(temp));
    int idx = 0, last = n + 1;
    for(int i = 0; i < n; i++) {
        if(temp[i].fi > n) {
            replacementSeq[idx++] = ori[temp[i].se];
            while(last < temp[i].fi) {
                replacementSeq[idx++] = last++;
            }
            last++;
        }
    }
    return l;
}
 
ll mypow(ll a, ll b) {
    ll ret = 1;
    while(b) {
        if(b & 1) ret = (ret * a) % mod;
        b >>= 1;
        a = (a * a) % mod;
    }
    return ret;
}
 
int countReplacement(int n, int inputSeq[]) {
    if(!valid(n, inputSeq)) return 0;
    ll ans = n;
    for(int i = 0; i < n; i++) {
        if(inputSeq[i] <= n) ans = 1;
    }
    sort(inputSeq, inputSeq+n);
    int last = n;
    for(int i = 0; i < n; i++) {
        if(inputSeq[i] > n) {
            ans = (ans * mypow(n - i, inputSeq[i] - last - 1)) % mod;
            last = inputSeq[i];
        }
    }
    return ans;
}

 

2. 친구

도대체 내 친구는 이걸 어떻게 풀었는지 모르겠다. 되게 어렵다. 그런데 풀이는 정말 너무 간단하고 아름다운 것 같다.

각 사람에 대해 그 사람을 선택했을 때와 선택하지 않았을 때의 신뢰도를 순서쌍으로 나타내자. (p, q)꼴로 나타낸다고 생각하면 이제 시행을 거꾸로 훑으며 각 시행에서 친구 네트워크를 형성하는 사람 둘을 하나의 사람으로 합칠 것이다.

 

y를 x에 합친다고 생각하고 (즉, 호스트가 x라면) x는 (p, q), y는 (p', q')이라 하면

 

IAmYourFriend의 경우 

1) x만 고르는 경우 --> p->p+q'

2) y만 고르는 경우 --> q->q+p'

3) 둘 다 안 고르는 경우 --> q->q+q'

그래서 p = p+q', q = max(q+p', q+q')이 된다.

 

MyFriendsAreYourFriends의 경우

1) x만 고르는 경우 --> p->p+q'

2) y만 고르는 경우 --> p->q+p'

3) 둘 다 고르는 경우 --> p->p+p'

4) 둘 다 안 고르는 경우 --> q->q+q'

그래서 p = max(p+q', q+p', p+p'), q = q+q'이 된다.

 

WeAreYourFriends의 경우

1) x만 고르는 경우 --> p->p+q'

2) y만 고르는 경우 --> p->q+p'

3) 둘 다 안 고르는 경우 --> q->q+q'

그래서 p = max(p+q', q+p'), q=q+q'이 된다.

 

이렇게 합쳐준 뒤 최종적으로 0번 사람을 골랐을 때와 고르지 않았을 때 중 최댓값을 출력하면 맞게 된다.

 

코드

#include "friend.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 = 101010;
const int INF = INT_MAX >> 1;
const ll LINF = LLONG_MAX >> 1;
const ll mod = 1e9+9;

pii arr[MAX];

int findSample(int n,int c[],int h[],int p[]){
    for(int i = 0; i < n; i++) {
        arr[i].fi = c[i];
    }
    for(int i = n - 1; i > 0; i--) {
        if(p[i] == 2) {
            arr[h[i]].fi = max(arr[h[i]].fi + arr[i].se, arr[h[i]].se + arr[i].fi);
            arr[h[i]].se = arr[h[i]].se + arr[i].se;
        }
        if(p[i] == 1) {
            arr[h[i]].fi = max({
                arr[h[i]].fi + arr[i].se, 
                arr[h[i]].se + arr[i].fi,
                arr[h[i]].fi + arr[i].fi
            });
            arr[h[i]].se = arr[h[i]].se + arr[i].se;
        }
        if(p[i] == 0) {
            arr[h[i]].fi += arr[i].se;
            arr[h[i]].se += max(arr[i].se, arr[i].fi);
        }
    }
    return max(arr[0].fi, arr[0].se);
}

 

3. holiday

꽤 유명한 문제인 것 같다. 우선 알아야 할 사실은 어쨋든 방문한 여행지는 연속된 구간이라는 것이다. 그리고 왼쪽 끝과 오른쪽 끝이 정해지면 그 구간을 최소로 이동하는 날짜가 있을 것이고, 그 날짜를 제외한 날 동안 여행지를 방문할 수 있다. 즉 구간에서 큰 값 몇 개를 더한 값을 알아야 한다. 이는 PST를 이용하면 log n만에 처리할 수 있다. 하지만 여전히 그 구간의 개수가 너무 많다. 여기서 중요한 사실을 하나 알 수 있는데, 하나의 오른쪽 끝점에 대해 최적의 왼쪽 끝점은 단조증가한다는 사실이다. 이 때문에 DNC optimization을 쓸 수 있고, 이를 잘 코딩하면 된다. 최종 시간복잡도는 O(n log^2 n)이 된다.

 

코드

#include"holiday.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 = 101010;
const int INF = INT_MAX >> 1;
const ll LINF = LLONG_MAX >> 1;
const ll mod = 1e9+9;

// ans[i] : i번째 도시를 마지막으로 할 때 최대 방문 개수

struct Node {
    int l = 0, r = 0, c = 0; ll val = 0;
};
Node tree[120*MAX];
vector <ll> num;
int st, d, root[MAX], sz, n;
ll ans;

void expand_tree(int s, int e, int k, int pnd, int cnd) {
    tree[cnd].c = tree[pnd].c + 1;
    tree[cnd].val = tree[pnd].val + num[k];
    if(s == e) return;
    int m = s + e >> 1;
    sz++;
    if(k <= m) {
        tree[cnd].r = tree[pnd].r;
        tree[cnd].l = sz;
        expand_tree(s, m, k, tree[pnd].l, tree[cnd].l);
    }
    else {
        tree[cnd].l = tree[pnd].l;
        tree[cnd].r = sz;
        expand_tree(m+1, e, k, tree[pnd].r, tree[cnd].r);
    }
}

ll cal(int s, int e, int cnt, int pnd, int cnd) {
    if(s == e) return cnt * num[s];
    int m = s + e >> 1, rcnt = tree[tree[cnd].r].c - tree[tree[pnd].r].c;
    ll ret;
    if(rcnt >= cnt) ret = cal(m+1, e, cnt, tree[pnd].r, tree[cnd].r);
    else {
        ll rval = tree[tree[cnd].r].val - tree[tree[pnd].r].val;
        ret = cal(s, m, cnt - rcnt, tree[pnd].l, tree[cnd].l) + rval;
    }
    return ret;
}

void dnc1(int s, int e, int l, int r) {
    if(s > e) return;
    int m = (s + e) >> 1;
    ll tans = -1, temp;
    int idx = l, cnt;
    for(int i = l; i <= r; i++) {
        cnt = d - i + m - min(st - m, i - st);
        cnt = min(cnt, i - m + 1);
        if(cnt < 0) continue;
        temp = cal(0, n-1, cnt, root[m-1], root[i]);
        if(temp > tans) {
            idx = i;
            tans = temp;
        }
    }
    ans = max(ans, tans);
    dnc1(s, m-1, l, idx), dnc1(m+1, e, idx, r);
}

ll findMaxAttraction(int N, int start, int day, int arr[]) {
    st = start + 1, d = day, n = N;
    if(d == 0) return 0;
    for(int i = 0; i < n; i++) {
        num.eb(arr[i]);
    }
    sort(all(num));
    for(int i = 0; i < n; i++) {
        sz++;
        root[i+1] = sz;
        int k = lower_bound(all(num), arr[i]) - num.begin();
        expand_tree(0, n-1, k, root[i], root[i+1]);
    }
    dnc1(1, st, st, n);
    cout << endl;
    return ans;
}