2020 ACM-ICPC Seoul Regional

Asia Regional - Seoul 2020

서론

실제로 참가하였던 대회이기도 하고 풀어볼 만한 문제도 많아 보여서 최대한 업솔빙하였다.

 

B - Commemorative Dice

단순 구현

 

C - Dessert Café

임의의 두 아파트 단지를 잇는 경로 사이에 존재하는 candidate site는 good place이다.

임의의 아파트 단지에서 dfs를 돌리면 모든 good place를 찾을 수 있다.

간선의 가중치는 필요하지 않다.

 

E - Imprecise Computer

각 round의 결과에 대하여 D[i]의 값은 다음과 같이 결정된다.

if (i - 1) vs i의 결과가 동일

    if i vs (i + 1)의 결과가 동일

        D[i] = 0

    else

        D[i] = 1

else

    if i vs (i + 1)의 결과가 동일

        D[i] = 1

    else

        D[i] = 0 or 2

 

여기서 알 수 있는 사실은 다음과 같다.

• (i - 1) vs i의 결과가 동일하다면 D[i]는 2 미만이다.
• 그렇지 않다면 D[i]는 3 미만이다.
• (i - 1) vs i의 결과와 D[i]의 값을 이용하여 i vs (i + 1)의 결과를 알 수 있다.

따라서 D[1]부터 D[N]까지 순차적으로 살펴보면 문제를 해결할 수 있다.

 

G - Mobile Robot

로봇을 차례대로 배치할 때 로봇의 최대 이동 거리를 최소화하는 문제이다.

i번 로봇을 좌표 (x + i * D)에 배치한다고 가정하자.

이때 i번 로봇이 이동하는 거리 B[i]는 다음과 같이 정의된다.

B[i] = x + i * D - A[i];

B[i]가 음수이면 왼쪽으로 이동한다는 것이다.

 

잘 생각해보면 max(B) = -min(B)를 만족시키는 x가 최적임을 알 수 있다.

이때 로봇의 최대 이동 거리는 max(B) = -min(B) = (max(B) - min(B)) / 2가 된다.

그런데 x와 무관하게 (max(B) - min(B)) / 2의 계산 결과는 항상 동일하다.

따라서 답은 임의의 x에 대하여 (max(B) - min(B)) / 2가 된다.

 

두 가지 주의 사항이 있다.

첫 번째는 로봇이 역순으로 배치될 수도 있다는 것이다.

따라서 위의 과정을 반대 방향으로 한 번 더 처리해주어야 한다.

두 번째는 부동 소수점 오차이다.

답은 항상 x / 2 꼴이므로 정수 자료형을 사용하되 소수점 아래 부분은 if 문으로 출력해주면 된다.

 

H - Needle

DO YOU KNOW FFT

 

J - Switches

각 i에 대하여 Gaussian Elimination을 수행하면 전체 시간 복잡도 O(N^4)에 문제를 해결할 수 있다.

하지만 제한이 크기 때문에 O(N^4)는 허용되지 않는다.

 

Gaussian Elimination으로 주어진 행렬의 역행렬을 구하면 O(N^3)에 문제를 해결할 수 있다.

역행렬이 존재한다면 답은 역행렬로부터 구할 수 있다.

그렇지 않다면 답은 -1이 된다.

선형대수학 지식이 부족하여 원리는 정확히 이해하지 못하였다.

 

A - Autonomous Vehicle

좌표 제한이 크기 때문에 나름 효율적으로 구현해야 한다.

모든 도로에 대하여 교차점을 구하고 이동 시에는 각 도로의 시작점과 끝점 그리고 교차점만을 고려하면 된다.

그런데 구현이 많이 더럽다.

집에서 음악 들으면서 평온한 상태에서 풀어도 1시간이 넘게 걸렸는데 대회 중에 풀 수 있을지가 의문이다.

 

I - Stock Analysis

세 가지 풀이를 소개한다.

모든 풀이는 구간 트리와 offline query를 동반한다.

 

첫 번째 풀이는 Merge Sort Tree의 아이디이를 이용한다.

query는 e의 오름차순으로 정렬한다.

Segment Tree의 각 노드는 담당 구간의 모든 누적 합을 set으로 관리하도록 한다.

각 query는 구간 [s, e]를 담당하는 모든 노드에 대하여 u에 대한 upper_bound를 구하여 처리할 수 있다.

이 풀이는 TLE를 받지만 간단한 아이디어로 접근할 수 있어서 설명하였다.

 

두 번째 풀이는 크기가 O(N^2)인 Segment Tree를 이용한다.

마찬가지로 query는 e의 오름차순으로 정렬한다.

Segment Tree는 각 누적 합 i에 대하여 S[j .. k] = i를 만족하는 j의 최댓값을 관리하는데 이를 A[i]라고 하자.

각 query는 i <= u이고 A[i] >= s를 만족하는 i의 최댓값을 구하여 처리할 수 있다.

값의 범위가 넓기 때문에 좌표 압축이 필요하다.

 

세 번째 풀이는 2D Fenwick Tree를 이용한다.

query는 u의 오름차순으로 정렬한다.

문제를 변형하면 직사각형 내의 최댓값을 구하는 문제가 된다.

하지만 일반적으로 Fenwick Tree는 최댓값 연산을 수행할 수 없다.

 

각 직사각형의 좌표에 주목해보자.

좌상단 꼭짓점의 좌표는 (s, s)이고 우하단 꼭짓점의 좌표는 (e, e)이다.

a > b일 때 좌표 (a, b)의 값은 0이므로 각 좌표를 (s, 1)과 (N, e)로 변형할 수 있다.

인덱스 [i, j]에 대한 업데이트를 인덱스 [N - i + 1, j]에 대한 업데이트로 바꾸어 수행해보자.

놀랍게도 최댓값 query를 수행할 수 있게 된다.

 

L - Two Buildings

식을 잘 정리하면 dnc opt가 가능함을 알 수 있다.

WF 문제인 14636번과 매우 유사하다.

 

D - Electric Vehicle

Pass

 

F - Ink Mix

Pass

 

K - Tiling Polyomino

Pass

 

끝

끝