[2019.12.31] IOI 2014 Day 1

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

 

rail은 귀찮아서 풀이를 보지 않았다.

1. rail

끝까지 못 풀었다. 서브태스크 2까지 풀었는데, 0번 역에서 가장 가까운 역은 0번 역에서 D타입 중에 가장 오른쪽 역이니까 이 역의 타입과 위치를 구할 수 있다. 이 역에서 또한 모든 역까지의 거리를 구한 뒤 0번 역에서 어떤 역으로 가는 비용이 0번에서 방금 구한 역까지의 거리와 방금 구한 역에서 어떤 역까지의 거리를 더한 것과 같다면 C 타입이므로 위치와 타입 모두 알 수 있다.

 

코드

#include "rail.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()
#define report(x, l, s) stype[x] = s, location[x] = l, chk[x] = true

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

const int MAX = 5050;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;

int d[4][MAX];
bool chk[MAX], LR[MAX];

void findLocation(int n, int l0, int location[], int stype[]) {
    report(0, l0, 1);
    int mi = INF, i1, i2;
    for(int i = 1; i < n; i++) {
        d[0][i] = getDistance(0, i);
        if(d[0][i] < mi) {
            mi = d[0][i], i1 = i;
        }
    }
    report(i1, l0 + mi, 2);
    int ma = 0;
    for(int i = 1; i < n; i++) {
        if(chk[i]) continue;
        d[1][i] = getDistance(i1, i);
        if(d[0][i] == d[0][i1] + d[1][i]) {
            report(i, location[i1] - d[1][i], 1);
        }
        else {
            report(i, location[0] + d[0][i], 2);
        }
    }
}

 

2. wall

이 문제는 쉬웠나? segment tree랑 lazy propagation을 잘 해주면 된다고 한다. 대회 당시에는 풀이가 상당히 난해?한 것으로 보이나 구간의 최대/최소를 미리 구해 놓은 뒤 max(a[i], X) 또는 min(a[i], X)로 구간 업데이트를 할 때 어떤 구간에서 업데이트가 일어나지 않는 것이 당연하다면 리턴하고, 모든 값이 업데이트 되는 곳까지 깊이 들어가서 Lazy 값을 바꿔주면 놀랍게도 시간 안에 들어간다. 실제로 반례 데이터가 존재하는데, 내가 뚫은 것 같다...

내가 아는 방법으로는 segment tree beats를 쓰면 풀 수 있는 것 같다. min으로 바꾸는 과정에서 구간에서 가장 큰 원소를 제외하고는 min 이하일 때 Tag하는 방식을 max에 대해서도 한다면 (n + q)log n에 된다.

 

3. game

참 다양한 풀이가 있는 것 같지만 가장 간단한 풀이는 이 것으로 보인다.

부모 정점의 번호가 항상 자식 정점 번호보다 작은 트리를 이루고 있다고 생각하는 것이다. 어떤 정점보다 작은 번호의 정점 중 현재 질문으로 들어온 것을 제외하고는 모두 연결되어 있지 않다고 대답했을 때만 그 간선을 이어준다. 그러면 마지막 답 전까지 절대로 연결성 여부를 알 수 없다. 마지막 질문에서 번호가 큰 정점은 아직 부모 정점이 정해져있지 않고, 나머지는 모두 연결되어있기 때문이다.