Codeforces Round #848 (Div. 2)

Dashboard - Codeforces Round #848 (Div. 2) - Codeforces

 

복귀 성공

 

Prob. A

대충 다 해보면 된다.

 

Prob. B

초기에 조건을 만족하는지 확인하고, 그렇지 않다면 인접한 거끼리 위치를 바꾸거나 멀리 보내보면 된다.

 

Prob. C

대충 비트마스크 써서 다 해보면 된다. 이런 걸 굳이 냈어야 싶지만..

정확히 k개 쓸 때만 확인하는 게 정해인 듯 한데, 나는 k개 이하일 때 다 확인해보고 통과했다.

 

Prob. D

다른 개수에 대한 기댓값 DP식을 세우고, 조금 변형하면 $dp_{i+1} = p \times dp_{i} + q \times dp_{i-1}$ 꼴로 나타낼 수 있다. 이제 $dp_0$과 $dp_1$만 찾으면 되는데, $dp_0$은 자명하게 $0$이고 $dp_1$은 $n=3$까지 손으로 계산해보면 $2^n-1$임을 추측할 수 있다.

 

Prob. F

열심히 생각해보면 해야 하는 것은 명확하다. 최종적으로 1번 노드에 최대한 큰 값을 곱해야 하고, 그러기 위해선 하위 노드들이 모두 그 값의 배수여야 하고, 그걸 맞추기 위해서 하위 노드에서도 적당한 값을 곱해야 하고... 의 반복이다. 나는 이걸 dfs로 '잘' 구현하려다 망했다. 정해는 dp를 이용한다.