Codeforces Round #854 by cybercats (Div. 1 + Div. 2)

Dashboard - Codeforces Round #854 by cybercats (Div. 1 + Div. 2) - Codeforces

 

Rated Round를 오랜만에 하는 거라 걱정했는데, 다행히 선방했다.

 

Prob. A

지문이 도저히 해석이 안 돼서 예제 보고 찍어 맞췄다. 풀이는 그냥 구현이다.

 

Prob. B

처음에 1이 존재하면서 1이 아닌 수도 존재한다면 불가능하고, 나머지 경우에는 가장 큰 수를 가장 작은 수로 나누는 것을 반복하면 언젠가 같아진다.

 

Prob. C

C 주제에 더럽게 까다롭다. 일단 정렬하고 앞에서부터 볼 때 같은 문자가 두 개 있다면 양 끝에 붙여주는 게 최적이다. 그렇지 않고 가장 작은 문자가 한 개 존재한다면 두 가지 경우로 나눠야 한다. 이 한 개 남은 문자를 제외한 문자들이 모두 같다면 한 개 짜리를 중앙에 배치하면 되고, 그렇지 않다면 하나 짜리를 제외하고 사전순으로 배치한 다음 마지막에 하나 짜리를 붙여주는 게 최적이다.

 

Prob. D1

$dp[i][j]\, (i > j) :$ $i$번까지 돌리고 나서 다른 쪽에서 가장 최근에 돌린 것이 $j$번일 때 최소 비용

을 $O(N^2)$에 어렵지 않게 전이할 수 있다.

 

Prob. D2

일단 인접한 것이 동일한 것들은 모두 hot을 써서 없애주자. 그리고 cold만 쓸 때의 누적합을 전처리하자.

$dp1[i] :$ $i$번을 hot으로 돌렸을 때 최소 비용 (불가능하면 INF)   /   $dp2[i] :$ $i$번을 cold로 돌렸을 때 최소 비용   이라 하면

$dp1[i] = min(dp1[p[a[i]] + 1], dp2[p[a[i]] + 1]) + sum[i - 1] - sum[p[a[i]] + 1] + hot[a[i]]$,

$dp2[i] = min(dp1[i - 1], dp2[i - 1]) + cold[a[i]]$

가 성립하고, 이는 $O(N)$에 전이할 수 있다.

 

Prob. E

일단 완성된 모양에서 같은 줄(행 또는 열)의 채워진 칸들은 모두 연속해야 한다. 이 조건을 만족하도록 칸을 모두 채워주는 것은 dfs로 구현할 수 있다. 다 채운 후 컴포넌트가 1개라면 그냥 끝난 것이고, 그렇지 않다면 조금 더 생각을 해야 한다.

두 컴포넌트는 일단 strict하게 분리되어 있다. 둘의 위치 관계는 대각선 방향에 따라 총 4가지가 가능하고, 서로와 가까운 방향의 모퉁이를 직사각형마냥 꽉 채워줘야 한다. 이는 직사각형의 꼭짓점을 찾고 위의 dfs를 재활용하면 된다. 그리고 두 꼭짓점을 선분 두 개로 이어주기만 하면 된다. 실전에서는 내 dfs를 조금 착각해서 훨씬 많은 케이스를 고려하느라 고생했다.