ICPC 2022 Asia Yokohama Regional

https://www.acmicpc.net/category/detail/3481

역량강화 셋이었는데 어떻게 다이아가 절반 이상;;

역량강화에서 A, B, D, G, E는 모든 팀이 풀었다.

J는 두 팀이, C, K, F는 한 팀씩이 풀었다.

J는 아마도 모든 팀이 풀이는 대충 생각해 냈는데, 기하라서 구현에 실패한 듯하다.

밑은 내가 생각하는 난이도 순이다.

 

A. Hasty Santa Claus

 

그리디하게 끝나는 시점이 제일 작은 애한테 잘 배정해주면 된다.

 

B. Interactive Number Guessing

 

만일 자리올림이 있으면 각 자리 숫자의 합이 감소할 것이다.

따라서 예를 들어 5를 주었을 때 각 자리의 합이 줄어들면 일의 자리가 5 이상, 아니라면 5 미만이란 뜻이다

따라서 맨 처음에 그냥 각자리의 합을 알기 위한 query 0을 물어보고

18개의 자리에 대해서 이분탐색을 해주면 각 자리마다 4개의 query가 필요하여 대충 총 73개로 답을 구할 수 있다.

 

G. Remodeling the Dungeon

 

일단은 초기 성 상태를 이용하여 Queen의 방이 root인 트리를 형성할 수 있다.

그렇다면, 우리가 하는 것은 트리의 한 간선을 끊고, 다른 간선을 새롭게 이어주는 것이다.

X-Y 간선을 끊고 Z-W 간선을 새롭게 이어줬다고 생각한다면 (단 X = par[Y])

Ans = (Z까지의 거리) + 1 + (W부터 exit까지의 거리)가 된다.

이때 반드시 Y의 subtree 내에 W와 exit이 존재하여야 하고, Z는 존재하지 않아야 한다.

따라서 W가 정해진다면, Y는 그냥 W와 exit의 LCA로 잡는 것이 손해가 없다.

그러면 각 W에 대해서, exit과의 LCA가 다른 주위의 Z에 대해서 답을 계산해주면 된다.

굳이 LCA를 구현할 필요까지는 없고, DFS를 한 번 잘 돌아두면 쉽게 구현할 수 있다.

 

D. Move One Coin

 

동전하나 이동시켜서 두 그림을 똑같이 만들어주면 된다.

일단 90도씩 돌리면서 4번 진행하는 것은 기본으로 두고, 현재 각도에서 똑같이 만들 수 있는지 보자.

우선 Souce pattern에서 제일 왼쪽 위의 동전 2개 중에서 한 개는 옮기지 않을 것이다.

마찬가지로 Target pattern의 제일 왼쪽 위 동전 2개 중에서 한 개는 옮겨서 생긴 동전이 아닐 것이다.

따라서 (Source의 좌상단 2개)와 (Target의 좌상단 2개) 중에 적어도 한 쌍은 무조건 매칭이 가능하다.

그러면 현재 두 개의 pattern이 몇 칸 밀려있는지 확인 가능하고 O(보드의 크기)로 동전 하나 옮겨서 매칭되는지 확인된다.

따라서 90도 돌리면서 생기는 4개의 그림에대해 4가지 쌍 모두를 확인해주면 답을 구할 수 있다.

 

E. Incredibly Cute Penguin Chicks

 

N^2 dp를 떠올리는 것은 그렇게 어렵지 않다.

[L, R]이 ICPC-ish한지는 prefix sum으로 O(1)에 판별할 수 있기에

dp[i] = sum(dp[j]) (단, [j + 1, i]는 ICPC-ish)라는 식을 세워주면 된다.

 

아무튼 이걸 로그로 내리는 방법은 여럿 있지만 본인은 다음의 방법으로 했으나, 그렇게 이쁘진 않다.

I > P = C인 경우만 고려하자.

만일 [j + 1, i]가 I > P = C이라면, (j까지의 P개수 - C개수) = (i까지의 P개수 - C개수)가 성립한다.

