Codeforces Round #642 (Div. 3)

Codeforces Round #642 (Div. 3)에 부계정으로 참가했다.

 

 

저번 Div. 4를 제외하고 첫 올솔브다 ㅎㅎ. 사실 Div. 2 올솔은 능력 밖이기도 하고.

 

A. Most Unstable Array

$N=1$이면 0 $N=2$이면 M, 아니면 2M 이다.

 

B. Two Arrays And Swaps

A에서 제일 작은것과 B에서 제일 큰것 swap을 반복해주면 된다. 왜 $N \le 30$?

 

C. Board Moves

가운데로 모으는게 최적임을 알 수 있다.

이렇게

$O(N)$ 에 해도 되고, 일반항도 있다 카더라.

 

D. Constructing the Array

{구간의 길이, 구간의 시작점} pair로 우선순위 큐를 관리하면 된다. 길이와 시작점의 대소 우선순위가 다름에 유의하자.

 

E. K-periodic Garland

$dp[i]$ : i번째 전구를 켤 때 (1~i) 전구들을 K-periodic 하게 만들기 위한 최소 비용

이때 $dp[i]$ 는 $dp[i-K]$에서 가져오거나, i번째만 켜고 나머지는 다 끄거나 둘 중 하나다.

이때 어떤 구간에 켜져있는 전구의 개수를 빠르게 구해야 하는데, 이는 prefix sum으로 $O(1)$에 가능하다.

실제 답은 $dp[i]$ + ($[i+1;N]$ 에 켜져있는 전구 개수) 가 됨을 유의하자.

 

F. Decreaseing Heights

$(1,1)$ 에서 $(n,m)$ 으로 가는 경로에서, 적어도 하나의 $a_{i,j}$는 변화시키지 않는게 최적이다. 따라서 모든 $a_{i,j}$에 대해, 해당 값을 고정시킨 후 답을 구하자. $a_{i,j}$를 고정시켰다면, $(x,y)$ 의 값은 $a_{x,y}-a_{i,j}+i-x+j-x$ 가 되어야 한다. 격자점 최단거리와 거의 동일한 $O(nm)$ dp를 통해 고정된 $a_{i,j}$ 에 대해 답을 구할 수 있으므로, 총 $O(n^{2}m^{2})$에 해결할 수 있다.