2020 숭고한 연합 알고리즘 캠프 후기- Contest

2020 숭고한 연합 알고리즘 캠프 후기를 씁니다.
Contest 와 Maraton을 분리해서 작성합니다. Maraton은 안 쓸수도..
ALPS에서 운영진을 맡고 있지만 숭고한은 참가자로 나갔습니다.
이유는 이미 출제진이 충분히 많았고 ALPS에서 문제제작 스터디를 진행하고 있었고 시험기간이 겹치는 상황이었고 등등 여러가지가 있습니다.
결과적으로 1등을 해서 40만원을 받게 됐습니다.
사실 저보다 잘하는 사람들이 꽤 많이 나와서 대상은 바라지도 않았고 최우수상이라도 받을 수 있을까 걱정했는데 결과가 좋아서 기뻤습니다.
문제는 Advanced(Div.1) 기준 A부터 I까지 9문제이고 저는 A,B,C,D,F,G를 해결했습니다.
작년 숭고한은 Educational하고 쉬운 문제들로 구성되었는데 이번에는 난이도가 대폭 상승했습니다.
문제와 해설는 여기서볼 수 있습니다.
해결한 순서대로 문제별 후기를 적겠습니다. 풀이는 공식풀이가 있으니 자세히 적진 않겠습니다.

B. 제곱 가중치 - 00:13(+0)

DP+수학 문제고 제가 퍼솔했습니다.
호불호가 갈릴 수 있을 것 같지만 저는 재미있었습니다.
A를 보다가 해석이 안돼서 B를 먼저 봤는데 문제가 간단해서 B를 먼저 시도했습니다.
풀이는 그냥 손으로 써보면서 규칙성을 찾아서 점화식을 세웠습니다.
다만 수학을 잘하는 사람에게 많이 유리하고 trivial하게 느껴질 수 있을 것 같습니다.

C. 강남 건물주 - 00:30(+1)

DP+세그먼트 트리입니다.
세그먼트 트리는 부차적인 것 같습니다.
처음에 문제를 잘못읽어서 한번 틀렸습니다.

D. 최소 대역폭 보장 - 00:45(+1)

윾파+오프라인 쿼리 문제입니다.
웰노운 사골이라 딱히 언급할 건 없는 것 같습니다.

A. 나무를 심어 볼까요? - 00:62(+0)

시뮬레이션 문제인데 해석이 매우 힘들었습니다.
저는 스택을 이용해서 풀었고 코드는 짧게 나왔습니다.
A번 문제에서 말리지 않는 것이 이 대회의 포인트 중 하나인 것 같습니다.
평소 코포에서 문제가 안풀리면 건너뛰는 연습을 많이 해서 다행인 것 같습니다.
지문의 퀄리티는 별개로 괜찮은 스택 문제인 것 같습니다.
이 문제가 Intermediate에서 C번이었는데 참가자들에게 너무 힘들지 않을까 걱정됐습니다.

 

이 시점에서 4등 정도였고 E,F,G 중 풀린 문제가 없었습니다.
패널티는 잘 관리된 상황은 아니었습니다.
E를 보았는데 아무 생각이 안 들었고 F와 G를 읽은 뒤 G의 풀이를 거의 가닥을 잡았습니다.
하지만 G의 구현이 너무 빡세보였고 2시간 시점까지는 F를 고민해보기로 했습니다. 결과적으로는 나쁘지 않은 선택이었습니다.

F. 숭고한 아이스크림 - 02:14(+1)

