AtCoder Regular Contest 150

문제풀기

lml 2022. 10. 10. 16:17

D를 정말 다 풀었는데 마음이 너무 급해서 AC를 받지 못했다.

A. Continuous 1

앳코더에서 왜 이딴 문제를 냈지? 라는 생각이 잠시 들었지만 사실 그리 복잡한 문제는 아니다.

어떤 지점 i에 대해서 k개의 연속한 1을 만들 수 있는 조건은

1) i부터 i + k - 1까지 0이 없고

2) i이전에 1이 없고

3) i + k - 1 이후에 1이 없으면 된다.

따라서 이런 포지션들의 개수를 모두 세주었을 때 1개면 Yes 아니라면 No를 출력

B. Make Divisible

(A + X) * k = (B + Y)를 만족한다.

k = 1, 2, ... sqrt(1e9)까지 전부 해보고

(B + Y) / k = 1, 2, ... sqrt(1e9)을 전부해보면 된다.

복잡도는 T * sqrt(1e9)

C. Path and Subsequence

나의 편의를 위해 0-index

dp[i] = j : i번지점에 도달하였을 때 B0, B1... B_{x - 1}을 무조건 거치도록 하는 x의 최댓값이 j이다.

그렇다면 p -> q라는 간선이 존재한다면 dp[q] = min(dp[q], dp[p] + (A[q] == B[dp[p]]))가 된다.

따라서 다익스트라를 이용하여 각 노드에 대한 dp값의 최솟값을 구할 수 있다.

dp[n - 1]이 정확히 k이 되어야만 문제 조건을 만족한다.

D. Removing Gacha

f(i) = (white node가 i개 있는 상태에서 i - 1개 있는 상태로 넘어갈 때 필요한 operation의 기댓값) 이라 하자.

Ans = f(n) + f(n - 1) + f(n - 2) + ... + f(1)이 된다.

g(i) = (white node가 i개 일때 bad node의 개수의 기댓값)이라면 f(i) = g(i) / i이다.

따라서 sum(g(i) / i)만 구해주면 된다.

이때 g(i) = 각 노드에 대해 sum ( C(n - depth - 1, i - 1) * (subtree의 노드의 개수) / C(n, i) )가 된다.

왜냐하면 특정 노드가 자신의 subtree를 전부 bad node로 만드는 white node인 경우의 수가 C(n - up - 1, i - 1)이기 때문.

각 노드에 대해서 이제 sum{i = 1~n} C(n - depth - 1, i - 1) * (subtree의 노드의 개수) / C(n, i))의 값을 구해주면 된다.

식정리를 잘 해보면 각 노드에 대해서 1 / (depth + 1) * (subtree의 노드의 개수)의 합 임을 알 수 있다.

식정리의 결과가 워낙 간단해서 왜 이런 1 / (depth + 1)이라는 결과가 도출되었는지 생각해보았다.

claim) h(i) = (한 원소가 paint되는 횟수의 기댓값) = 1/1 + 1/2 + ... + 1/(depth + 1) 이다

1) 한 원소가 paint될 때, 자신의 ancestor이 아닌 원소들은 무시하여도 된다.

-> 자기 자신을 기준으로 외부의 노드가 색칠된다고 good이 되지도 않으며, 자신이 paint되는 것도 아니기에 h(i)는 그대로.

2) 자기 자신과 ancestor들만을 고려할 때, 모두가 색칠될 때까지 bad node이기에 good node들이 색칠된다해도 된다.

-> good node들이 repaint된다고 가정하더라도 h(i)에 어떠한 영향도 주지 않고, 상황도 변하지 않기에 상관이 없다.

따라서 위의 두 가지 아이디어를 고려한다면

n개의 원소들에 대해서 모든 원소들이 한 번씩 골라질 때까지 필요한 paint의 횟수를 구하고 이를 n으로 나누면 h(i)이다.

x개가 paint된 상태에서 x + 1개가 paint된 상태로 넘어가기 위해 필요한 paint의 횟수는 n / x이다.

따라서 h(i) = (n / 1 + n / 2 + ... n / n) / n = 1/1 + 1/2 + ... + 1/n이다. (n = depth + 1)