CodeForces Educational Round 175

https://codeforces.com/contest/2070
 

 
Performance Rating : 2300
 
A
$0$이상 $n$이하의 수 중 나머지가 0, 1, 2인 수의 개수를 찾는 문제였다. $(n/15)*3+\mathrm{min}(n\%15+1,3)$을 출력해 주면 된다.
 
B
$x$에서 시작하여 시뮬레이션을 해서 0에서 만나면 끝내주고 0과 만나지 않는다면 0을 출력해 주고 끝낸다. 0에서 시작하는 것으로 시뮬레이션을 다시 해줘야 하는데 이후 0에서 0과 만나기까지 이동한 횟수를 주기로 반복되므로 이를 바탕으로 계산해 주면 되고 안 만나면 그대로 끝내주면 된다. 여기서 0과 만나면 남은 횟수를 주기로 나누고 더해주고 반복문을 종료해주어야 하는데 종료를 안 했다가 WA를 한번 받았다.
 
C
처음에 문제를 잘못 읽었다. 페널티는 색이 안 맞는 노드의 페널티 중 최댓값인데 합이라고 생각하고 문제를 풀기 시작했다. 세 번째 예제의 정답이 이해가 가지 않아 오랜 시간을 고민하다가 문제를 다시 읽고 문제를 잘못 읽었다는 것을 알게 되었다. 풀이는 우선 R과 B가 연속하는 구간으로 쪼갤 생각을 했다. R과 B가 연속하는 구간으로 쪼개고 각 구간에서 페널티의 최댓값을 저장해 두었다. 연속한 B구간의 개수를 $cnt$에 저장해 놓으면 정확히 $cnt-k$개의 구간을 일치시킬 수 없다고 생각하여 저장해둔 페널티 중 $cnt-k$번째 값을 출력하는 풀이를 만들었다. 하지만 색깔이 맞지 않는 $cnt-k$개의 구간 중 연속하는 구간이 있으면 안된다는 것을 예제를 통해 알게 됐다. 이를 해결하기 위해 구간의 페널티와 인덱스를 묶어 $pq$에 넣어놓고 하나씩 뽑으면서 답을 구할 생각을 했다. $pq$에서 나온 인덱스를 바탕으로 $len$배열에 연속한 구간의 개수를 양끝에 저장해놓으면 연속한 구간의 개수를 통해 고를 수 있는 구간의 개수를 계산해 나갈 수 있겠다는 생각이 들었다. 구간의 개수를 세주면서 $cnt-k$개 이상이 될 때까지 반복하여 답을 구했다. 아무리 생각해도 내 풀이가 정해가 아닐 것 같다는 생각이 들어 jiangly님과 ksun48님의 코드를 보았다. R과 B가 연속한 것을 묶는 것이 아니라 앞뒤에 R을 하나씩 추가하고 R과 B의 경계가 $2k$개 이하가 되어야 한다는 것을 바탕으로 푼 것을 확인했다.
 
D
풀이를 생각하기 전에 각 노드의 깊이를 구해주는 dfs함수부터 만들고 시작했다. 그리고 dp배열에 각 노드에서 시작해서 나올 수 있는 수열의 개수를 저장해 놓을 생각을 했다. 여기서 문제는 dp배열을 채울 때 자신의 자식이 아닌 노드들을 봐주어야 하기 때문에 시간복잡도가 최악의 경우 $O(n^2)$이 될 수 있다는 것이었다. 이를 해결하기 위해 깊이가 $d$인 모든 노드들의 dp값의 합을 저장해 놓는 방법을 생각했다. 깊이가 $d$인 어떤 노드의 dp값을 구할 때 자신의 자식이 아닌 모든 노드들을 보는 것이 아니라 미리 구해놓은 깊이가 $(d+1)$인 모든 노드의 dp값의 합에서 자신의 자식 노드들의 dp값을 빼주면 각 노드별로 자신의 자식 노드만 보면 되기 때문에 $O(n)$에 처리가 가능할 것이라고 생각했다. dfs를 할 때 깊이별로 노드들을 나누어놓고 깊이가 깊은 곳부터 dp값을 채워나갔고 답은 1에 깊이가 2인 모든 노드에서의 dp값을 더하여 구하였다. 빼는 연산이 있기 때문에 답이 음수가 나오지 않도록 유의했다.
 
E
첫턴인 사람이 이기려면 0의 개수가 1의 개수보다 많아야 한다는 것을 먼저 생각했다. 0의 개수가 1의 개수보다 많으면 연속한 0이 무조건 존재하므로 0과 1이 놓인 순서는 크게 중요하지 않아 지고 후턴인 사람은 무조건 0 하나 1 하나를 없애는 것이 최선이라는 것을 생각했다. 0과 1이 놓은 순서가 상관이 없으므로 1의 개수에 따라 첫 턴인 사람이 이기는 0의 개수에 대한 규칙을 찾아보고자 했다. 1의 개수가 $x$개라면 0이 $3x-1$개이거나 $3x+2$개 이상이면 첫 턴인 사람이 이긴다. 1 하나에 0 3개가 대응되는 것을 보고 0에 $1$, 1에 $-3$을 대응시킬 생각을 해봤다. 이렇게 대응시키면 누적합이 -1이거나 2 이상인 연속구간의 개수를 찾는 문제로 바뀐다. $i$보다 작은 인덱스에서 시작해서 $i$에서 끝나는 모든 연속구간을 한 번에 처리할 생각을 해보았다. $(i-1)$에서 끝나는 모든 연속구간의 부분합을 활용하면 $i$에서 끝나는 모든 연속구간도 처리해 줄 수 있는데 이는 펜윅트리를 사용하여 처리해 주었다.
 
F
각 친구가 좋아하는 피자를 비트에 대응시켜 놓으면 두 친구를 골랐을 때 먹는 피자는 $x|y$, 둘 다 좋아하는 피자는 $x\&y$로 표시할 수 있겠다는 생각이 들었다. 하지만 시간복잡도를 $O(m^2)$미만으로 줄일 방법은 도저히 생각나지 않았고 못 풀었다.