따라서 각각의 x에 대해서 우선 minus[(x까지의 P개수 - C개수)].push_back(x)를 해둔다.

이때 (i까지의 I개수 - P개수) > (j까지의 I개수 - P개수)가 성립해야하니, 이를 기준으로 minus를 모두 정렬해둔다.

(사실 미래에 segtree만 생각하면 정렬을 안해도 되는데, 좌표압축을 위해서 정렬했다.)

이후 dp[0], dp[1], ...을 차례로 계산해나가면 된다.

-> minus[i까지의 P개수 - C개수)]에서 i보다 앞에있는, i > j인 j들의 dp값을 합하면 된다.

 

J. Traveling Salesperson in an Island

 

업솔빙에서도 AC를 받는데 실패함.

가볍게 풀이를 설명하자면

1) 우선 각 점들 사이의 거리를 구하자.

이때 (i, j) 사이를 잇는 직선이 island 밖으로 나간다면, 그 거리를 1e18로 하여야 한다.

여기서 플로이드 와샬을 돌리면 모든 점들 사이의 거리를 구할 수 있다.

2) 이제 최소 cycle의 길이를 구하면 된다

 

1)은 사실상 직선이 polygon 밖으로 나가는지 판정하는 것과 같다. (나머지 부분들이 너무 쉽기에)

-> 끝점을 제외하고 우선은 island의 경계와 만난다면 그냥 나가버린다고 여기면 된다.

   -> 만일 내부에서 겹친다 하더라도, 이는 플로이드 와샬에서 저절로 해결된다.

   -> 예를 들어 A - B 직선 사이에 X - Y가 있다면, A - B를 1e18로 잡아도 A - X + X - Y + Y - B로 저절로 복구된다.

-> 그러면 이제 끝점을 제외하고 경계와 안 만나지만 밖에 있는 케이스들을 해결하면 된다.

    -> Sample 2에서 6번 꼭짓점과 8번 꼭짓점을 이은 선분 등이 그렇다.

    -> 이들은 중점을 잡아서 밖에 있는지 판단해주면 된다.

 

2)는 TSP같지만, 모든 port가 polygon의 변 위에 있음을 생각하면 직관적으로 생각할 수 있다.

-> polygon을 반시계방향으로 돌면서, 순서대로 나오는 port들을 이어주면 된다.

 

기하는 풀지 말자.

 

F. Make a Loop

 

Track은 다음과 같이 4종류로 나눌 수 있다.

(우상단으로), (우하단으로), (좌상단으로), (좌하단으로) 향하는 종류의 철도가 존재한다.

이때 다음과 같은 조건이 반드시 만족한다

1) 오른쪽으로 가는 만큼, 왼쪽으로 와야 한다

2) 위로 가는 만큼, 아래로 와야 한다

3) 부드럽게 이어져야하므로, 4 종류는 반드시 개수의 기우성이 같다.

    -> (오른쪽으로 가는 철도), (왼쪽으로 가는 철도), (위로가는 철도), (아래로 가는 철도)는 모두 짝수개이다.

따라서, 전체를 기우성이 같고 합도 같은 두 그룹으로 나누는 방법이 2가지 이상이면 된다.

-> 그렇다면 그 2가지를 이용하여 (좌, 우) (상, 하)를 나누어버릴 수 있기 때문이다.

 

K. New Year Festival

어떻게 잘 하면 된다는데... 흠

C. Secure the Top Secret

그래프를 잘 만들고 + Flow...?

 

H. Cake Decoration

 

우선은 그냥 a < b < c < d라고 가정해버린다면 세는 것이 조금 더 편할 것이다.

직접 모든 경우의 (a, b)를 세보고, 제한 시간이 10초라면, log 정도의 계산으로는 된다는 생각을 할 수 있다.

그러면 우선 a, b가 정해져 있다고 가정하자.

이때 x in {a, b, c, d}, y in {a, b, c, d}에 대해서 L <= x +y < R인 경우의 수를 모두 세고, 여기에 4배를 하면 답이 된다.

(x, y가 서로 바뀔 수 있고, x, y가 아닌 2개가 서로 바뀔 수 있어서 4배.)

 

