Codeforces Round 947 (Div. 1 + Div. 2)

https://codeforces.com/contest/1975

이 정도 퍼포를 또 해야 2600.... 쉽지 않다.

 

A. Bazoka and Mocha's Array

 

operation을 몇 번 가하든 간에 결국 0번 혹은 1번 가한 상태랑 똑같다.

따라서 모든 N가지 경우를 확인해보면 된다.

 

B. 378QAQ and Mocha's Array

 

편의상 a를 정렬하자.

a가 beautiful 하다면, a[i]와 a[j] 중 하나는 반드시 a[0]와 동일하다. (만일 아니라면, a[0]는 나눠질 수 없음)

그러면 a[0]로 나뉘지 않는 애들을 모아 g = (a[x] % a[0] != 0인 모든 a[x]의 gcd 값)이라고 하자.

g % a[j] == 0인 j가 존재해야만 yes가 될 수 있다.

 

C. Chamo and Mocha's Array

 

한 번이라도 불어날 수 있다면 무한히 늘릴 수 있다.

예를 들어 [L, R]에서 x로 모두 맞추었다면, 이후 [L - 1, R], [L - 2, R], ...과 [L, R + 1], [L, R + 2], ...을 시행하면 된다.

따라서 한 번이라도 median이 되는 x 중 최댓값을 구하면 된다.

이때 모든 [L, L + 1]과 [L, L + 2]만 확인하면 충분하다.

pf) median이 x 이상인 경우가 있다는 뜻은 절반 이상이 x 이상인 [L, R]이 존재한다.

-> 절반 이상이 x 이상인 구간 내에는 반드시 a[i], a[i + 1] 모두 x 이상이거나 a[i], a[i + 2]가 x 이상인 i가 존재한다.

 

D. Paint the Tree

 

B가 최초로 red를 밟는 순간을 생각해보자.

이후로 B는 어차피 모든 Vertex를 paint해야 한다.

이때 B의 최적의 순회는 2 * (N - 1) - (제일 depth가 큰 vertex의 depth)이 필요하다.

그러면 당연히 A가 이 최적의 순회를 미리 한 칸씩, 혹은 동시에 가는게 최적이다.

따라서 (A, B가 만나는데 걸리는 시간) + 2 * (N - 1) - (제일 depth가 큰 vertex의 depth)가 답이 된다.

(A, B가 만나는데 걸리는 시간)은 (거리 + 1) / 2로 구할 수 있다.

 

E. Chain Queries

 

뇌쓰기 귀찮았다.

Black인 모든 vertex들을 가진 set S = {{depth[x], x} | vertex x is black}를 관리하자

1) S에서 제일 depth가 작은 노드, LCA를 고르자.

2) S에서 제일 depth가 큰 노드인 S를 잡자. 이는 chain의 한 시작점이 될 것이다.

3) LCA에서 S를 향해 한 칸 내려간 노드를 SR이라 하자.

4) segtree를 이용하여 [in[SR], out[SR])을 제외한 구간에서 depth가 제일 큰 black vertex를 E라 하자.

5) 이때 (S, E)가 chain이 될 것이고

-> (S, E)로 이어지는 길에 white가 존재하는지 hld로 확인할 수 있다.

-> (depth[S] + depth[E] - depth[LCA] * 2 + 1) = S.size()로 모든 black vertex가 이 위에 존재하는지 확인 가능하다.

 

원래 생각했던게 정해에 가깝다.

즉, 모든 black vertex에 대해 2 정점만 1개의 black vertex와 인접하고 나머지는 전부 2개와 인접해야 한다.

다만, '인접'이라고 생각하면 O(NQ)가 되버리기에 관리가 어렵다.

1) '자식' 중에서 black vertex가 2인게 1개, 0인게 2개, 나머지는 전부 1개

2) '자식' 중에서 black vertex가 0인게 1개, 나머지는 전부 1개

이러면 부모와 자식관계만 따지면 되기에 O(1)로 된다.

 

