CodeTON Round 1 (Div. 1 + Div. 2)

문제풀기

lml 2022. 3. 26. 12:25

보통 div2를 풀면 ABC는 뇌가 없어도 된단 마인드로 푼다.

div1 + div2가 나오면 어디부터 고민을 해야하는지가 애매해져서 뭔가 맘에 안든다.

문제 느낌이 앳코더 같았다.

A. Good Pairs

크기관계가 a_i < a_k < a_j면 무조건 성립하기 때문에 최대와 최소를 찾아주면 된다.

B. Subtract Operation

해보면 결국 a_i - a_j가 k가 될 수 있는지 확인하면 된다는 것을 알 수 있다.

C. Make Equal With Mod

만일 1보다 큰 숫자로 단일화시키는 것이 가능하다면 그 숫자로 다시 mod를 굴리면 모두 0이 된다.

-> 따라서 모두 0으로, 혹은 모두 1으로 굴려줄 수 있는지 확인하면 된다.

-> 만일 애초에 1이 없다면, 수열에 존재하는 모든 숫자에 대해서 큰 순서로 mod계산을 해주면 모두 0이된다.

-> 1이 수열에 존재하는 경우 모든 숫자를 1로 바꾸는 것이 가능한가?

-> 인접한 두 수 x, x + 1가 존재하는 것은 모두 1로 바꾸는 것이 불가능함과 필요충분하다.

pf) 만일 인접한 두 숫자가 없다면 수열에 존재하는 모든 숫자에 대해 큰 순서로 (a_i - 1)로 mod계산을 하면 된다.

만일 인접한 두 수 x, x + 1이 존재한다면 mod값이 0이 될 수 없으므로 이 둘은 영원히 같아질 수 없다.

D. K-good

전체를 합한식이 k * (m + (k + 1) / 2)꼴이므로 n의 약수들만 적절히 확인하면 된다.-> 하지만 (k + 1) / 2이 정수 보장이 안되므로 2^i들에 대해서는 조금 조심해야할 필요가 없다.

->2^i들에 대해서 모두 확인해주고, 제일 작은 홀수 소인수에 대해서 확인해주면 된다.

-> 제일 작은 홀수 소인수일 필요도 없다. n이 홀수가 될 때까지 2로 나눈 숫자만 확인해도 된다.

E. Equal Tree Sums

어떤 지점을 root로 잡고 그에대해 상대적인 depth들을 구한다.-> depth % 2 = 1 이면 -(인접한 노드의 수) 아니라면 +(인접한 노드의 수)를 부여하면 된다.

cf) size()가 unsigned라서 -adj[i].size()를 하는 순간 overflow 비슷한게되어 4e9로 가버린다. 이래서 WA당했다.

풀이)

어떤 노드 cur의 자식들 c1, c2 ... 들에 대해 (c1 이하의 노드들의 합) = (c2 이하의 노드들의 합) = ... 이다.

-> 따라서 어떤 노드 이하의 자식들의 합을 어떤 값으로 고정시켜주어야 한다.

-> notation의 편의를 위해서 특정한 root (=0)에 대해 depth가 같다면 이 값이 모두 동일하다고 가정하자.

(사실 같을 필요는 없다. cur에 대해 살펴본 후에 cur의 부모나 c1으로 들어가면 c2, c3..등은 관심사항이 아니다.)

-> depth가 x인 노드 cur에 대해서 본인 이하의 노드들의 a값의 합이 반드시 어떤 숫자 b[x]라고 정하자.

-> 그렇다면 cur에 대해 a[cur]는 b[x] - (자식의 수) * b[x - 1]이 된다.

-> a[cur] != 0이니, 제일 깊은 b[x]를 1로 결정하고 b[x - 1] > b[x] * (자식의 수)가 되도록 b[x - 1]을 설정 가능

-> 하지만 위의 방식대로라면 a[i] > 1e5인 케이스가 있으니 불가능

-> b[x] 와 b[x - 1]의 부호가 항상 다르면 깔끔히 해결되니 b[x] = 1, b[x - 1] = -1을 하면 답이 된다.

F. Parametric MST

수열 a는 sorted이라고 가정하자.

-> a_i * a_j + t(a_i + a_j) = (a_i + t) * (a_j + t) - t^2이므로 t와 i가 고정되어 있다면 j는 0이나 n - 1인게 이득이다.

-> a_i가 0이랑 연결될지, n - 1과 연결될지는 t = -a_i일 때 바뀌므로 모든 i에 대해 t = -a_i만 계산해주면 된다.

-> 모든 t = -a_i에 대해 계산해주고 추가로 t =1e6, -1e6을 확인하여 답이 INF가 되어야하는지 확인한다.