본문 바로가기

Computer Science/Competition

2019 ICPC 한국 리저널 인터넷예선 풀이

Note: 아직 미 완성인 글입니다.

 

20.06.03: A, B, C, D, F, H, I, J, L 풀이 수록

 

문제는 다음 사이트에서 일부 해결해볼 수 있다: 링크

A. All You Need is Dating

$i$번째 IC 학생이 원하는 데이트의 최소 횟수를 $minIC_i$, 최대 횟수를 $maxIC_i$로 표기하자. 비슷하게 $minPC_j$와 $maxPC_j$를 정의하자. 그러면, 이 문제는 아래와 같이 간선을 지나가는 유량의 최소 제한과 최대 제한이 있는 플로우 그래프로 모델링 가능하다.

이는 전형적인 LR-flow 문제로, 해결법이 널리 알려져 있다. 일반적인 네트워크 플로우 알고리즘을 사용하여 해결하는 방법과 MCMF를 활용하는 방법이 있는데, 이 글에서는 생략한다.

B. Balanced String

$D[i][j = -1, 0, 1]$를 길이 $i$이고 $1$과 $0$의 개수 차이가 $j$인 균형잡힌 문자열의 수로 정의하면 동적 계획법을 통해 쉽게 해결할 수 있다. 혹은 이 점화식을 손으로 직접 해결하여 구현해도 된다.

 

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

typedef long long ll;

const ll mod = 16769023;

int N;
ll D[100005][3];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    D[1][0] = 1, D[1][1] = 0, D[1][2] = 1;
    for (int i=2; i<=N; i++){
        D[i][0] = D[i-1][1];
        D[i][1] = (D[i-1][0] + D[i-1][2])%mod;
        D[i][2] = D[i-1][1];
    }
    cout << (D[N][0]+D[N][1]+D[N][2])%mod << endl;
}

C. Byte Coin

단순한 그리디한 방법을 통해 해결할 수 있다. $i$일에 다음과 같은 행동을 하면 된다:

  • 모든 코인을 매도한다.
  • $i+1$일의 가격이 $i$일보다 높으면, 코인을 최대한 많이 매수한다.
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int N;
ll W, A[20];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >>N >> W;
    for (int i=0; i<N; i++) cin >> A[i];
    for (int i=1; i<N; i++){
        if (A[i] > A[i-1]){
            ll c = W/A[i-1];
            W -= A[i-1]*c;
            W += A[i] * c;
        }
    }
    cout << W << endl;
}

D. Canal

문제에 주어진 기하적인 상황이 다소 비직관적이므로, 다음과 같이 상황을 바꾸어 생각하자.

$n$개의 순서쌍 $(x_i, y_i) \in \mathbb{Z}^2$이 주어진다.
$\min_{a, b \in \mathbb{R}} \max_{1 \le i \le n} \min(|x_i - a|, |y_i - b|)$을 구하여라.

이 문제를 이분 탐색을 통해 접근한다면 다음과 같이 결정문제로 다시 쓸 수 있다.

$\max_{1 \le i \le n} \min(|x_i - a|, |y_i - b|) \le d$를 만족시키는 $a$, $b$가 존재하는가?

편의상 $(x_i, y_i)$가 $x$ 좌표 순으로 정렬되어 있다고 하자. $a$ 값을 골랐을 때 $|x_i - a| \le d$를 만족시키는 인덱스 $i$들은 연속적으로 위치한다. 따라서, 만약 인덱스들의 $y$ 좌표 값의 prefix/suffix min/max 값을 저장 해두었다면, 고정된 $a$에 대해 문제의 조건을 만족하는 $b$ 값의 존재성을 $O(1)$에 확인할 수 있다.

 

결론적으로, 결정문제를 해결하는 것은 투 포인터 기법을 통해 양 끝의 $x$ 좌표 값의 범위가 $2d$ 이하인 구간들을 살펴보면서 해결해주면 된다. 총 시간복잡도는 $O(n \log X + n \log n)$이 된다. 아래 구현을 보는 것이 풀이 이해에 더 용이할 것으로 생각된다.

 

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

typedef long long ll;

typedef pair<ll, ll> pi;

int N;
pi A[300005];
ll pmax[300005], pmin[300005];
ll smax[300005], smin[300005];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << setprecision(1) << fixed;
    cin >> N;
    if (N == 1){
        cout << 0.0 << endl;
        return 0;
    }
    for (int i=1; i<=N; i++){
        cin >> A[i].first >> A[i].second;
    }
    sort(A+1, A+N+1);
    pmin[0] = smin[N+1] = (1E9)+1;
    pmax[0] = smax[N+1] = -(1E9)-1;
    for (int i=1; i<=N; i++){
        pmin[i] = min(pmin[i-1], A[i].second);
        pmax[i] = max(pmax[i-1], A[i].second);
    }
    for (int i=N; i; i--){
        smin[i] = min(smin[i+1], A[i].second);
        smax[i] = max(smax[i+1], A[i].second);
    }
    
    ll lo = 0, hi = ((ll) 2E9) + 1; // (lo, hi]
    while (lo+1 < hi){
        ll mid = (lo + hi)/2;
        int st = 1, ed = 1;
        bool able = false;
        while (ed <= N){
            while (st < ed && A[ed].first - A[st].first >= mid) st++;
            ll m = (1E9)+1, M = -(1E9)-1;
            if (st > 1){
                m = min(m, pmin[st-1]);
                M = max(M, pmax[st-1]);
            }
            if (ed < N){
                m = min(m, smin[ed+1]);
                M = max(M, smax[ed+1]);
            }
            if (M - m < mid){
                able = true;
                break;
            }
            ed++;
        }
        if (able) hi = mid;
        else lo = mid;
    }
    cout << lo*0.5 << endl;
}

