제9회 한양대학교 프로그래밍 경시대회 (HCPC) Open Contest - Advanced Division

제 9회 한양대학교 프로그래밍 경시대회 (HCPC) Open Contest - Advanced Division

B - 배수관 미스터리

Union-Find + offline query

00:08 AC

 

C - 나락도 락이다

dp

00:20 AC

 

F - 출제비 재분배

단순 구현

00:23 AC

 

G - 트리와 수열

트리 dp로 각 간선이 사용되는 횟수를 기록한 후 정렬하면 된다.

00:34 WA

정렬 과정에서 실수가 있었다.

00:47 AC

 

J - 선물의 재분배

+ 연산만 사용하여 풀이할 수 있다.

B 값이 가장 큰 부원에게 선물을 몰아준 후 적절히 재분배하면 된다.

01:19 AC

 

남은 문제는 5개였고 문제별 감상평은 다음과 같았다.

• A - 어려워 보인다. 푼 사람이 별로 없다.
• D - SCC로 풀릴 것 같다. 그런데 나는 SCC를 공부한 적이 없다.
• E - 어려워 보인다. 푼 사람이 별로 없다.
• H - 내가 풀 수 없는 더러운 기하 문제이다.
• I - FFT로 풀릴 것 같다. 그런데 나는 FFT를 공부한 적이 없다.

잠시 고민하다 내린 결론은 FFT와 SCC를 빠르게 학습한 후 I번과 D번을 처리하자는 것이었다.

다행히 성공하였다.

 

I - 트리의 팔

FFT만 잘 하면 되는데 나는 FFT를 모른다.

급하니까 일단 초록책에서 코드만 베껴 왔다.

 

01:48 WA

실수 오차 때문이라고 추정하고 long double 타입을 사용하였다.

01:55 WA

배열의 크기를 2^19으로 잡은 것이 문제였다.

N = 3e5는 2^19보다 작지만 다항식 곱셈 결과 2 * N = 6e5는 2^19보다 크다.

따라서 배열 크기를 2^20으로 잡아야 한다.

02:00 AC

 

사실 원래 틀렸어야 하는 코드가 맞았다.

AC 제출에서는 다시 double 타입을 사용하였다.

대회 종료 후 테스트해보니 일부 입력에서 실수 오차로 인하여 잘못된 답을 출력한다.

long double 타입을 사용하면 해결되는 것으로 보인다.

데이터 추가 요청을 올렸다.

 

CP4에서 FFT를 20 페이지에 걸쳐서 다루고 있는데 원리를 차근차근 잘 설명하고 있다.

수식 생략하고 간략하게 정리하자면 다음과 같다.

 

지구에서 두 다항식의 곱셈은 O(N^2)이 소요된다.

이세계에서는 O(N)에 수행할 수 있지만 지구와는 상이한 표기법을 사용한다.

지구 표기의 다항식을 이세계 표기로 변환하는 데 O(N log N)이 소요된다.

마찬가지로 이세계 표기의 다항식을 지구 표기로 변환하는 데 O(N log N)이 소요된다.

따라서 두 다항식의 곱셈을 이세계에 위임함으로써 O(N log N)에 해결할 수 있다.

자세한 변환 및 계산 과정은 우리 부서 담당이 아니다.

 

D - 즉흥 여행 (Hard)

사실 scc 문제가 맞다고 확신이 들지는 않았다.

그런데 인터넷을 뒤지다가 그래프를 scc로 분할한 후 위상 정렬하는 테크닉을 발견하였다.

이는 이 문제의 풀이와 정확히 일치한다.

 

급하게 scc를 공부하였다.

kosaraju 알고리즘과 tarjan 알고리즘이 있던데 이해가 간편한 kosaraju 알고리즘을 선택하였다.

지금 보니 tarjan 알고리즘도 그리 복잡하지는 않다.

02:48 AC

 

여담으로 scc를 발견한 순서가 곧 scc의 위상 정렬 순서가 된다고 한다.

 

A - NATO 음성 기호와 쿼리 (not solved)

다음과 같은 점화식을 생각할 수 있다.

dp[i][j] = j번 문자에 변환을 i번 적용하였을 때 문자열의 길이

