Codeforces Global Round 24

Dashboard - Codeforces Global Round 24 - Codeforces

서론

이 대회 직전에 BOJ 대회에 6시간 동안 참가하였다.

컨디션이 너무 나빴다.

레이팅이 나락 갈 가능성이 높다고 온몸이 말해주고 있었다.

하지만 오늘 퍼플 복귀에 실패하면 한동안 블루로 살아야만 하였다.

대회 도중 뇌정지가 많이 왔지만 다행히 퍼플 복귀는 성공하였다.

 

A - Doremy's Paint

ps 복귀 이후 코포에서 만난 문제 중 제일 쓰레기 같은 문제이다.

l = 1, r = N이 너무 자명해서 문제를 잘못 이해한 줄 알았다.

아무리 읽어도 잘못 이해한 것 같지는 않아서 그냥 제출하였다.

00:02 AC

 

B - Doremy's Perfect Math Class

감이 잘 안 왔는데 많이 풀리고 있었다.

주어지는 연산이 유클리드 알고리즘과 유사한 것 같아 그냥 모든 수의 gcd를 출력하도록 하였다.

00:11 AC

 

C - Doremy's City Construction

정점 x에 대하여 자신보다 작은 정점의 집합을 U 그리고 자신보다 큰 정점의 집합을 V라고 하자.

문제의 조건에 따라 서로 다른 집합에 속하는 두 정점과 동시에 관계를 맺을 수는 없다.

따라서 U와 V 중 크기가 더 큰 집합에 속하는 모든 정점과 관계를 맺으면 된다.

 

하지만 이렇게 하다 보면 문제의 조건을 위반하게 된다.

집합 V와 관계를 맺기 위해서는 기존에 집합 U와 맺었던 모든 관계를 끊어주어야 한다.

구체적으로는 아래와 같이 구현할 수 있다.

 

우선 a를 정렬하고 모든 원소에 대하여 |U|와 |V|를 구하자.

|U|가 더 크다면 현 상태를 그대로 유지하면 된다.

|V|가 더 크다면 |U|개의 관계를 끊고 |V|개의 관계를 새로 맺으면 된다.

 

코너 케이스가 하나 존재한다.

00:33 WA

코너 케이스 처리를 잘못하였다.

00:34 AC

 

정해가 더 깔끔하고 증명도 자명하기에 정해를 소개한다.

결국 이 문제는 모든 정점을 두 개의 집합 U와 V로 분할하는 문제이다.

이때 U의 최댓값은 V의 최솟값보다 작아야만 한다.

가능한 관계의 수는 |U| × |V|이므로 이를 최대화하면 된다.

 

나의 풀이도 정해와 매우 유사하다.

하지만 제대로 된 증명 없는 그리디한 접근이 우연히 맞은 것이다.

에디토리얼을 읽고 나서야 동작 원리를 명확하게 이해할 수 있었다.

 

D - Doremy's Pegging Game

두 원소 x와 y 사이의 거리를 d(x, y) = min(abs(y - x), N - abs(y - x))라고 정의하자.

그리고 게임이 종료되었을 때 남아 있는 원소 중 거리가 가장 먼 두 원소를 u와 v라고 하자.

u와 v를 제외한 나머지 (N - 2)개의 원소의 상태를 살펴보자.

 

u와 v 사이에 있는 원소의 개수는 (d(u, v) - 1)개이다.

이들은 게임의 종료 여부에 아무런 영향도 미치지 않는다.

 

나머지 원소의 개수는 (N - d(u, v) - 1)개이다.

이들은 반드시 제거되어야 하는데 이때 제거 순서가 매우 중요하다.

임의의 순서로 제거하면 게임이 보다 일찍 끝날 수 있다.

 

마지막 원소를 제거하기 직전에는 게임이 유효한 상태여야 한다.

그리고 마지막 원소를 제거하는 순간 게임이 종료되어야 한다.

이를 만족하는 원소의 개수는 (d(u, v) + 2 - N % 2)개이다.

 

위의 내용을 종합하면 다음과 같이 정답을 구할 수 있다.

for i = 0; i < N; ++i

    for j = i + 1; j < N; ++j

        for k = 0; k <= d(i, j); ++k

            ans += nCr(d(i, j), k) * fact[N - d(i, j) + k - 3] * (d(i, j) + 2 - N % 2);

 

하지만 위의 코드는 O(N^3)으로 TLE를 받는다.

잘 관찰해보면 i와 j의 값은 d(i, j)의 계산에만 사용되는 것을 알 수 있다.

따라서 d(i, j)의 발생 빈도를 미리 계산해놓으면 다음과 같이 O(N^2)에 정답을 구할 수 있다.

 

for i = 0; i < (N - 1) / 2; ++i

    for j = 0; j <= i; ++j

        ans += A[i] * nCr(i, j) * fact[N - i + j - 3] * (i + 2 - N % 2);

 

N이 짝수일 때는 단 하나의 원소만 남는 경우가 생길 수 있다.

이 경우는 별도로 처리해주자.

 

01:10 TLE

당혹스러웠다.

로컬에서는 N = 5000일 때도 빠르게 답이 나온다.

문제의 시간 제한이 1.5초이고 로컬에서는 대략 0.4초가 소요된다.

조금 어이가 없었지만 최적화를 해보기로 하였다.

 

d(i, j)의 발생 빈도는 모두 N으로 동일하다는 것을 파악하였다.

덕분에 불필요한 2중 for 문을 제거할 수 있었다.

01:16 TLE

pragma 붙여서 다시 시도하였다.

