(8/14 크리님의 생일을 맞아서 다시 풀어보고 있다. YZ 풀이 추가. RST 풀이 약간 추가)
범수형이 검수하러 간 틈을 타서 몰래 껴들어갔다.
팀 이름은 내가 AcornCkiGs14004Team으로 지었다. 하지만 ainta가 지은 기만 팀명에 능욕당했다. 이럴 줄 알았으면 ↑우리보다못하는팀 으로 바꾸고 나올 걸 그랬다...
아쉬움 없을 만큼 하고 나왔기 때문에 아주 즐거웠다.
사실 극후반부에 서버가 터져서 PQ 제출에 문제가 있었다. 열심히 제출해도 안 돼서 상당히 짜증났지만, 알고 보니 내 제출이 4시간 59분 59초에 기적적으로 큐에 들어가서 2점을 득점했었다 (...) 그래서 안 짜증났다.
후기는 그냥 좀 재미있던 것만 간략하게 쓰려고 한다. 몇 문제는 스포일러도 있다 (물론 가려놨다).
ABC
한 10분 쯤에 dotorya님이 격침했다.
DE
출제자 풀이가 틀린 문제였다. 그게 얼마나 심각했냐면 예제 2가 안 나왔다 (...) "정수 점만 가져갈 수 있습니다" 라는 조건으로 겨우 살렸지만 dotorya님이 날렸던 20분은 되찾지 못했다. ㄹㅇ루노답
HI
재밌는 문제다. 나중에 풀어봐야지
JK
ainta랑 같이 돌았던 opencup에 똑같은 문제가 있었다. k번째를 안 찍는 거 빼고 전부 똑같았다. 난 이걸 그 전에 풀어봤기 때문에 풀 수 있었지만 어째 그 때도 인타는 신기하게 잘 풀더라.
LM
Dynamic MST로 비비다가 실패했다. 사실 별로 승산이 없는 접근이기도 했다 ㅋㅋ 크리님한테 정해 스포일러를 들었는데 아주 멋진 문제였다.
만약에 한 정점에 연결된 간선이 1개라면, MST 상에서 그 간선이 잇는 두 점 사이의 최대 cost 간선을 끊어버리면 새로운 MST를 찾을 수 있다. 2개라면, 세개의 점 사이에서 적당한 간선을 골라서 끊어버리면 새로운 MST를 찾을 수 있다. 이러한 생각을 일반화하면 정해를 찾을 수 있다.
각각의 정점 R마다, R - i 를 잇는 간선이 강제 된다면, i번 정점을 마킹하자. 이제 트리에서 적당한 간선을 끊어서, 모든 포레스트가 1개 이상의 마킹된 정점을 가지게 하고 (R번 정점도 마킹해야 한다), 그 과정에서 끊은 간선의 cost 합을 최대화해야 한다. 이는 tree dp를 통해서 O(N)에 해결할 수 있다. 여기까지 O(n^2).
이제 tree dp가 O(마킹된 정점 개수) 에 비례하는 시간에 돌도록 최적화해야 하는데, 마킹의 개수가 3개 ~ 5개인 상황을 그려보면 모든 N개의 정점이 중요한 것이 아니라는 것을 간파할 수 있다. 실제로 필요한 정점과 간선들을 그려보면, 리프 (= 마킹된 정점)과, 리프를 합쳐주는 몇개의 노드, 그리고 그 사이를 잇는 긴 체인들의 형태를 띄게 될 것이다. 긴 체인 중에서 중요한 것은 가장 가중치가 큰 간선밖에 없으니 긴 체인은 간선 하나로 치환된다.
고로, 저러한 형태의 트리를 O(마킹된 정점 개수) 정도에 만들어 줄 수 있다면, 똑같이 tree dp를 사용해서 문제를 해결할 수 있다.
여기서 사용할 수 있는 괜찮은 트릭이 "트리 압축"이다. MST의 루트를 1로 잡아서 rooted tree로 만들어 주자. 모든 마킹된 정점을 dfs preorder로 정렬하면, 저러한 트리에서 실제로 필요한 정점들은
* 마킹된 정점
* 두 연속된 마킹된 정점 간의 LCA
밖에 없다.
이러한 정점 리스트를 알면, 다시 preorder로 정렬해 주고 스택을 사용해서 압축된 트리의 형태를 알 수 있다. 압축된 트리의 가중치는, MST의 path maximum일 것이다. 즉, path maximum과 LCA를 lgN 정도에 빠르게 계산할 수 있다면 O(마킹된 정점 개수 * lgN)에 해결 가능한데, 둘다 sparse table을 사용해서 O(nlgn) 전처리 / O(lgn) 쿼리 가 가능하다.
결론적으로 O((n + m) lgn) 에 문제를 해결할 수 있다.
NO
재밌는 문제였다.
일단 요상한 식의 정체를 파악해보자. f(S, P) = ((S[0, |P|) = P) + (S[1, 1 + |P|) == P) + ... + (S[N-|P|, |P|) == P)) 라는 boolean 식의 합으로 정리할 수 있다. 이걸 제곱해서 풀어보면 f(S, P)^2 = (0 <= i, j <= N - |P|) (S[i, i + |P|) == P && S[j, j + |P|) == P) 라는 식이 나온다. 이걸 모든 가능한 P에 대해서 더해야 한다.
근데 사실 S[i, i + |P|) == P && S[j, j + |P|) == P를 둘다 만족하는 P의 개수는 0이거나 1이다. 그것도, S[i, i + |P|) == S[j, j + |P|) 일 때만 1이고, 아니면 0이다. 그러니까 결국은 S[i, i + k) == S[j, j + k)를 만족하는 i, j, k triplet을 세는 문제이다.
이제 문자열을 뒤집어서 suffix에 대해서 저 triplet을 세면, 결국 P_i = (i <= j < k < |S|) Sigma(LCP[j, k]) * 2 + (N - i) * (N - i - 1) / 2 라는 식이 나오고 이것이 N^2 풀이이다.
이제 편의상 P_i = (i <= j < k < |S|) Sigma(LCP[j, k]) 라고 두고 이것만 계산해보자. 모든 쌍 0 <= i < j < |S|에 대해서, P_0 ... P_i 구간에 LCP[i, j]를 더하는 것을 반복하면 문제를 풀 수 있다. 구간에 더하는 것은 변홧값 배열을 쓰면 P_i 하나에만 더한다고 생각할 수도 있고, LCP는 결국 suffix array로 구한다고 하면,
이는 분할 정복으로 해결할 수 있다. i <= m && j > m을 만족하는 모든 쌍에 대해서 저 과정을 O(nlgn)에 처리해보자. 골자는 같은 LCP 값을 가지는 원소들을 한번에 처리하는 것이다. 처음에는 m, m+1부터 시작한다, 만약 lcp(m)이 lcp(m+2)보다 작다면, m+1을 오른쪽으로 늘려주고, 아니면 m을 왼쪽으로 내려준다. 그러면 m+1이 m+2가 되면서 (m, m+2)의 LCP 값이 추가된다. 일반화해서, 현재 [s, e] 구간을 보고 있다면, lcp(s)가 lcp(e+1)보다 작은지 큰지에 따라서 다음에 볼 원소를 고정하고, 만약에 e+1이 추가되면 [s, m] x {e+1}, 아니면 {s-1} x [m, e] 를 한번에 처리해준다.
이제 한번에 처리해 주는 게 문제다. 더할 값은 알지만, 어디다 더할 지 모르기 때문이다. e+1을 넣었다 치자. [s, m] 구간에 대해서, 만약 sfx[i] < sfx[e+1] 이면 a[sfx[i]] 에 값이 더해지고 아니면 a[sfx[e+1]]에 값이 더해진다. a[sfx[e+1]] 에 값을 더해주는 것은 쉽다. 구간에서 sfx[i] > sfx[e+1] 인 원소의 개수만 알면 되고, 이는 분할 정복 과정에 BIT를 넣거나 아니면 아예 persistent tree같은 걸 써도 되기 때문이다. (난 전자를 택했다.)
반대의 상황은 상당히 골치아프게 느껴질 지도 모르지만 예상 외로 그렇지 않다. 반대의 상황은, [s, m] 구간에 대해서, sfx[i] < sfx[e+1] 이면, a[sfx[i]] 에 임의의 값을 더하는 것이다. 그때 그때 처리하면 머리가 아프지만, 저러한 연산들을 따로 저장해 놓고, 이후에 Line Sweeping을 한번 적용하면 쉽다.
시간 복잡도는 마지막 Line Sweeping에 대해서 좌우된다. Line Sweeping은 nlgn개의 이벤트가 있고 그 과정에서 O(lgn)의 BIT를 사용하므로 총 로그제곱이다.
RST
대회 때는 자비없는 2점 서브태스크의 상태를 보고 생각조차 하지 않았으나, 끝나고 보니 아주 신기한 문제인거 같다.
풀이를 보고 이해는 했는데 수식편집기의 보조가 없이는 풀이를 쓸 수가 없다. 그리고 난 수식편집기를 어찌 쓰는지 잘 모른다. 고로 크리님 블로그를 참고하자..
대충 키워드만 설명하자면, 결국 DP를 구하는 것이 행렬 연산과 역행렬 연산의 조합이라 쿼리 당 O(53^3)에 해결할 수 있고, 이 행렬 / 역행렬 연산을 잘 분석해 보면 굉장히 단순한 형태라는 것을 더 관찰하면 이를 쿼리 당 O(53)까지 줄일 수 있다.
YZ
CERC2015 Looping Labyrinth 문제의 약한 버전이라고 한다. 대회 중에는 상수가 풀었다.
Looping Labyrinth를 풀면서 풀어버렸다. 그 문제 증명의 중간 정도를 알면 풀 수 있다.
격자를 잇는 그래프를 만드는데, 인접한 셀이 같은 색이면 에지를 이어준다. 격자를 튀어나갔다가 다시 돌아오는 등의 경우가 문제인데, 이거를 (N-1, i)와 (0, i)를 잇는 간선을 만들어주는 식으로 해결하자.
물론 단순히 하면 말도 안되니까 에지에 추가적인 정보를 더 넣어줘야 한다. 에지에 가중치 두개를 주는데, 이쪽으로 가면 X좌표료 몇N 떨어진 영역인가? Y좌표로 몇M 떨어진 영역이가? 라는 식의 정보이다. (N-1, i) / (0, i)를 이으면 +N, -N 정도의 X좌표 변화가 무시되니 +1, -1을 넣어주는 식이다. 물론 (i, M-1) / (i, 0) 에도 동일하게.
이제 컴포넌트마다 dfs를 하는데 각 컴포넌트에서 두 가중치의 합 중 하나라도 0이 아닌 사이클이 나오면 infinity이다. 아니면 그 컴포넌트 크기가 답이 된다. 컴포넌트가 덮는 영역에 답을 칠해주면 된다.