하지만 최대 변환 횟수가 2e23이기 때문에 현실적으로 적용하기 어렵다.

관찰이 필요하다.

 

변환을 x번 적용하면 문자열의 길이는 4^x배 이상 증가한다.

변환을 30번 이상 적용하는 경우 문자열의 길이는 1e18보다 커진다.

이 상태에서 변환을 계속해서 적용하더라도 앞에서부터 1e18개의 문자는 변하지 않는다.

따라서 변환은 최대 30번만 고려하면 되므로 위의 점화식을 그대로 사용할 수 있다.

 

S의 길이가 최대 2e5이기 때문에 선형 탐색은 TLE를 받는다.

누적 합으로 관리하고 이분 탐색을 수행하면 된다.

하지만 변환이 적용될 때마다 누적 합의 업데이트가 필요하다.

다행히 변환은 최대 30번만 고려하면 되므로 이 부분도 문제가 되지는 않는다.

 

E - All Solve를 향해! (not solved)

Segment Tree로 풀이하였지만 정해는 이분 탐색이다.

출제자님 오피셜로 기존 정해는 Segment Tree였으나 굳이 필요 없어서 수정되었다고 한다.

에디토리얼만 봐서는 무슨 말인지 이해하기 어려웠다.

출제자님의 코드를 확인하고 나서야 이해할 수 있었다.

 

Segment Tree 풀이는 상당히 직관적이다.

그냥 문제 설명을 Segment Tree를 이용하여 그대로 시뮬레이션하면 된다.

Segment Tree 풀이에서는 날마다 어떤 문제를 풀 것인지를 결정한다.

이와 달리 이분 탐색 풀이에서는 각 문제를 어떤 날에 풀 것인지를 결정한다.

 

먼저 다음과 같은 배열을 관리하자.

A[i] = i번 날에 푼 문제 중 가장 어려운 문제의 난이도

B[i] = i번 날에 푼 문제 수

모든 문제를 순차적으로 푸는데 현재 문제가 풀릴 수 있는 날을 two pointer로 관리한다.

해당 pointer를 p와 q라고 하자.

 

p == q이거나 A[p .. q)가 현재 문제의 난이도보다 크거나 같다면 해당 문제는 다음 날에 풀어야 한다.

이 경우 q를 증가시켜주면 된다.

그렇지 않다면 A[p .. q) 내에서 이분 탐색을 하면 된다.

A[i]는 단조롭게 감소하므로 이분 탐색이 유효하다.

현재 문제의 난이도보다 작은 원소 중 가장 왼쪽에 있는 원소를 찾으면 된다.

 

한 페이지에 최대 K개의 문제만 보인다는 조건도 처리해주어야 한다.

B[p + 1 .. q)의 합이 K보다 크다면 p번 날에는 더 이상 문제를 풀 수가 없다.

이 경우 p를 증가시켜주면 된다.

 

H - 보물 찾기 (not solved)

기하 Pass

 

Advanced Division 문제는 여기서 끝이다.

Beginner Division 문제의 풀이를 일부 남긴다.

 

BB - 즉흥 여행 (Easy)

하나의 scc로 이루어져 있는지 확인하면 된다.

두 번의 dfs로 확인할 수도 있는데 그게 곧 scc 풀이이다.

 

BC - Wordle 찍기

G가 4개라면 나머지 하나는 B이어야 한다.

이 부분만 예외 처리해주면 된다.

정답 단어는 간단하게 ABCDE로 하고 판정 결과에 대해서는 적절히 출력해주면 된다.

 

BI - 로하의 농사

p가 작으므로 완전 탐색이 가능하다.

구부러진 파이프를 잘못 처리하면 TLE를 받는다.

잘못 처리하기도 쉽지 않다.

 

BJ - 한양 가왕

N개의 라운드가 진행되면 N명의 참가자의 위치는 고정되며 나머지 N명의 참가자는 계속해서 순환한다.

따라서 M > N인 경우 M = N + M % N으로 고려해도 된다.

M이 충분히 작아졌으므로 그대로 시뮬레이션 돌리면 된다.

 

끝

끝