SNUPC 2018

https://www.acmicpc.net/category/683

 

5시간 잡고 풀기에는 매우 빡셌다. (A, C, D, E, I, L)

B, K를 실패한게 아무래도 컸다.

H는 기하인데 솔브 수도 적어서 시도하지 않았다.

F, G, J는 스코어보드에서 거의 풀려 있지 않아서 읽어보지도 않았다. 

자력솔은 (G, H, K)

자력 실패는 (B, F, J)

내 생각에 F, J는 자력불가능하다.

 

A. 달빛 여우 (#16118, G1)

 

다익스트라를 하면, 여우, 늑대에 대한 최단 거리를 알 수 있다.

 

B. Cherrypick (#16119, P2)

 

벌써 난관에 봉착했다.

아무튼 포인트는 체리의 최대 당도가 1000 이하라는 점이다.

즉, 최대 변의 길이가 32 미만이라는 뜻이다.

따라서 각 점에 대해서 (1 * 1), (3 * 3), ... (61 * 61) 내의 최대 체리 당도만 구하면 된다.

c[k][i][j] : (2k - 1) * (2k - 1) 크기의 정사각형에 대해서 체리의 최대 당도

-> 그러면 c[k][i][j] = Max(c[k - 1][i'][j']) (단, abs(i - i') <= 1, abs(j - j') <= 1)

이를 반복하면 O(N * N * sqrt(N))에 할 수 있다.

 

C. PPAP (#16120, G4)

 

앞에서부터 쌓아나간다고 하면 편하다.

A를 보는 순간

1) 앞에 P가 2개 이상 존재하는지 확인

2) 직후에 P가 존재하는지 확인

3) A와 함께 양 옆의 P를 제거

하는 작업을 하여, 맨 마지막에 P 혼자 남는지 확인하면 된다.

 

D. 사무실 이전 (#16121, D5)

 

그냥 0번 점을 중심으로 dfs를 해서 나오는 거리를 dist라고 하자.

그렇다면 i 지점에 사무실이 존재하고, j 지점에 직원이 살고, 그 둘의 LCA를 k라고 한다면

모든 i에 대해서 Sum( (dist[i] + dist[j] - dist[k] * 2)^2) for all j)를 구해주면 된다. 

위의 식을 정리해보면 적당한 i, j, k에 대한 식이 나온다.

이 식을 잘 관찰해보면, a * dist[i] + b 꼴로 나타낼 수 있다.

a, b를 잘 관리하면서 DFS를 돌리면 모든 점 i에 대해서 원하는 값을 구할 수 있다.

 

센트로이드 분할 풀이에 의해 D5가 붙은 것 같다.

 

E. Unary (#16122, P4)

 

--, ~~ : 그냥 사라짐

-~ : x + 1

~- : x - 1

따라서 (--, ~~, -~, ~-)를 차례대로 잘 이어서 M을 만드는 방법을 구하면 된다.

N이 짝수라면, 단순히 N / 2짜리 수열을 만드는 과정이라고 여기면 된다.

이때 -~의 사용 횟수를 i라고 둔다면, ~- 의 사용횟수 j와, --, ~~의 사용횟수 k가 자동결정된다.

그러면 총 경우의 수는 (N / 2)! / i! / j! / k! * 2^k 의 총합이다.

 

만일 N이 홀수라면, 맨 마지막에 붙는게 -라면 -M, ~라면 - M - 1을 만드는 모든 경우의 수를 구해주면 된다.

따라서 O(N)에 모든 가짓수를 구할 수 있다.

 

F. 피타고라스 쌍 (#16123, D2)

 

관찰

1) m, n의 기우성이 같다면, a, b, c가 모두 짝수이다 -> m, n은 기우성이 다르다

2) a^2 + b^2 = c^2 -> a, b가 공통 소인수 p를 가진다면, c도 p의 배수이므로 a와 b는 서로소

-> (a, b) = 1을 통해 (a, m) = 1임을 알 수 있고, 따라서 m, n은 서로소이다.

-> 추가적인 관계확인을 통해서 m, n만 서로소이면 gcd(a, b, c) = 1이다.

