Educational Codeforces Round 181 (Rated for Div. 2)

실수 없이 4솔한 것에 만족한다. 특히 D를 생각보다 빨리 풀어서 4솔 상위권에 올 수 있었던 것 같다. E, F는 패스..

A — 00:06 AC#

T가 F, N보다 앞에 오도록 재구성하면 FFT, NTT를 포함할 수 없음이 자명하다.

B — 00:08 AC#

한 개의 이동방법? 만으로 로봇을 이동시키기 위해선 그냥 $(a, b)$만큼 움직여도 되지만, 이동거리 제한 $k$가 있기 때문에 가능한 $k$보다 작게 하려면 $a$, $b$의 최대공약수로 $a$, $b$를 각각 나눈 값으로 움직여야 할 것이다. 예를 들어 $a, b = 6, 9$이고 $k = 4$라면 6과 9의 최대공약수인 3으로 $a$, $b$를 나눠 $(2, 3)$을 움직임으로 정하는 것이다. 이렇게 정해진 $(dx, dy)$에 대해 $\max(dx, dy) \le k$라면 답은 1이고, 그렇지 않다면 $(0, 1)$과 $(1, 0)$을 사용한 2가 답이다.

C — 00:11 AC#

한 자리 소인수는 2,3,5,7이 전부이다. 포함배제로 1부터 $n$까지 중에 좋은 숫자의 개수를 구하는 함수를 정의하고, 누적합 구하듯이 구간에서의 좋은 숫자의 개수를 구하면 된다.

D — 00:52 AC#

공식 에디토리얼에 나온 2번째 DP 방법과 거의 비슷하게 풀었다. $dp[x]$를 1번 셀부터 $x$번 셀까지 조건을 만족하고, 이후에는 아무 선분도 없는 확률로 정의하자. 그럼 $dp[x+1]$은, $x + 1$번 셀에서 끝나는 모든 선분의 시작점 셀 $l$에 대하여 $dp[l-1] \times p / (q - p)$의 합으로 정의할 수 있다. 여기서 $dp[l-1]$은 $l - 1$번 셀까지 조건을 만족하고, 이후에는 아무 선분도 없는 확률이기 때문에 $x + 1$번 셀에서 끝나는 선분도 존재하지 않는다. 즉, $x + 1$번 셀에서 끝나는 선분이 존재하지 않을 확률을 가지고 있다고 할 수 있으며, 그 값은 $(q - p) / q$이다. 따라서 여기에 $p / (q - p)$를 곱해주면 $p / q$가 되어 선분이 존재할 확률만 남게 된다. 즉 $l - 1$번 셀까지 조건을 만족하면서, 동시에 $x + 1$번 셀까지도 조건에 맞게 덮는 확률을 얻을 수 있다. 이렇게 하면 $dp[m]$은 1번 셀부터 $m$번 셀까지 조건을 만족하는 확률을 얻는 것처럼 보이지만, dp 전이 과정에서 각 선분이 존재한다는 가정 하에 확률을 구했기 때문에 최종적으로 $dp[m]$이 문제의 답을 내놓는 것은 아니다. 여기다 모든 선분이 독립적으로 존재하지 않을 수 있는 가능성을 곱해야 문제의 답을 구할 수 있고, 그렇기 위해선 추가로 각 선분이 존재하지 않을 확률인 $(q - p) / q$를 모두 곱한 값을 곱해주면 된다.

dp 전이할 때 모듈러를 써야 하는데, 나눗셈에서는 모듈러가 성립하지 않기 때문에 페르마의 소정리를 써서 숫자를 줄여주면 된다.