2023 ICPC Sinchon Summer Algorithm Camp Contest - Open Contest

2023 ICPC Sinchon Summer Algorithm Camp Contest - Open Contest

서론

오랜만에 백준 대회에 참가하였다.

 

B - Potato

정렬

00:02 AC

 

A - Toe Jumps

격자판을 돌릴지 case work를 할지 고민하다가 case work로 결정하였다.

격자판을 돌리면 구현이 많아지고 case work를 하면 무려 12개를 처리해야 한다.

뭔가 굉장히 애매한 문제가 되었다.

00:10 AC

 

C - 피보나치 사각형

그림의 가로 길이가 세로 길이보다 더 길거나 동일하다고 가정하자.

n번째 그림의 가로 길이와 세로 길이는 각각 F[n + 1]과 F[n]이다.

n번째 그림 내부에 (n - 1)번째 그림 두 개가 들어 있는데 n번째 그림과 방향이 반대이다.

n번째 그림의 가로 길이 F[n + 1] 중 왼쪽 F[n - 1]과 오른쪽 F[n - 1]은 (n - 1)번째 그림이 차지하고 있다.

 

현재 그림이 n번째 그림이고 좌표가 (x, y)일 때 다음과 같이 재귀적으로 답을 구할 수 있다.

• x가 F[n - 1] 이상 (F[n + 1] - F[n - 1]) 미만이라면 좌표 (x, y)는 n번째 피보나치 사각형에 속한다.
• 그렇지 않다면 좌표 (x, y)는 (n - 1)번째 그림에 속한다.
• 좌표를 적절히 변형한 후 (n - 1)번째 피보나치 사각형에 속하는지 검사한다.

00:27 AC

 

I - W키가 빠진 성원이

bfs

00:31 AC

 

D - 좋은 팀이란?

N이 매우 크지만 가능한 (실력 값, 일주) 쌍의 개수는 5 * 60 = 300개이므로 O(N^3) 풀이가 가능하다.

00:42 AC

 

E - Spell Cards

정해는 dp라는데 그리디 풀이가 보여서 그리디로 풀었다.

max(A[i - 1], A[i])의 값이 최소가 되는 i를 찾고 min(A[i - 1], A[i])를 제거하는 작업을 반복하면 된다.

00:49 AC

 

H - 슥~빡! 빡~슥!

부동 소수점 연산이라는 함정만 조심하면 쉬운 구현 문제가 된다.

01:04 AC

 

F - 납이야 나비야

다음과 같은 배열 A, B, C, D를 정의하자.

A[i][j] = 정점 i와 정점 j가 연결되어 있으면 true, 그렇지 않으면 false

B[i] = 정점 i를 포함하는 길이 3 사이클의 개수

C[i][j] = 정점 i와 정점 j를 포함하는 길이 3 사이클의 개수

D[i] = 정점 i의 차수

 

정점 i를 중심 정점(a~g에서 c)이라고 하자.

길이 3 사이클 2개를 선택하는 경우의 수는 (B[i] * (B[i] - 1) / 2)인데 간선이 중복되는 경우는 세면 안 된다.

모든 정점 j에 대하여 (C[i][j] * (C[i][j] - 1) / 2)를 빼주면 간선 중복 없이 길이 3 사이클을 선택하는 경우의 수를 구할 수 있다.

여기에 ((D[i] - 4) * (D[i] - 5) / 2)를 곱하면 정점 i를 중심 정점으로 하는 나비의 개수를 구할 수 있다.

01:22 AC

 

M - 편광판

빛을 가로막는 편광판을 set으로 관리하면 Segment Tree 없이 풀이할 수 있다.

01:35 AC

 

J - Minimax Tree

tree dp

01:46 AC

 

L - 피보나치 서로소

gcd(F[i], F[j]) = F[gcd(i, j)]가 성립하므로 Euler's phi function으로 개수를 셀 수 있다.

02:11 AC

 

K - 도로 위의 표지판

mst

진작에 짰는데 예제가 나오지 않아서 던져두었다.

다시 보니 변수명을 잘못 썼길래 바로 고쳐서 제출하였다.

02:16 AC

 

내 풀이는 dijkstra 비슷한 풀이였는데 에디토리얼을 보니 mst 문제라고 한다.

내 코드를 다시 보니 prim mst 코드와 매우 흡사하였다.

prim mst는 사용할 일이 없어서 너무 오래 잊고 살았다.

당연히 kruskal mst로도 풀리는 문제였는데 대회 중에는 생각나지 않았다.

 

G - Equilibrium Points

수학 및 물리 지식이 부족해서 계속 헛발질을 하였다.

02:52 TLE

02:54 TLE

03:11 WA

 

두 전하가 매우 가까워지면 전기력은 무한으로 수렴한다.

따라서 인접한 두 점전하 사이에 반드시 답이 존재하는데 좌표의 크기가 최소인 곳을 구하여야 한다.

첫 번째 점전하와 두 번째 점전하 사이에서 이분 탐색을 하면 된다.

 

03:18 WA

이분 탐색 횟수를 30으로 잡았는데 오차 범위 내에서 답을 구하기에는 조금 부족하였던 것 같다.

이분 탐색 횟수를 100으로 늘리고 double 타입을 long double 타입으로 변경하였다.

03:26 AC

업솔빙하면서 실험해보니 long double 타입은 굳이 필요하지 않았다.

 

N - 나비야 나비야 (not solved)

답은 2 * (볼록 사각형의 개수)가 된다.

naive하게 세면 O(N^4)이므로 더 빠른 방법이 필요하다.

 

임의의 사각형을 이루는 4개의 점으로 6개의 직선을 그려보자.

이때 각 직선에 속하지 않는 2개의 점이 어떤 영역에 속하는지 관찰해보자.

볼록 사각형인 경우 4번은 동일한 영역에 속하고 나머지 2번은 서로 다른 영역에 속하게 된다.

오목 사각형인 경우 3번은 동일한 영역에 속하고 나머지 3번은 서로 다른 영역에 속하게 된다.

 

O(N^2)개의 직선을 긋고 nCr(동일한 영역에 속하는 점의 개수, 2)를 계산하자.

그리고 이들의 합을 K라고 하자.

이제 다음과 같은 연립 방정식을 풀면 된다.

X = 볼록 사각형의 개수, Y = 오목 사각형의 개수

X + Y = nCr(N, 4)

4X + 3Y = K

 

K를 naive하게 계산하면 O(N^3)이므로 더 빠른 방법이 필요하다.

각 점을 기준으로 각도 정렬을 하고 two pointer를 이용하면 O(N^2 log N)에 문제를 해결할 수 있다.

 

끝

끝