2021-09-10 Problem Solving

11385. 씽크스몰

단순히 다항식의 곱셈을 FFT로 수행하면 해결할 수 있어 보인다. 하지만, 입력되는 수의 범위를 살펴보면, long double을 써도 맞기 쉽지 않음을 알 수 있다. 나는 조금 더 안전 빵으로, 소수 두 개를 이용해 NTT를 두 번 한 후, CRT를 이용해 계수들을 복원하여 문제를 해결했다.

19265. Is it a p-drome?

모든 값을 0-based index로 생각하자.

 

어떤 문자열이 $p$-drome 이라면, $p$를 적용한 결과물과 해당 문자열의 라빈 핑거프린트 해시 값이 같을 것이다. 고로, $i$에서 시작하는 길이 $m$인 문자열을 본다고 할 때, 원래 문자열의 해시 값은 $\sum_{j=0}^{m-1} a_{i+j} x^j$ 이 될 것이고, $p$를 적용한 결과물의 해시 값은 $\sum_{j=0}^{m-1} a_{i+j} x^{p_j}$가 될 것이다. 이들을 빼주면, $\sum_{j=0}^{m-1} a_{i+j} (x^{p_j} - x_j)$가 될 것이고, 이것이 0인지 판별하는 것이 우리가 풀고 싶은 문제이다. 그런데, 편의상 $b_{i} = a_{n-1-i}$로 놓으면, 각 $i$에 대해 우리는 $\sum b_{n-i-j} (x^{p_j} - x^j) = 0$ 인지 판별하면 되고, 이는 FFT를 이용하여 할 수 있다.

13941. Kronican

비트로 문제 상황을 나타낼 수 있다. (물이 차 있는 컵에 대응되는 비트만 켜자.) 그러면, $D[x]$를 $x$에 켜진 비트에만 물이 담겨있을 때, 문제의 답으로 정의할 수 있다. 다른 컵으로 물을 옮길 때, 이미 물이 차 있는 컵으로 물을 옮기는 것이 최적임을 쉽게 알 수 있고, 이를 이용하면 상태전이는 명백하다.

6049. Triangle Counting

원점을 중심으로 점들을 각도 순 정렬하자. 원점을 포함하지 않는 삼각형을 생각해보면, 원점을 지나는 직선이 존재해 삼각형이 한 쪽 반 평면에만 존재하게 된다. 따라서, 반시계 방향으로 점들을 순회하면서, 점 $p$를 기준으로 본다고 할 때, $p$를 오른쪽 끝 정점으로 하는 삼각형의 수를 잘 세어주면 된다.