abc339 - 블루를 가다

https://youtu.be/cof3wZFfDrY?si=RaH9QREx484eQ2cV

중등부 왜케 좋지

 

한국 2등 했어요

A - split('.')

 

B - toroidal 이 무슨 뜻인가 했는데 그냥 움직일때마다 mod H, mod W 해주면 되는 그림으로 그리기는 힘들 것 같은 무언가? 더라고요. 아무튼 구현 하면 됩니다.

 

C - 구간합을 쭉 구해준 후 min값을 찾고 총합에서 빼주면 됩니다.

 

D - 첫번째 플레이어의 위치와 두번째 플레이어 위치의 경우의 수는 $O(N^4)$개 이기에, 각 상태를 정점으로 두고 bfs를 돌려주면 됩니다.

 

E - $dp_i$ = i번째 수로 끝나는 가장 긴 smooth subsequence 라 하면, $dp_i$ = $\min_j$ $dp_j$ ($a_i - D \leq a_j \leq a_i + d$) + 1 다음과 같은 점화식이 성립합니다. 이는 그냥 구현하면 $O(N^2)$이고 세그먼트 트리를 이용하면 전이를 $O(\log N)$ 에 할 수 있습니다.

 

F - 각 수가 등장하는 횟수를 전처리해주고 $O(N^2)$개의 pair에 대해 두 수의 곱이 몇개 존재하는지 구해주면 풀 수 있을 것 같았지만, 범위가 너무 큽니다. 정해인지는 모르겠지만 저는 해싱 비슷하게 풀었습니다. 각 수를 어떤 소수에 대한 나머지를 취해주고, 두 수의 곱 또한 나머지를 취해주며 처음 언급한 알고리즘을 사용해 개수를 세어줍니다. 단 이때 소수를 적게 사용하면 틀릴 확률이 높기에, 소수를 10개 사용해 주었습니다.

 

G - 2차원 쿼리 문제이고 온라인으로 풀어야 합니다. 그냥 2차원 세그먼트 트리를 짜면 TLE를 맞을 것 같이 생겼습니다. 실제 2차원 세그의 상수가 엄청 크기도 하고요. PST를 활용한 풀이도 존재할 것 같으나, 제 풀이는 다음과 같습니다. 우선 머지소트트리를 가져옵니다. 트리의 각 노드에는 범위에 해당하는 수가 정렬된 상태로 저장되어있을텐데, 이들의 구간합 또한 구해줍니다. 이제 쿼리는 각 노드에서 이분탐색으로 $X$보다 작거나 같은 수의 인덱스를 찾아주고, 전처리한 구간합으로 답을 구해주면 됩니다. 시간복잡도는 $O(N \log N + Q \log^2 N)$ 입니다.

 

총평) 전체적으로 난이도가 쉬워서 제가 이득을 본 것 같습니다(?) 드디어 블루에 가게 되네요.. abc 올솔도 처음 해보고 기분이 좋습니다.