저만 푼 문제입니다.
$i$번째로 먹은 아이스크림을 $a_i$라고 합시다.
$m$개의 아이스크림을 먹는다고 할 때 아이스크림 맛의 합은 $\sum_{i=1}^m D_{a_i}-F\cdot (m-i)\cdot C_{a_i}$ 입니다.
따라서 $i$번째로 어떤 아이스크림을 먹을지 선택할 때 다른 번째에 어떤 아이스크림을 먹었는지에 영향을 받지 않습니다.
따라서 $i$번째에 어떤 아이스크림을 먹을 지를 독립적으로 선택할 수 있고 이것은 CHT로 계산할 수 있습니다. 저는 팀노트에 있는 리차오 트리를 열심히 타이핑 했습니다.
값이 음수가 나올수 있는데 그 경우는 아이스크림을 먹지 않으면 됩니다.
굉장히 좋은 문제인 것 같습니다.

 

F를 풀고 나니 2등이었고 G가 많이 풀려있었습니다.
1등을 하기 위해서는 최소 한문제를 더 풀어야 하는 상황이었습니다.

G. 수열 복원 - 03:26(+5)

그래프에서 두 인접한 정점의 가중치 값의 합이 주어질 때 전체 정점의 가중치를 알아내는 문제입니다.
그래프에서 각 컴포넌트마다 홀수 사이클을 찾으면 모든 정점의 가중치를 알아낼 수 있습니다.
짝수 사이클은 항등식이 나오기 때문에 쓸모가 없습니다. 엄밀한 증명은 선형대수를 이용한다고 합니다.
아이디어는 어렵지 않은 것 같고 구현은 썩 즐겁지 않지만 그렇게 복잡하진 않았습니다.
그런데 두 번은 다른 파일을 제출(...)해서 RE 두 번, void로 선언해야 할 함수를 int로 선언해서 RE 두 번,integer overflow 때문에 WA 한번을 받아 패널티가 많이 쌓여있었습니다. 그래서 대회가 끝날때까지 1등을 뺏길까봐 조마조마했습니다.

E. 동굴의 입구를 열어라!

저를 포함해 아무도 못 푼 문제입니다.
이 문제도 상당히 신선하다고 느꼈는데 남은 시간이 너무 적어서 대회중에는 못풀었습니다.
두 가지 아이디어가 필요한데 저는 둘 중 하나를 캐치했다고 출제자님이 말씀해주셨습니다.
첫 번째는 $i$번째 돌은 $A_{i+1}$보다 적게 사용해야 한다는 것입니다. $A_2\cdot A_3\cdot ... A_{n-1} \leq 3\cdot 10^7$ 이기 때문에 이 특성을 이용해서 백트래킹을 돌릴 수 있습니다.
대회 중에 이 아이디어는 생각해 냈지만 $A_n$은 저 식에 포함되지 않기 때문에 이것만으로는 풀 수 없었습니다.
두 번째 아이디어는 백트래킹을 $n-1$까지만 돌리고 $A_{n-1}\cdot x + A_n\cdot y = r$ 형태의 디오판토스 방정식을 푸는 것입니다.
이 방정식은 확장 유클리드 알고리즘을 이용해 전처리를 해놓으면 풀 수 있습니다. 유클리드 알고리즘은 로그복잡도이지만 시간제한이 빡빡하기 때문에 전처리를 하는 게 안전할 것 같습니다.
대회가 끝나고 업솔빙을 하는데 오버플로우 때문에 틀리는 걸 해결할 방법을 모르겠어서 그냥 __int128을 박아서 풀었습니다.

 

H는 뭔가 복잡한 DP문제인 것 같고 I는 cheetose님이 내셨는데 얼마 전에 같이 돌았던 요코하마 리저널의 문제와 유사하다고 합니다. 조만간 업솔해야지 하고 생각만 하고 있습니다.

 

좋은 대회를 열어주신 운영진과 출제진, 후원사분들께 감사합니다. 마라톤을 포함하여 상당히 괜찮다고 느낀 문제들이 꽤 있는데 저도 자극을 받고 그동안 쓰레기같은 문제만 만든 자신을 반성하게 됐습니다. 2학기에 있을 KCPC에는 최대한 높은 퀄리티의 문제를 내기 위해 노력해야겟습니다.