1) L <= a + b < R, L <= a + c < R, L <= b + c < R

-> 우선 c < d를 이용해서 이분탐색을 돌리면 c의 범위를 구할 수 있다.

-> 그러면, 위의 부등식들은 c의 범위와 쉽게 합칠 수 있고, 새로운 c의 범위 내의 c의 개수만 구해주면 된다.

2) L <= a + d < R, L <= b + d < R  (편의를 위해 a만 설명)

-> 이번에는 단순하게 L <= a + d, a + d < R 두 가지에 대해서 각각 c에 대한 이분탐색을 하자.

-> 그러면 첫 번째 이분탐색에서 나온 R1과 두 번째 이분탐색에서 나온 L2에 대해 c의 범위는 [L2, R1]이 된다.

3) L <= c + d < R

-> 미분을 통해서 c < sqrt(X / i / j)에서는 c + d가 감소함을 알 수 있다.

-> 이때 c < d이기에 위의 조건은 당연히 만족한다.

-> 따라서 단순한 L <= c + d, c + d < R에 대한 이분탐색으로 c의 범위를 구할 수 있다.

 

결과적으로 모든 (a, b)에 대해 이분탐색을 7번씩 돌렸고, 이것은 시간내에 통과한다

이것보다 느린 풀이는 아마 없을테니, 로그 시간으로 c를 대충 찾기만 하면 무조건 통과될 것이다.

 

I. Quiz contest

 

이런 문제에서 modulo가 998244353이라면 FFT를 의심하게 된다...

FFT가 정해가 아니라면 일부러 1e9 + 7을 소수로 잡는 출제자들이 있기 때문이다.

아무튼 sum(a[i]) = m <= 2e5임에 착안하자.

 

기본적인 아이디어는 에디토리얼에서 따왔다.

이진트리 형태로 Divide and Conquer를 한다고 생각해보자.

1) 그러면 두 개의 그룹을 합치면서 각 시점에 대해 subtree에서 승자가 결정되는 경우의 수를 구한다

-> 이렇게 타고 올라가면, 모든 subtree에 대해서 모든 시점에서 승자가 결정되는 경우의 수를 구할 수 있다.

2) 위에서부터 이제 내려오면서 각각의 그룹이, 특정 시점에서 승리하는 경우의 수를 계산해준다

 

FFT로 된다는 것을 기억하면서 하면 어떻게 어떻게 잘 할 수 있다.

a[x] = (a번 그룹이 x번째 승리를 통해서 우승이 확정지어지는 경우의 수)

1) a 그룹과 b 그룹이 합쳐진다고 가정하자 (s = a + b)

-> s에서 (i + j)번째 판에서 a 그룹이 i번째로 승리하며 s에 대한 우승를 가져가는 케이스는 다음과 같다

-> s[i + j] += C(i + j - 1, i - 1) * C(asz + bsz - (i + j), asz - i) * a[i] * sum(b[x > j])

-> 이때 위의 combination들이 (i + j), i, j에 대해 이쁘게 잘 쪼개진다는 것을 이용해서 FFT가 가능하다.

 

대문자는 조금 다르게 A[x] = (a번 그룹이 실제로 x번째 승리르 통해서 우승을 한 경우의 수)라 하자.

2) s 그룹에서 a, b로 나누어준다고 생각하자.

-> 그러면 S[x]를 적당히 A, B에게로 나누어주어야 한다.

-> 아까 1)에서 각각의 a[i], b[i]가 얼만큼 s[i + j]에 기여하였는지를 확인해주면 된다.

-> A[i] += (S[i + j] / s[i + j]) * C(i + j - 1, i - 1) * C(asz + bsz - (i + j), asz - i) * a[i] * sum(b[x > j]) 이 된다.

-> 이것도 마찬가지로 이쁘게 잘 쪼개지므로 FFT를 통해서 A, B를 구할 수 있다.

 

이러면 각각의 leaf에는 개인이 우승하는 경우의 수가 나와있으니, 답을 구할 수 있다.