CodeForces Round 947 - Div 1.5

https://codeforces.com/contest/1975

 

 

Performance Rating : 2450

 

A

한 번의 수행밖에 못하므로 $a_i>a_{i+1}$인 $i$의 개수를 세고 0개라면 "Yes", 2개 이상이라면 "No", 1개라면 $a_1$과 $a_n$의 크기를 비교하였다.

 

B

가장 작은 수는 다른 수의 어떤 수의 배수일 수 없기 때문에 정렬을 해두고 처음부터 수를 보면서 $a_0$의 배수인지 확인하고 배수가 아니라면 $a_i$를 저장해두고 나머지 수들이 두 수중 하나의 배수인지 확인하였다. 구현 과정에서 $a[i]$라고 써야 하는 것을 $x$를 쓰는 실수를 하여 WA를 한 번 받았다.

 

C

처음에 순서를 바꿀 수 있는 것인줄 알고 두 번째로 큰 수를 출력했다가 틀렸다. 생각을 해보다가 그러면 답이 $\underset{1\leq i\leq n-1}{\mathrm{max}}(\mathrm{min}(a_i, a_{i+1}))$인줄 알고 두 번째 제출을 했다가 틀렸다. 2개를 묶는것 보다는 3개씩 묶는 것이 낫다는 생각을 했고 고쳐서 맞았다.

 

D

결국 두 노드의 거리를 1 또는 0으로 좁혀놓고 dfs를 하듯이 순회해 주는 것이 가장 최선이라는 것을 정성적으로 증명하고 dfs로 문제를 해결했다.

 

E

Rooted tree에서 chain이 어떤 성질을 가질지 생각해 보다가 부모 입장에서 $c_i=1$인 자식 노드의 개수는 비교적 빠른 시간 안에 구할 수 있고 $c_i=1$인 노드들의 자식 노드 중 $c_j=1$인 것의 개수를 관리하면 chain을 이루었는지도 파악하는 것이 가능할 것 같았다. chain을 이루고 있다면 $c_i=1$인 노드들의 자식 노드 중 $c_j=1$인 것의 개수의 구성이 하나만 $0$, 나머지 $1$이거나 $0$이 2개, $2$가 하나, $1$이 나머지이면서 $2$인 노드의 부모 노드가 $1$이 아니면 된다는 것을 알게 되었고 이를 구현했다.

 

F

문제를 보고 생각한 것은 조건이 너무 많다는 것이었다. 그래서 조건 2개를 하나로 합쳐가면서 문제를 풀어야 시간 안에 들어올 것 같다는 생각을 했지만 구현 할 방법을 떠올리지 못했다. 끝나고 업솔빙 과정에서 풀이의 방향성은 맞았지만 dfs로 구현할 수 있다는 것을 몰랐던 것이었음을 확인했다.