Editorial

C

문제 요약:

2*n 격자판이 있는데, 로봇은 처음 (1,1)에 있고, 상하좌우 1칸으로만 움직이고, 밖으로 나갈 수 없다.

중복 없이 모든 칸을 방문해야 하는데, 칸에 적힌 숫자만큼 시간이 돼야 칸이 열린다.

몇초만에 다 방문할 수 있는가?

문제 해설:

어떤 칸$(i,j)$(0-indexed)에서

$\downarrow, \rightarrow, \uparrow, \rightarrow, \ldots$ 식으로 빈 칸 없이 채우며 맨 끝까지 가는 것을 snake,

맨 끝$(i,n-1)$까지 갔다가 $(1-i,n-1)$을 거쳐 밑$(1-i,j)$으로 돌아오는 것을 hook라고 하자.

중간에 방문하지 않은 칸이 존재하면 안 되므로, snake를 하면서 중간에 hook를 하는 것들 중에 답이 있을 것이다.

hook를 빨리 하기 위해 미리 $(i,j)$칸에서 hook을 시작하기 위한 시간을 계산하는 배열 d를 미리 계산한다.

$d_{i,j}= (i,j)$칸에서 시작해서 끝까지 갔다가 $(1-i,j)$칸으로 돌아올 때 기다리는 칸이 없게 가장 빨리 출발할 수 있는 시간이라고 하면,

$d_{i,j}= max(d_{i,j+1}-1\ , a_{i,j}\ ,a_{1-i,j}\ -(2* (n-j)-1))$이다.

$d_{i,j+1}$은 오른쪽 한 칸 뒤$(i,j+1)$에서 hook할 때의 값을 나타내므로, 앞에 한 칸$(i,j)$이 생기므로 1초 빨리 출발하는 것과 마찬가지 이므로 $d_{i,j+1}-1$과,

$a_{i,j}$는 지금 칸,

$a_{1-i,j}$는 지금 칸의 위/아래 칸인데, 끝까지 갔다가 $(n-j-1)$ 밑으로 내려가고 (1), 또 돌아오면 $(n-j-1)$ 이므로 모두 합하면 $a_{1-i,j}\ -(2* (n-j)-1)$이 된다.

따라서 hook을 하기 위한 계산을 하고,

snake를 하는 것을 반복해 가면서 멈춘 칸에서 hook을 하는 경우를 계산하고, 최솟값에 $2*n-1$(이동 거리)를 더하면 답이 된다.

의견: 이렇게 해도 되는데, 어떤 시간을 기준으로 되고 안 되고가 구분되므로 이분 탐색으로 했어도 가능했다는 사실을 알았다.

D

summary:

0에서 시작해서, $k$의 배수만큼 더하고, 그 다음엔 $k+1, k+2, \dots$ 만큼 더해 나간다.

1~$n$까지 각각의 수들에 도달하는 경우의 수를 세는 문제이다.

solution:

당연히 dp이고,

$d(s,i)= s번 연산을 거쳐서 i를 만드는 경우의 수$ 라고 할 때

$d(s,i)=\underset{가능한 j}{\sum} d(s-1,i-j*(k+s-1))$이라고 할 수 있다.

그런데 i는 $\frac{ s(2k+s-1) }{2}$를 넘을 수 없으므로(각 연산마다 더해야 하는 최소의 k가 존재하므로)

계산하는 전체 시간 복잡도는 $O(n \sqrt{n})$이 된다.

그런데 상태를 전부 저장하면 메모리 가 부족하다.

$d(s,i)$를 구하려면 이전 상태만 보면 되므로 d배열을 1차원으로 유지해서 계산하고 갱신하고를 반복해서 구한다.

더 자세하게는 $d(s,i)=d(s-1,i-k)+d(s-1,i-2k)+d(s-1,i-3k)+\dots$이고 (k=현재 k의 값),

$i-k, i-2k, i-3k, \dots$들을 k로 나눈 나머지는 모두 같다.

따라서 현재 인덱스를 i라고 할 때, sum[i 이전의 수들을 k로 나눈 나머지]에 d[i 이전의 수] (이전 스텝의 것으로 생각)들을 모두 더하고

ans에 d[i]를 매번 더해주면 된다.

for (int mn = 0; mn+k<= n; mn += k++) {
    vl sum(n + 1);
    for (int i = mn; i <= n; i++) {
        int t = d[i];
        d[i] = sum[i % k]; //자기 이전까지
        (sum[i % k] +=t) %= mod;
        (ans[i] +=d[i]) %= mod;
        
    }
}

opinion:

실제로 생각했어야 하는 것은 메모리 문제를 어떻게 해결할지인데 시간 초과가 난다고 생각했다.