Codeforces Round 864 (Div. 2)

https://codeforces.com/contest/1797

 

나쁘지 않은거 같기도 하고, 좀 개같은거 같기도 하고

솔직히 앳코더식 서술이 좋은데 코포 스타일의 서술이 사라지면 그거대로 서운할 것 같다.

개인적으로 문제 이름들이 다 "Li Hua and ~"이고 "unusual starting time"이라서 인상만으로는 거를만 했다.

 

A. Li Hua and Maze

 

(x1, y1)에서 (x2, y2)로 갈 때 몇 개의 칸을 막아야 통하지 않게 할 수 있는가.

크게 2가지 생각을 할 수 있다.

1) 한 칸을 다 둘러싼다

2) 한 행이나 열을 막는다 -> 이거는 무조건 1)보다 더 많은 칸을 쓴다.

따라서 (x1, y1)이나 (x2, y2)를 둘러쌀 때 필요한 칸의 최소 개수를 구하면 된다.

 

B. Li Hua and Pattern

 

180도 대칭이 되기 위해서는 위쪽 절반을 아래쪽 절반과 똑같이 매칭시켜준다.

다만 "exactly K operation"을 사용해야하기 때문에 추가적인 처리를 해야한다.

만일 N이 홀수라면 정중앙 칸을 남은 횟수만큼 쓰면 되고, N이 짝수면 홀짝성이 맞아야 한다.

 

C. LI Hua and Chess

 

king이 있는 칸을 (x, y)라고 하자.

만일 "? A B" 라는 질문을 던지면 max(abs(A - x), abs(B - y))가 돌아온다.

Question을 3번 이하로만 할 수 밖에 없기에 이분 탐색은 아니고 적당히 결정됨을 알 수 있다.

그렇기 때문에 abs(A - x)를 A - x나 x - A로 확정시켜주는 (1, 1), (n, m)을 사용해야함을 유추할 수 있다.

 

(1, 1)과 (n, m)을 던지면 max(A-1, B-1) = x1, max(n-A, m-B) = x2를 구할 수 있다.

i) x1 + x2 = n - 1 : A = x1 + 1 확정 -> 이제 "? A 1"을 던지면 된다.

ii) x1 + x2 = m - 1 : B = x1 + 1 확정 -> 이제 "? 1 B"를 던지면 된다.

모두 아니라면 두 가지 케이스를 더 확인해주면 된다. 

iii) A = x1 + 1, B = m - x2

iv) B = x1 + 1, A = n - x2

이 두 케이스는 A, B가 그대로 정해지기에 "? A B"를 물어봐서 0이 나오는지 확인하면 된다.

단, A, B가 valid한 question인지 확인해주어야 함.

 

D. Li Hua and Tree

 

vector<set<pii>>를 이용하여 각 벡터에 {subtree_size[son], -son}을 다 저장해두고 있으면 된다.

그러면 각 노드 x에 대해서 heavy son을 구할 수 있다.

 

문제의 2번째 operation을 보면 x, heavy son, parent간의 관계만 바뀜을 알 수 있다. (다른 vertex 영향 x)

1) x의 자식에서 heavy son 사라짐

2) parent의 자식에서 x가 사라짐

3) heavy son의 자식에 x가 생김

4) parent의 자식에 heavy son이 생김

-> 여기서 바뀌는 것만 모두 갱신시켜주면 된다.

 

E. Li Hua and Array

 

phi를 5e6까지 구하는 구현을 알고 싶다면  https://codeforces.com/blog/entry/54090 참고

어떤 숫자 x에 대해서 x = phi[x]를 반복하여 1이 되기 위해서 필요한 횟수를 to1[x]라고 하자.

이때 실제로 해보면 to1이 최댓값이 23정도라는 것을 알 수 있다. (대략 log(MAXA))

 

그렇다면 세그트리에서 한 노드에서 2가지 정보를 저장해주면 된다.

1) num[node] = (내 범위 내의 숫자들이 phi값이 모두 같아진다면 어떤 값에서 같아지는가)

2) vector<int> cnt(25) : cnt[x] = (to1값이 x인 숫자들의 개수)

이 정보만 있으면 이 범위 내에서 x = phi[x]를 이용하여 모든 숫자들의 값을 같게 하기 위해서는 

\(\sum_{x=0}^{24}{max(0, x - to1[num]) * cnt[x]}\) 번이 필요하다.

 

merge할 때에는 단순하게 cnt는 각각을 더해주고 num들은 같아질 때까지 더 큰거에 x = phi[x]처리를 하면 된다.

두 개 다 log(MAXA)의 범위 아래에서 가능하다는 것을 알 수 있다.

따라서 segtree 자체에서 나오는 NlgN, merge등을 할 때 필요한 lgMAXA를 보면 총 복잡도 N * lgN * lgMAXA

 

Editorial은 x -> phi[x]로 가는 간선들을 만들어서 그래프를 형성하였다.

그래서 loglogMAXA의 시간으로 어떤 두 숫자들의 phi값이 같아지는지 구했다. (LCA를 향해 가야하기 때문)

segtree에 i) (필요한 operation의 수) ii) (같아질 때의 값) 을 저장해두면 된다.

다만 이러면 어떤 범위에 x = phi[x]를 취하는 것이 불가능하다. 

그래서 각 노드를 하나하나 방문해주는 수 밖에 없다.

하지만 어차피 모든 숫자에 대해서 가능한 operation의 수가 lgMAXA이므로 복잡도는 보장된다고 한다.

 

F. Li Hua and Path 

 

cf) Kruskal reconstruction tree, DSU-tree https://mzhang2021.github.io/cp-blog/kruskal/ 참고

reconstruction tree 2개인 MaxTree, MinTree를 만들자.

어떤 간선 (u, v)가 있다면 u 밑에 v를 이어준다.

그 다음에 v가 자신의 parent보다 작아질/커질 때까지 rotate 시키면 된다. (마치 D에서 한 것처럼)

그렇다면 u에서 v로 가는 경로에서 최댓값은 MaxTree에서 LCA(u, v)이고 최솟값은 MinTree에서 LCA(u, v)이다.

 

따라서 어떤 정점 u가 최대인 경로의 개수는 자기 subtree에 있는 정점의 개수로 쉽게 구할 수 있다.

그리고 두 조건을 모두 만족시키는 것은 inverse세듯이 세면 셀 수 있다.

 

풀이가 매우 간단하다.

아마도 DSU-tree를 깨닫기라도 했으면 다들 푼 것 같다.