Codeforces Round #695 (Div. 2) 후기

Codeforces Round #695 (Div. 2)

---

A. Wizard of Orz

약간 함정스러운 문제였다. 무조건 \(989\cdots \)로 시작하는게 가장 크다.

 

B. Hills And Valleys

\(a_i\)를 바꿨을 때, 개수가 변하는 요인은 \([a_{i-2},a_{i-1},a_i]\)과 \([a_{i-1},a_{i},a_{i+1}]\)과 \([a_{i},a_{i+1},a_{i+2}]\)로 세 가지 뿐이니 \(a_i\)를 적당히 바꾼 뒤에 개수를 비교해주면 된다.

이 때 적당히가 어느정도인지가 관건인데, \(a_{i-1}\)또는 \(a_{i+1}\) 중 하나가 답이 될 수 있다. 나는 대회 때는 적당히 저 둘을 포함한 \(10\)가지 정도 다 검사했다.

 

C. Three Bags

첫 문단의 수가 여러번 나타난다는 말이 무슨 뜻인지 이해가 안 가서 D번부터 풀었는데, 아직도 이해가 안 간다.
일단 그걸 피하는 방법이 무조건 있을거라고 생각하고 풀어보면, 최선의 방법은 두 가지 경우가 있다.

\(1.\) 하나만 남길 가방(\(A\))과 더할 가방(\(B\)), 나머지 가방(\(C\))을 정한다. 그리고 \(A\)에 하나만 남기고 전부 \(C\)에 빼준다. 그리고 \(B\)도 \(C\)에 빼준다. 그리고 \(C\)에 있는걸 전부 \(A\)의 수 하나에 몰아준다. 이 때 총합은 \(S_A+S_B-S_C\)가 된다.

\(2.\) 하나만 남길 가방(\(A\))과 나머지 가방(\(B,C\))을 정한다. 그리고 \(A\)는 하나만 남기고 전부를 \(B,C\) 중 가장 작은 원소에 빼준다. 그리고 \(B\)에서 가장 작은 원소를 제외한 나머지를 전부 \(C\)에서 가장 작은 원소에 빼준다. \(C\)에서 가장 작은 원소를 제외한 나머지를 \(B\)에서 가장 작은 원소에 빼준다. 그리고 그 두 원소를 \(A\)의 하나 남은 원소에 빼주면 된다. 이 때 총합은 \(S_A+S_B+S_C-2\text{min}(B)-2\text{min}(C)\)가 된다.

 

D. Sum of Paths

꽤 간단한 경우의 수 문제다.

\(D_{i,j}\)를 \(j\)번 이동해서 \(i\)번 칸에 도달할 수 있는 횟수라고 하자.
끝 부분과 초기값을 잘 처리해주면 \(D_{i,j}=D_{i-1,j-1}+D_{i+1,j-1}\)로 \(D_{n,k}\)까지 채울 수 있다.

\(j\)번 만에 \(i\)번 칸에 도착하는 경우의 수와 \(i\)번 칸에서 출발해 \(j\)번 움직이는 경우의 수가 같기 때문에, \(\sum^k_{j=0}D_{i,j}\times D_{i,k-j}\)가 모든 경로에서 \(i\)가 등장하는 횟수가 된다.

이 총합을 미리 계산해두고 쿼리마다 합을 계산해주면 된다. \(O(nk+q)\)

 

E. Distinctive Roots in a Tree

놀랍게도 BOJ에 있던 문제라고 한다.

일단 아무 정점이나 루트로 삼아 트리를 만든다.
이 때 DFS 과정에서 두 가지 경우가 생긴다.

\(1.\) 현재 정점과 같은 번호의 자식 노드가 있음.
\(2.\) 현재 노드와 같은 번호가 다른 서브트리에 있음.

\(1\)번 경우엔 같은 번호인 자식을 향하는 서브트리를 제외한 모든 노드 + 같은 번호인 자식의 서브트리가 답이 될 수 없다.

\(2\)번 경우엔 단순히 번호가 같은 노드의 서브트리가 답이 될 수 없다.

이 둘을 잘 처리해야되는데, 나는 각 노드마다 자신의 서브트리에서 등장한 번호들을 저장해두고 이를 Small to Large 기법으로 합쳐가면서 처리했다.
일단, 단순히 자신의 서브트리를 답에서 제외시키면 되는 경우엔 노드에 가중치를 매우 크게 준다.
그리고 \(1\)번 경우에 자식으로 향하는 서브트리는 제외시켜야되는 경우는 루트노드에 가중치를 주고 그만큼을 자식으로 향하는 노드에 빼준다.
그리고 다시 DFS를 하면서 현재 노드까지 누적 가중치를 확인해서 \(0\)보다 크다면 답에서 제외되는 것이다.

설명이 잘 안 되기는 하는데, 아무튼 구현에는 여러가지 방법이 있을 것 같다. 내 방법은 \(O(n\log^2{n})\)정도 된다.

---

일단 ABC 전부 실수가 나오기 좋은 문제여서 안 틀리는게 매우 큰 이점이 되는 대회였다. 나는 D랑 E에서 한 번씩 틀리기는 했지만 ABCD까지 다 빠른 편으로 풀어서 등수가 어마어마하게 올랐다.
저번 코포에서 100점 넘게 떨어졌지만 이번에 Div.2 214점 올라서 최고레이팅 찍었다. 매번 이렇게만 되면 좋겠다.