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) <= 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] * 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 전이할 때 모듈러를 써야하는데, 나눗셈에서는 모듈러가 성립하지 않기 때문에 페르마의 소정리를 써서 숫자를 줄여주면 된다.