ABC335 F - Hop Sugoroku

Competitive Programming C++

2024-01-11

문제 링크
https://atcoder.jp/contests/abc335/tasks/abc335_f

원문 링크
https://atcoder.jp/contests/abc335/editorial/9038

검게 칠해진 칸의 집합과 말의 진행 방법은 대응하므로, 가능한 말의 진행 방법의 수를 세면 됩니다.

이를 바탕으로, 이 문제의 계산량을 신경쓰지 않고 생각해봅시다. 이하와 같이 DP를 구성할 수 있습니다.

dp = {1, 0, ..., 0};
for (i = 1; i <= N; i++)
    for (j = i + A[i]; j <= N; j++)
        dp[j] += dp[i];
print(sum(dp));

\(A_i\)가 큰 경우에는 \(j\)의 반복문이 도는 횟수가 적어 이런 방법을 쓸 수 있을 것 같지만, \(A_i=(1,1,…,1)\)같은 케이스에서는 \(O(N^2)\)의 시간복잡도를 필요로 하기에, 이대로는 통과할 수 없습니다.

그렇다면, \(A_i\)가 작은 경우에 대해 \(dp\)배열을 빠르게 처리하는 방법을 생각해봅시다.

\(i < j\)일 때, \(dp[i]\)에서 \(dp[j]\)로의 전이를 할 수 있는 조건은 \(j - i\)가 \(A_i\)의 배수일 것(즉, \(i\)를 \(A_i\)로 나눈 나머지가 일치할 것)입니다.

이것으로부터 \(dp2[d][r]={d로\ 나눈\ 나머지가\ r인\ 집합}\)과 같이 배열을 만들면 문제를 풀 수 있을 것 같습니다.(실제로, 이 풀이로 AC를 받을 수 있습니다.)

그럼, \(A_i\)가 작다, 크다는 어떻게 판별할까요?
예를 들어, \(A_i \leq b\)가 \(A_i\)가 작은가 큰가의 경계라고 해 봅시다.

가 됩니다. \(O(Nb + N \times {N \over b})\)의 평가를 가능한 좋게 하기 위해서는 \(b = \sqrt{N}\)으로 하면 좋습니다.(산술-기하 평균의 관계에 따라서)

구현상으로는 \(b\)를 \(\sqrt{\max N}\)근처의 적당한 정수로 해도 상관없습니다. 또한, 각 부분의 정수 배에 대해서는 최적인 \(b\)가 \(\sqrt{N}\)으로부터 조금 먼 경우도 있기에, 상황에 따라 여러 가지를 시험해 보면 됩니다.

이렇게 문제를 \(\sqrt{N}\)을 경계로 구별지어 \(\sqrt{N}\)개의 문제로 분할해 빠르게 해결하는 테크닉을 제곱근 분할법이라고 부르기도 합니다.

루트질(제곱근 분할법)까지 동원해야 하는게 F구나…
E 보는게 고작인 나는 더 분발해야겠다.

« PREV NEXT »