F. Set

 

S에 n - 1이 존재한다고 생각해보자.

그러면 n - 1을 지니지 않은 모든 T에 대해서 |S & T| + 1 == |S & (T + {n - 1})|이 성립하게 된다.

반대로 S에 n - 1이 없다면 |S & T| == |S & (T + {n - 1})|이 성립한다.

그러면 n - 1이 존재할 때와 안 존재할 때에 새로운 v'을 만들 수 있다.

-> 존재한다면 v'[i] = v[i] & (v[i + (1 << n - 1)] >> 1)

-> 존재하지 않는다면 v'[i] = v[i] & v[i + (1 << n - 1)]

즉 Solve(bit, cur, v)라는 함수가 있다면, bit은 1씩 감소하고, v는 반으로 나뉘게 된다.

최종으로 bit = -1일 때 v = {1}이 된다면 cur이 가능하다는 뜻이고, 그게 아니면 불가능하다는 뜻이다.

코드를 참고하라.

 

G. Zimpha Fan Club

 

S = s1 * s2 * ... * sn 이라고 할 수 있고 T = t1 * t2 * .... * tm이라고 할 수 있다. (S[i], T[i] can be empty)

보면 알겠지만 둘 다 *이 존재할 경우에 min(s1, t1)과 min(sn, tm)만 공유하면 무조건 대응이 된다.

이 경우 S[i] == T[i] or S[i] = '-' or T[i] = '-'를 앞에서부터, 그리고 뒤에서부터 확인하면 된다.

 

따라서 한쪽에 *이 없는 것만 해결하면 된다.

S = s1 * s2 * ... * sn이고 T는 그냥 *이 없다고 생각하자.

그러면 T에서 순서대로 s1, s2,... sn과 대응되는 부분이 존재해야 한다.

즉 (L[1], R[1]), (L[2], R[2]), ... (L[n], R[n])이 존재하여 s[i] = T.substr(L[i], R[i] - L[i])여야 한다. (단, R[i] <= L[i + 1])

이것을 찾는 과정은 단순히 T의 맨 앞에서부터 s[i]들을 찾아나가면 된다.

결국 s, t모두 *이 없고 -는 있는 string일 때 t 내에서 s 찾는 문제가 된다.

언뜻 보면 KMP를 통해 O(|S| + |T|)로 가능해 보이지만 이것은 KMP로 불가능하다.

 

이건 FFT로 해야 한다고 한다. 

만일 '-'은 0으로 대응하고 나머지는 1~26으로 대응된다고 할 때

SUM( (S[i] > 0) * (T[i + j] > 0) * (S[i] - T[i + j]) ^ 2 = 0이면 S[L, R]과 T[L + j, R + j]이 대응된다.

이걸 확인하는 식을 만들면

\(\sum_{i=L}^{R}( (S[i] > 0) * (T[i + j] > 0) * (S[i] - T[i + j]) ^ 2 = 0 \)
\(\sum( (S[i] > 0) * (T[i + j] > 0) * (S[i]^2 + T[i + j]^2 - 2S[i]T[i+j]) = 0 \)
\((\sum S[i]^2x^{-i}) * (\sum (T[i] > 0)*x^i) + (\sum (S[i] > 0) *x^{-i}) * (\sum T[i]^2*x^i)-2(\sum S[i]*x^{-i})*(\sum T[i]*x^i)\)

이렇게 쪼개버릴 수 있다.

 

다만 문제점은 이러면 [L, R]만 찾을 수 있기에 O((조각의 개수) * (S + T) log(S + T))꼴이 나버린다는 것이다.

이것의 해결방안은 매번 전체 T를 확인하는게 아니라 적당히 T[x, x + slen * 2]씩만 확인하는 것이다.

이 범위 내에 만일 S[L, R]이 있다면 찾은거고, 못 찾더라도 T의 앞쪽 slen만큼을 버릴 수 있다.

따라서 이러면 O((S + T) log(S + T)).