01:19 TLE

 

어이가 없었지만 최적화만 성공하면 AC를 받을 수 있다는 희망이 있었다.

매우 미미한 최적화를 시도하였다.

01:29 TLE

 

TLE의 원인을 찾지 못하고 있었다.

O(N^2)이 TLE를 받는다는 것이 이해가 되지 않았다.

또한 로컬에서는 잘만 돌아가지 않는가.

 

잘 생각해보니 O(N^2) 코드가 아니었다.

nCr을 구할 때 페르마의 소정리를 이용하고 있었기 때문이다.

이때 시간 복잡도는 O(log P)이므로 전체 시간 복잡도는 O(N^2 log P)였다.

 

dp를 이용하면 각각의 nCr을 상수 시간에 구할 수 있다.

따라서 전체 시간 복잡도를 O(N^2)으로 줄일 수 있다.

01:40 AC

 

여담으로 O(N)에 해결할 수도 있다고 한다.

 

E - Doremy's Number Line (not solved)

정렬하여 풀 수 있는 문제 같았다.

그리디한 풀이를 여럿 시도해보았으나 모두 실패하였다.

 

에디토리얼은 무슨 말인지 잘 모르겠고 에디토리얼 댓글에서 이해할 만한 풀이를 찾을 수 있었다.

if K <= A1 then

    ans = YES

elif K > A1 + B1 then

    ans = NO

이외의 경우에는 (K - B1)의 색칠 가능 여부에 따라 답이 결정된다.

 

우선 배열 A와 B를 A + B가 큰 순으로 정렬하자.

우리의 목표(goal)는 (K - B1)을 색칠하는 것이다.

다음과 같이 case work를 할 수 있다.

 

if Ai + Bi < goal then

    이 경우 goal을 색칠할 수 있는 방법이 존재하지 않는다.

    따라서 답은 NO이다.

elif Ai >= goal then

    이 경우 바로 goal을 색칠하면 된다.

    따라서 답은 YES이다.

elif Ai + Bi >= goal && Aj + Bj >= goal then

    이 경우 max(Ai, Aj)를 색칠하고 곧바로 goal을 색칠할 수 있다.

    따라서 답은 YES이다.

else

    이외의 경우에는 (goal - Bi)의 색칠 가능 여부에 따라 답이 결정된다.

    따라서 goal을 Bi만큼 낮추고 case work를 계속하여 진행하면 된다.

 

F - Doremy's Experimental Tree (not solved)

정점 u와 v 사이에 간선이 존재한다고 가정하자.

해당 간선의 가중치 w(u, v)는 다음과 같이 구할 수 있다.

w(u, v) = (f(u, u) + f(v, v) - 2 * f(u, v)) / N

유도 과정은 생략한다.

 

원본 트리는 다음과 같이 구할 수 있다.

모든 정점 쌍 (u, v)에 대하여 u와 v를 연결하는 가중치가 f(u, v)인 간선이 존재한다고 가정하자.

해당 간선들로 Maximum Spanning Tree를 구성하면 원본 트리와 동일한 구조가 된다.

이때 원본 트리에서의 가중치는 f(u, v)가 아닌 w(u, v)가 된다.

 

에디토리얼에는 단순히 증명이 가능하다고만 나와 있다.

대략적으로 증명을 시도해보자.

MST는 kruskal로 구한다고 가정한다.

 

현재 유망한 간선 중 가중치가 가장 큰 간선 e가 정점 u와 v를 연결하는 간선이라고 하자.

이때 원본 트리에서 정점 u와 v 사이에는 반드시 간선이 존재해야 한다.

간선이 존재하지 않는다면 원본 트리의 정점 u와 v 사이에는 최소 하나의 정점이 존재하게 된다.

이 정점들 중 하나를 x라고 하면 다음 식이 성립한다.

f(u, x), f(x, v) > f(u, v)

이는 e가 유망한 간선이라는 가정과 모순이다.

 

현재 유망한 간선 중 가중치가 가장 큰 간선의 집합을 E라고 하자.

이때 E에서 간선을 선택하는 순서와 무관하게 원본 트리의 구조는 항상 동일하다.

원본 트리의 구조가 달라지려면 E에 속하는 모든 간선을 추가하였을 때 사이클이 발생해야 한다.

E에 속하는 간선 e가 정점 u와 v를 연결하는 간선이라고 하자.

그리고 E에서 e를 제외한 일부 간선을 추가하였을 때 u와 v를 연결하는 단순 경로가 존재한다고 하자.

그렇다면 E에 속하는 간선 중 최소한 하나는 정점 u와 v를 연결하는 단순 경로에 속하게 된다.

해당 간선이 연결하는 정점을 x와 y라고 하면 다음 식이 성립한다.

• 두 간선 모두 E에 속하므로 f(u, v) = f(x, y)
• u와 v를 연결하는 단순 경로가 x와 y를 연결하는 단순 경로를 포함하므로 f(u, v) < f(x, y)

두 식이 서로 모순이므로 위와 같은 상황은 발생하지 않는다.

 

나 혼자 증명한 것이라서 증명이 틀렸을 수도 있다.

증명이 틀렸다면 제보 부탁드립니다.

 

G1 - Doremy's Perfect DS Class (Easy Version) (not solved)

Pass

 

G2 - Doremy's Perfect DS Class (Medium Version) (not solved)

Pass

 

G3 - Doremy's Perfect DS Class (Hard Version) (not solved)

Pass

 

H - Doremy's Paint 2 (not solved)

Pass

 

끝

끝