UCPC 2023 본선 후기

시원하게 조졌다. (팀적으로도, 개인적으로도)

조진 이유는 여러가지가 있다.

 

사실 우리 팀에서의 나의 역할은 플상위 + 다하위를 푸는 것이라고 대충 생각하고 있었다.

이러한 경향은 지난 대회참가/연습에서도 사실 알아차릴 수 있다.

UCPC 예선 - 9솔 중에서 2솔, 티어는 각각 P1, D4

FunctionCup - 22점 중에서 8점, 만점(3점)을 받은 1문제는 D4

SWERC2020 연습 - 10솔 중에서 1솔, 티어는 P1

 

그래서 나는 기본적으로 초반 실골플 밀기는 팀원에게 맡기고, 보다 솔브수 늘리기에 치중된 스탠스를 가지고 있었다.

이러한 스탠스 덕에 UCPC 예선에서는 H 퍼솔과 D4의 해결로 동일 솔브수 대비 제일 좋은 패널티를 받을 수 있었다.

하지만 이번에는 I, J, K를 잡았지만, 풀지 못하였기 때문에 큰 문제가 생겼다. (0솔)

사실 나는 정올 등을 거치지 않았기 때문에 다이아 풀기보다는 플레 풀기에 치중된 사람이라고 생각한다.

저점 관리를 하려면 앞으로는 조금 더 실골플 밀기에서의 내 비중을 높여야 한다는게 내 생각이다.

물론 어쩌면 WF 진출이라는 고점을 노리고 싶은 상황에서는 기존의 전략이 좋을 수도 있다는 생각이 든다.

 

그리고 F에도 관여를 했는데, F가 2D seg를 구현하면 끝난다는 것을 깨닫고서는 준서한테 바로 넘겼다.

이 판단은 지금 다시 생각해봐도 틀리지 않았다고 생각한다.

다만, 그 때 바로 준서가 2D seg 구현을 하도록 했어야 한다고 생각한다.

아마도 준서가 그 때 H를 잡고 있었던 것 같은데, H 스타일의 문제를 준서한테 넘긴 것은 잘못된 것 같다.

나와 준서가 대충 H를 '적당히 그냥 하면 된다'로 결론내리고 준서에게 구현을 맡겼었다.

여기까지는 그렇다 치더라도, 준서가 한 번 구현이 꼬인 다음에는 문제를 뺏어와서 나도 관여했어야 한 것 같다.

 

문제들이 대충 거의 다 플레 이상이니 업솔빙을 슬슬 해본다.

문제의 순서는 대충 스코어보드 기준으로 풀어야 했는 문제의 순서.

 

L. 나무늘보

 

우선은 평소에 우리가 다루는데로, 전위와 후위 순회의 결과를 in[i], out[i]로 바꾸자.

그렇다면, a가 b의 parent이면 in[a] < in[b], out[a] > out[b]를 만족하여야 한다.

이진트리니까 b가 만약에 왼쪽 자식이면 in[a] + 1 = in[b]까지 성립한다.

만일 in[a] + 1 = in[b]인데, out[a] < out[b]라면 b는 자식이 될 수 없으므로, a의 parent의 오른쪽 자식이다.

-> 이것을 통해서 우리는 전위와 후위의 결과로 트리의 형태가 결정된다는 것을 알 수 있다.

-> 다만, 이때 한 노드의 자식이 1개 뿐이라면, 이것이 left일 수도, right일 수도 있으니 답이 2배가 된다.

-> 따라서 DFS(전위 따라가기)를 하면서 트리를 만드는데, 어떤 노드의 자식이 1개일 때마다 답을 2배시켜주면 된다.

 

G. K번째 스페이드 찾기

 

우선은 어떠한 경우에도 유진이가 제일 적은 동전을 지불하는 전략을 알아내야 풀 수 있다.

K = 1이라면, 유진이는 어쩔 수 없이 모든 카드에 대해서 스탑을 외쳐야 한다.

K = 2이라면, 유진이는 2장씩 스탑을 외치다가 스페이드가 처음 나온 순간, K = 1과 다를게 없으니 항상 스탑을 외친다.

이를 통해서 K = N일 때의 전략을 유추해낼 수 있고, 더 좋은 방법은 없다.