E. Choreography

F. Dryer

가능한 $t$의 값이 총 $40 \le t \le 100$으로 61가지이다. 같은 $t$ 값을 가지는 옷들은 동시에 처리해줘도 됨은 명백하다.

 

$k$개의 dryer의 온도를 각각 어떤 값으로 고정시켰을 때 최소 시간안에 건조를 마치는데에 다음 전략이 유효하다.

 

$t$값이 작은 옷 부터 차례로 dryer에 다음과 같이 배정한다:

  • $k$개 중 하나의 어느 dryer에 넣었을 때 해당 dryer의 작동시간에 영향을 주지 않는 경우, 그 dryer에 배정해주면 된다.
  • 아니라면, 옷이 손상되지 않는 범위 내에서 가장 온도가 높은 dryer에 배정한다.

이 경우, 총 시간복잡도는 $O(61^{k+1})$이 된다.

G. Enumeration

H. Four Squares

$D[n]$을 합이 $n$과 같게 되는 제곱수들의 최소 개수로 정의하고 동적 계획법을 수행하면 된다. 총 $O(n \sqrt{n})$ 시간에 해결할 수 있다.

 

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

int N;
int D[100001];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    fill(D, D+100001, 5);
    cin >> N;
    D[0] = 0, D[1] = 1;
    for (int i=2; i<=N; i++){
        for (int j=1; j*j<=i; j++){
            D[i] = min(D[i], D[i-j*j]+1);
        }
    }
    cout << D[N] << endl;
}

I. Registration

대회 전에 미리 DomJudge ID와 패스워드를 기록해둬야 해결할 수 있다. 대회 중에 이메일로 전송된 패스워드를 확인하는 것은 규정 위반이다.

J. Star Trek

$D[i]$를 $i$번 행성까지 가는데 걸리는 최소 시간으로 정의하여 동적 계획법을 활용하면 된다. $T[i]$를 행성 $i$에서의 준비 시간, $P[i]$를 행성 $i$에서 출발할 때의 pace, $A[i]$를 $1$번 행성으로 부터 거리라고 하면, 다음과 같은 점화식이 나온다:

$$D[i] = \min_{j < i} (P[j] \times A[i]) - P[j]A[j] +T[j] + D[j].$$

 

이는 직선 $P[j] x - (P[j]A[j] + T[j] + D[j])$의 $x = A[i]$ 에서의 최소값으로 생각할 수 있다. 따라서, Convex Hull Trick을 이용하여 $O(N \log N)$ 시간에 해결하면 된다. 나는 LineContainer.h 로 널리 알려진 자료구조를 사용했다. 자료구조 코드 출처: 링크

 

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

typedef long long ll;

bool Q;
struct Line {
	mutable ll k, m, p;
	bool operator<(const Line& o) const {
		return Q ? p < o.p : k < o.k;
	}
};

struct LineContainer : multiset<Line> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	const ll inf = LLONG_MAX;
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(iterator x, iterator y) {
		if (y == end()) { x->p = inf; return false; }
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(ll k, ll m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	ll query(ll x) {
		assert(!empty());
		Q = 1; auto l = *lower_bound({0,0,x}); Q = 0;
		return l.k * x + l.m;
	}
} cht;

int N;

ll D[100005];
ll A[100005];
ll P[100005];
ll T[100005];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    for (int i=1; i<N; i++){
        cin >> A[i];
        A[i] += A[i-1];
    }
    for (int i=0; i<N-1; i++){
        cin >> T[i] >> P[i];
    }
    for (int i=1; i<N; i++){
        cht.add(-P[i-1], A[i-1]*P[i-1]-T[i-1]-D[i-1]);
        D[i] = -cht.query(A[i]);
    }
    cout << D[N-1] << endl;
}

K. Steel Slicing

L. Two Machines

2015 KAIST 5th ACM-ICPC Mock Competition G번과 완전히 같은 문제이다.

 

$D[i][t]$를 $i$번째 작업까지 해결하면서 기계 $A$를 $t$시간 사용할 때 기계 $B$를 사용해야 하는 시간으로 정의하고, 동적 계획법을 사용하면 된다고 한다.

'Computer Science > Competition' 카테고리의 다른 글

UCPC 2020 참가 후기  (0) 2020.08.01
2019 ICPC 한국 리저널 인터넷예선 풀이  (0) 2020.06.03
Google Code Jam Round 1C  (0) 2020.05.03
Educational Codeforces Round 86  (0) 2020.04.30
Google Hash Code 2020 참가 후기  (0) 2020.02.21