Educational Codeforces Round 176 (Div. 2)

문제풀이

A. FizzBuzz Remixed

$\mod{3}$과 $\mod{5}$에서 합동인 어떤 $i$가 구간 $[0,N]$에 몇개 존재하는지에 대한 문제이다. 그런 $i$는 $\mod15$에서 주기성이 보인 다는 점을 활용하여 답을 구할 수 있다.

B. Robot Program

우선 주어진 $s$를 읽으면서 원점 $0$에 도달할 수 있는지 체크한다. 도달할 수 없다면 답은 그대로 $0$이 되고, 도달할 수 있다면 원점 $0$에서 시작했을때 $s$를 다시 읽으면서 원점 $0$에 다시 도착할 수 있는지, 있다면 그 주기가 몇이 되는지를 확인한다. 다시 원점 $0$에 도착할 수 없다면 최초 원점 방문횟수만 친 $1$을, 도착할 수 있다면 남은 $k$를 사용하여 최소 도착 주기를 최대로 반복하면 정답니다.

• 주기성을 최대한 사용하고, 남은 구간에 대해서는 시뮬레이션을 돌리는 부분에 있어서 A번과 일관된 테마를 가지고 있다는 인상을 풍긴다.

C. Limited Repainting

최대패널티를 몇점을 받을지 고정된 상황을 생각해보자. 받는 패널티 이하의 칸들은 어떤칸으로 칠해져도 상관없다. 문제의 첫번째 예시를 살펴보자:

여기서 5점의 패널티를 감수한다고 생각하면, 첫번째 원소와 세번째 원소는 어떤 색으로 칠해져도 상관없기 때문에, 다음과 같이 문제가 축소된다:

이제 남은 칸에 대해서는 모두 정확히 원하는 색을 칠해줘야 하기 때문에, $B$의 개수가 $k$의 개수 이하인지 체크하는 문제로 바뀐다. 가능한 모든 “최대패널티”에 대해서 위와 같은 문제를 풀면 되는데, 패널티를 내림차순으로 정렬하면서 문자열을 구성하면 된다. 첫번째 예시는 다음과 같은 순으로 문자열이 구성될 것이다: $B\rarr RR \rarr RBR \rarr BRBR$.

다만 문자열이 중간에 삽입되는 경우도 존재하는데, map 자료구조 등을 사용해서 해결할 수 있다. 문자열을 계속 구성하면서, 연속된 $B$구간이 몇개인지 세주면 된다. $B$구간이 늘어나는 경우는 다음과 같이 2가지 경우가 있다:

1. 새로운 $B$구간이 생성되는 경우 ($A\rarr AB$)
2. 기존의 $B$구간이 $A$구간으로 분할되는 경우 ($BB \rarr BAB$)

따라서 전체 시간복잡도는 $\mathcal{O}(NlogN)$.

D. Tree Jumps

루트의 자식의 경우를 제외한다면, 정점 $x$로 진행하기 위해서는 자신의 부모와 같은 깊이에 있는, 부모를 제외한 모든 정점을 통해야 한다. 정점 $x$를 끝으로 하는 경로의 경우의 수를 $f(x)$라고 하고 정점의 깊이를 $d_x$, $x$의 부모를 $par_x$라고 하자. 루트의 자식 케이스를 제외한다면 $f(x)=\sum_{\{ prev:d_{prev}=d_x-1 \}}f(prev) -f(par_x)$ 라고 정리할 수 있다. 따라서 깊이별 $f$합을 따로 저장해놓는다면 답을 쉽게 구할 수 있다. BFS를 사용하면 깊이가 낮은 정점부터 $f$를 구할 수 있으므로 간편하다.

E. Game with Binary String

upsolved

가장 중요한 관찰은 $0$과 $1$의 배치는 상관없다는 것이다. 선택된 부분문자열이 원순열처럼 이어져있는 구조라서, 비둘기집의 원리에 의해서 남아있는 숫자의 갯수 조건만 맞는다면 항상 원하는 부분문자열을 제거할 수 있기 때문이다.

선공은 항상 $0$을 두개 제외하고, 후공은 최소 1개의 $1$, 가능하다면 $0$도 제외시키는게 선공의 선택지를 줄이는 최적의 수라는 관찰이 있다면 선공이 이기는 경우를 떠올려볼 수 있다. 0의 개수를 $cnt_0$, 1의 개수를 $cnt_1$이라고 하자. 선공이 이기는 경우는 다음 두가지로 정리된다:

1. $cnt_0-3\cdot cnt_1\geq2$ → 선후공이 턴을 계속 진행했는데, 결국 $0$만 남아 선공이 턴을 진행하고 후공은 가능한 행동이 없는 경우이다.
2. $cnt_0-3\cdot cnt_1 =-1$ → 선후공이 턴을 계속 진행했는데, 후공턴에는 $1$개의 $1$만 남아 진행이 불가능한 경우이다.

이제 각 범위 선택마다 선공이 이기는 경우의 수를 구해야 하는데, 이는 범위 $[1,N]$의 모든 $i$에 대해서 $[1,i]$의 $cnt_0-3\cdot cnt_1$ 값의 등장 횟수를 저장하는 세그먼트 트리를 사용하면 해결할 수 있다.

총평

무지하게 독한 스피드포스였다. ICPC룰인데, 4솔 퍼포가 민트~오렌지에 걸쳐있는 것을 보고 경악하였다. B 문제를 잘못 이해하고, C는 발상이 너무 느렸어서 퍼포가 많이 깎였다. 1900의 꿈은 쉽지않은 것 같다…

E는 재밌었다. $0$과 $1$의 배치는 아무래도 상관없다는 결론까지는 도달했으나, D를 풀고나니 30분밖에 없었어서 아쉬움이 남는다. (뒤에 세그먼트 트리 응용이 조금 복잡했어서 1시간 줬어도 힘들긴 했을듯 함)