현재까지 나온 스페이드가 x장이라면 (N - x)장마다 스탑을 외쳐야 한다.

 

위의 전략을 직접 하는 것이 NlgN임을 대충 생각해보자.

스페이드가 없는 보드라면 당연하게도 NlgN이다.

스페이드가 하나 있는 보드라면, 그곳까지 도달하는데 XlgX, 그 이후에 (N - X)lg(N - X)라서 이거도 대충 NlgN

너무 직관적이고 부정확한 생각이지만, 스페이드마다 보드를 쪼개서, 그거마다 XlgX라고 생각하면 대충 NlgN일 것 같다.

 

C. 황혼

 

규칙을 지키면서 1번 도시에서 모든 도시까지의 최단시간을 계산해야 한다.

어떤 정보가 p[1], ... p[s]로 주어진다면 p[1] -> p[s]를 모두 사용하는 경로를 막아야 한다.

p[1] -> p[x] (단, x < s)로의 간선을 모두 새롭게 만들어주고, p[1] -> p[2]는 삭제하자.

이때 새롭게 만든 간선 직후에는 이 정보에 속한 간선을 못 쓰도록 하면, p[1] -> p[s]를 모두 쓰는 것은 불가능하다.

하나의 간선은 한 경로에만 포함가능하므로, 하나의 정점은 최대 indegree개의 정보에 관여한다.

이것의 총합은 M개니까, N + M개의 상태에 대해서 다익스트라를 하면 된다.

내 풀이는 더럽지 않지만, 내 구현이 좀 더러워서 정해가 다를 것 같다.

 

H. 피보나치 반반수열

 

초반 몇 개를 굴려보면, 피보나치 수열이 곧 어마무시하게 커지면서 1e18을 넘어선다는 것을 알 수 있다.

어떤 적당한 수 i, j에 대해 a[i] = f[j]라면, 이 j에 대해서 i는 유일하다.

또한 a[p] = q라면, 이러한 p도 유일하다. 

그리고 초반 몇개를 넘어가고서를 관찰해보면 대충 a[x] = x + 1에, a[x + 1] > 1e18의 형태가 반복된다.

 

따라서 초반 몇개를 아주 잘 만들어주고

뒷부분은 적당히 a[x] = x + 1, x + 2와 a[x] > 1e18을 잘 정리해주면 된다.

솔직히 그다지 즐겁게 풀 문제는 아닌 것 같다.

 

M. 산 색칠

 

우선 가능한지 여부부터 판단하자.

-> f[a]를 x = a에서 도화지의 높이, g[a]는 x = a에서 그림의 높이라 하면, f[a] = g[a]인 모든 위치에서 색칠해보면 된다.

필요한 색칠의 수는, 양쪽보다 높이가 높은 지점의 개수를 구하면 된다.

즉, h[i] < h[i + 1] > h[i + 2]인 i의 개수를 세주고, 이게 진짜 가능한지 확인해주면 된다.

 

굳이 역추적이 필요했을까...

h[i]가 극대면 색칠한다는게 사실상 이 문제 아이디어의 전부 같은데 그에 비하면 문제가 비대하다.

 

F. 두 트리

 

어떤 트리에 대해서 전위 순회 결과를 IN[x], 후위 순회 결과를 OUT[x]라고 한다면,

p가 q의 ancestor일 때 in[p] <= in[q] < out[q] <= out[p]가 성립한다.

따라서 두 트리에 대한 in1[a], in2[a]를 마치 좌표계에서의 x값, y값이라고 생각한다면,

b가 a의 ancestor임은, (in1[b], in2[b])와 (out1[b], out2[b])가 꼭짓점인 직사각형 내에 a가 존재함을 의미한다.

따라서 점이 N개, 심지어 좌표압축이 이미 된 상태로 주어지고, 여기서 2D segtree를 구현하면 끝난다.

시간제한이 5초로 매우 넉넉하기에, 이것이 거의 정해일 것이라고 예상했다.

 

small to large trick을 이용한 풀이를 처음에 생각했었는데, 구현이 꼬여서 N^2인줄 헷갈렸다.

아무튼, 기본적인 아이디어는 오일러 순회를 통해  segtree에서 구간 max query를 통해서 답을 구하겠다는 것이다.