따라서 구해야 하는 값은 sum(모든 i에 대해 i와 기우성이 다르고 서로소인 숫자의 개수)

아주 잠시 sum(phi(i))를 했는데 이거조차 모르겠다.

솔직히 말해서 오일러 파이함수와 관련된 합 공식을 하나밖에 모르는데 관련없어 보이기에 답지를 깠다.

 

친절하게도 답지에 sum(phi(i))도 있었다.

sum(phi(i)) 대신에 (n, m)이 서로소인 쌍의 개수를 구해도 대충 비슷하다.

따라서 (n, m)의 공통 소인수에 대해서 포함과 배제를 하면 

근데 이건 최소 O(L)이라서 불가능하다

 

그래서 i가 적당히 square보다 커지면 [L / i]가 square보다 작아진다는 점을 이용하여 sqrt(L) 수준으로 식을 내렸다.

다만, 이제는 M함수의 값을 구해야 한다.

정수론 공부를 하러가자...총총

 

G. 나는 행복합니다 (#16124, D3)

 

자료구조 문제에 익숙한 2023년 현재 기준으로는 딱 보면 Segtree임을 알 수 있다.

다음과 같은 정보를 지닌 구조체 Info를 정의하자

1. sum[10] : sum[i] = (숫자 i의 개수. 이때 "22"와 같은 경우에는 2가 10 + 1개, 즉 11개 있는 것으로 취급한다.)

2. to[10] : to[i] = (숫자 i가, 실제로 반영될때 어떤 값으로 반영되는지를 의미. 아직 sum에는 영향을 끼치지 않은 상태)

3. cnt : (총 숫자의 개수. 이때 "22"와 같은 경우에는 2가 1 + 1개, 즉 2개 있는 것으로 취급한다.)

 

그렇다면 a + b = c를 정의할 수 있다.

1. c.sum[a.to[i]] += a.sum[i] * (10 ^ b.cnt) 

2. c.sum[b.to[i]] += b.sum[i] 

 

Lazy propagation은 c.to라는 규칙이 a.to와 b.to로 내려가는 것을 의미한다.

따라서 merge_rule이라는 함수를 만들면 된다.

-> a.to[i] = c.to[a.to[i]]의 작업을 해주면 a.to에 c.to가 덧씌워진 형태가 된다.

-> 이때 굳이 a.sum을 건드려줄 필요는 없다.

 

이제 일반적인 lazy seg를 하듯이 prop을 시켜주면서 내려가면서 각각의 쿼리를 가해주면 된다.

from -> to는 단순히 a.to[i] == from인 애들을 a.to[i] = to를 해주면 되고,

값을 구하는 것은 보통 lazy seg처럼 nums[node]나 query(node * 2) + query(node * 2 + 1)을 return하면 된다.

 

H. 영점사격 (#16125, P2)

 

우선 편의를 위해서 (x1, y1), (x2, y2)의 y좌표가 동일해지도록 판을 회전시키자.

y좌표가 똑같아 졌다면, 이제 (x1, y1), (x2, y2)의 수직이등분선이 단순하게 x = (x1 + x2) / 2이다.

당연하게도 x < -r 이거나 x > r이라면 외심이 절대 원 내로 들어올 수 없으므로 답이 0이 된다.

그러면 이 직선과 반지름 R인 원과의 교점을 (x, hi), (x, lo)로 잡을 수 있다. (단, hi > lo)

이제 두 점에 대해서 만족하는 세 번째 꼭짓점의 위치는 (x, hi)를 중심으로 (x1, y1)을 지나는 원이다.

답은 (x, hi), (x, lo)를 중심으로 하는 두 원의 XOR이다.

나는 이걸 OR로 착각해서 오래동안 다시 고민하게 되었다.

원주각이 둔각인 상황을 생각해서 적당히 처리하면 된다.

 

I. 동아리방 확장 (#16126, P1)

 

우선 벽이 2개 미만인 격자칸은 존재하지 않는다.

그 격자칸에 붙는 다른 칸들만으로 벌써 4칸 이상의 방이 생성되기 때문이다.

비슷한 이유로 2개인 칸은 서로 하나의 방에 존재할 수 없다.

 

아무튼 그러면 2는 주변 2개의 칸과, 3은 주변 1개의 칸과 연결되는 격자칸이라고 생각할 수 있다.

이때 우리는 모든 방을 홀수칸과 짝수칸으로 나누어 이분그래프를 형성할 수 있다.

각 격자칸에 대해서 자신 주변의 4개의 칸과 연결된 이분그래프를 형성할 수 있다. (단, 2 - 2는 연결하지 않는다)

그러면 단순히 플로우를 흘려서 최대 매칭이 가능하다면 HAPPY, 불가능하면 HOMELESS

 

J. 미생물 키우기 (#16127, D2)

 

x >= 1이라는 점 때문에 마지막에는 결국 모든 미생물이 있음을 알 수 있다.

따라서 2번째 미생물 부터는 그냥 최대한 싼 방식을 통해서 마련하면 된다.

태그를 까보니 "유향 최소 신장 트리"라는 것을 목격했다. (Directed MST)

이걸 그대로 사용하면 AC를 받을 수 있다.

 

K. 스눕시티 (#16128, P1)

 

매우 멀리 떨어진, 즉 대각선으로 양 끝에 있는 두 점은 그냥 맨해튼 거리임을 알 수 있다.

또한 멀리 떨어진 두 점을 향해 갈 때는 반드시 중간점을 지나야 함을 알 수 있다.

 

solve(x, y)를 점 x에서 점 y로 가는 최단거리라고 하자.

만일 x, y가 현재 보드에서 대각선 양 끝에 있다고 할 경우 그대로 맨해튼 거리를 리턴한다.

만일 x, y가 현재 보드에서 같은 사분면에 존재하면  1/4로 보드를 쪼개버린다.

만일 x, y가 현재 보드에서 다른 사분면에 존재한다면, 반드시 중앙의 4개의 점들 중 하나를 통과하여야 한다.

-> 즉 solve(x, 중앙점 중 1) + solve(y, 중앙점 중 1)로 쪼개면 된다.

 

이때 얼핏 생각하면 매번 2개씩 쪼개져 최악의 경우 2 ^ 40개의 solve가 굴러갈 것이라고 생각할 수 있다.

하지만 쪼개지면 한쪽 점이 중앙점으로 설정되어, 다음 solve에서는 끝점이 된다.

즉, 이것이 또 쪼개지게 되면, 두 쿼리 중 하나는 (끝점 1, 끝점 2)가 되어 대각선 양 끝에 놓여 적당히 개수가 적게 유지된다.

 

L. 뚜루루 뚜루 (#16129, P1)

 

cnt[i][j] = (i, j)에서 첫 '뚜'가 나오는 '뚜루루뚜루'의 개수

대충 생각해보면, 적당히 제일 가장자리에서 먼 벽들의 경우에는 대개 비슷한 개수를 가질 거라는 생각을 할 수 있다.

즉, 대충 cnt[i][j] = cnt[i + 5x][j + 5y]라는 직관을 가질 수 있다.

 

문제에서는 (R, C)에 대해 구해야 하지만 조금 더 작은 보드에서 모든 cnt가 겹치도록 보드를 설정할 수 있다.

r = min(R, R % 5 + 15), c = min(C, C % 5 + 15)로 만들면 된다.

따라서 우리가 만든 새로운 작은 보드에서, 각 칸과 대응되는 칸의 수를 구하고, new_cnt[i][j] * (대응칸 수)를 더하면 된다.

이때 대응되는 칸의 수는 O(1)에 구할 수 있으므로, R, C가 사실 어떤 값이여도 크게 상관 없다.

 

O(1)으로 구할 수 있겠지만, 귀찮아서 O(N)으로 구했다.

단순하게 R -> r, C -> c로 바꾼 만큼 X -> x, Y -> y로 따로따로 변환시킨다고 생각하면 된다.

모든 0 ~ R - 1까지의 X값이 각 0 ~ r - 1까지의 x값에 몇 번 관여하는지 확인해주면 된다.

( (i, j)와 대응되는 칸의 수 ) = (i와 대응되는 X의 개수) * (j와 대응되는 Y의 개수)가 된다.