Codeforces Round #848 (Div. 2)

어제 갑자기 블로그 조회수가 튀었길래 원인을 확인해보았더니 모 PS 커뮤니티에서 의문의 PS러가 이 블로그를 일종의 우수 블로그로 선정해주었다는 사실을 알게 되었다. 엄청난 분들과 함께 이름이 올라가 있어 기분이 좋았다. 뽑힌 김에 블로그 활동을 조금 더 성실히 해 보고자 오늘 있던 코포 후기부터 작성해보려 한다.

 

 

A. Flip Flop Sum (0:02, +)

원래 합을 \(S\)라 하자. 모두 1이면 \(S-4\), 연달아 있는 -1이 하나라도 있으면 \(S+4\), 모두 아니면 \(S\)가 답이다.

 

B. The Forbidden Permutation (0:14, +1)

문제가 좀 억지스럽다. 일단 Not good인지 판별을 먼저 하고, Not good이라면 인접한 쌍을 역전시키거나 거리를 \(d\) 이상으로 벌리는 것이 최적이다. \(d<N\)인 줄 알았는데 \(d \leq N\)이라 한 번 틀렸다. 왜 저렇게 둔 지는 모르겠다.

 

C. Flexible String (0:25, +)

한 인덱스를 두 번 이상 바꿀 일은 없으므로 기존에 있던 문자들 중 \(k\)개를 잘 골라 바꾸어 주는 것이 최적이다. 조건에 의해 모든 경우인 \(2^{10}\)가지를 다 보아도 넉넉히 통과할 수 있다.

 

D. Flexible String Revisit (0:57, +)

\(t_i\)를 \(i\)개가 다를 때의 기댓값이라 하면 \(t_0 = 0, t_N = 1 + t_{N-1}, t_i = 1 + \frac{i}{N} t_{i-1} + \frac{N-i}{N} t_{i+1} \) 이다. 변수 하나를 더 정의해 \(t_i = a_i + t_{i-1}\)이라 하자. 식을 잘 정리하면 \(a_i = \frac{(N + (N-i)a_{i+1})}{i} \)라는 사실을 알 수 있다. 이를 DP를 통해 다 구해준 뒤 앞에서부터 더하면 \(t_x\)를 구할 수 있다.

 

E. The Tree Has Fallen! (upsolved)

그냥 배열에서의 XOR 최대화 문제는 가우스 소거법을 통해 해결할 수 있음이 잘 알려져 있다. 우리는 이를 매 쿼리마다 트리의 특정 영역에서 구해야 한다. 특정 영역이란 루트를 1로 보았을 때 

1) \(r = v\)인 경우 - 트리 전체

2) \(v\)가 \(r\)의 조상인 경우 - 트리 전체에서 \(v\)에서 \(r\)로 향하는 방향의 서브트리를 뺀 부분

3) 그 외 - \(v\)의 서브트리

이다. 우선, 1과 3은 각 정점에 대해 서브트리의 모든 정점에 대해 가우스 소거법을 한 vector를 저장해주면 된다. 정점에 적힌 값이 최대 \(10^9\)이므로 각 vector의 최대 크기는 30 정도이다. 따라서 DFS를 하며 자식 노드의 vector를 잘 합쳐 주는 식으로 구현하면 \(O(30N)\) 정도에 전처리를 할 수 있다.

2번 경우가 좀 어려운데, 저러한 형태의 영역은 어차피 최대 \(O(N)\)개이다. 따라서 전처리를 해 준다고 생각하자. 2번과 비슷하게 진행하면 되지만, 시간 초과가 나지 않도록 적절한 구현 방법을 찾아야 한다. 우선 현재 노드를 기준으로 위쪽의 정보는 부모 노드에게서 가져올 수 있고, 각 자식에 대해 해당 자식의 서브트리만 빼고 다른 모든 자식의 서브트리에 대해 가우스 소거법을 한 결과가 필요하다. 이를 잘못 구현하면 시간 복잡도가 최대 차수의 제곱에 비례하는 상황이 나온다. 나는 이를 위해 가우스 소거법을 누적합처럼 저장한 후 양 쪽을 합쳐주는 방법을 이용하였다. 나는 처음에 TLE를 한 번 받고, 이를 수정했지만 다시 TLE를 받았다. 틀릴 수 없는 코드라 대회 끝나고 long long을 모두 int로 고쳤더니 AC를 받을 수 있었다.

다른 방법으로는 위 구간이 DFS ordering 상에서 하나의 구간, 또는 두 구간의 합으로 표현된다는 사실을 이용해 가우스 소거법 과정을 merge sort tree처럼 저장하고 매 쿼리마다 합치는 방법이 있는 것 같다.