즉, 두 번째 트리에 대해서 dfs를 돌면서 cur을 보고 있다면, cur의 모든 descendant가 켜진 상태인 segtree를 만들 것이다.

우선 adj를 subtree의 크기 순으로 정렬해준다.

이후에 트리순회를 할 때, child 1에서 child 2로 넘어갈 때, segtree의 모든 비트를 모두 꺼준다.

이때 마지막 child, 즉 subtree가 제일 큰 child에 대해서는 비트를 끄는 작업을 할 필요가 없다.

그러면, 미리 꺼둔 모든 descedant들, 즉 descendant 중에서 제일 큰 subtree에 속하지 않은 descendant들을 켜준다.

이 작업은 마치 N^2 * lgN으로 보이지만 NlgNlgN으로 할 수 있다.

 

I. 안테나 설치

 

안테나가 차지하는 지역이 [L, R]이라면, 비용은 Max(L, R) + (R - L)이 된다.

따라서 dp[i] = (i개의 안테나 설치를 위해 필요한 비용)이라고 정의한다면

dp[i] = min(dp[j] + Max(j, i) + (j - i)) = Min(dp[j] - j + Max(j, i)) + i가 된다.

여기서 여러개의 j에 대해서 Max(j, i)이 동일하다는 사실을 알 수 있다.

따라서 deque에 i 이하의 모든 x에 대해서 높이가 단조증가하도록 넣어두자.

예를 들어 deque에 p, q, r이 순서대로 있다면 p < q < r, a[p] > a[q] > a[r]이 성립하도록 넣어두자.

그렇다면, j가 (p, q]에 속한다면, Max(j, i)는 저절로 a[q]가 된다.

 

이때 i가 계속 바뀌고, deque에 새로운 원소가 아무리 들어오더라도, p, q만 유지된다면 (p, q]에서의 최솟값은 일정하다.

즉 미리 j in (p, q]에 대해서 Min(dp[j] - j + a[q]) = precalc를 계산해둔다면, i에 대해서 단순히 dp[i] = Min(precalc) + i 이다.

따라서 deque에 있는 원소들에 대해서, 제일 front에 있는 원소를 제외하면, 미리 값을 precalc하여 set 등에 넣어두자.

그러면 i에 대해서 Min(precalc) + i를 log 속도로 알아낼 수 있다.

그리고 deque의 front가 Max값이 되는 x들에 대해서는 segtree 등으로 계산을 해주면 된다.

 

B. I forgor 💀

 

우선은 카드를 총 뒤집은 횟수를 세고, 그것을 2로 나누어 필요한 턴의 수를 구하면 된다.

이때 각 절차에서 뒤집은 두 카드는 먼저뒤집/나중뒤집이라 부르고, 중복되는 두 카드를 첫 번째, 두 번째라 부르겠다.

 

어떤 동일 숫자를 가진 카드쌍은 다음과 같은 경우들로 나뉜다.

1) 첫 번째 카드를 먼저 뒤집고, 그 직후에 두 번째 카드를 나중 뒤집한 경우 -> 두 카드는 총 2번 뒤집는다

2) 미래에 두 번째 카드를 먼저 뒤집한 경우 -> 두 카드는 총 3번 뒤집는다.

3) 미래에 두 번째 카드를 나중 뒤집한 경우 -> 두 카드는 총 4번 뒤집는다.

따라서 각 경우의 수를 세주면 된다.

 

이때 내 직전에 두 번째 카드가 있을 경우 무조건 나는 먼저 뒤집힘을 알 수 있다.

-> 내 직전 카드가 먼저뒤집히면 그와 대응되는 카드를 뒤집기에, 나는 다음 절차에 먼저 뒤집힘

-> 내 직전 카드가 나중뒤집이면, 당연히 나는 먼저뒤집

따라서 먼저 뒤집과 나중 뒤집은 카드 x 앞에 있는 연속한 첫 번째 카드의 수의 기우성으로 결정됨을 알 수 있다.

-> 적당히 맨앞카드, 맨뒤카드, 최초 두 번째 카드의 위치, ... 등을 잘 관리하는 segtree로 답을 구할 수 있다.

만일 정직하게 위의 풀이대로 하면, 상당히 더러운 merge 함수를 짜면 AC를 받을 수 있다.