SCPC 2차 예선 후기

 

SCPC 2차 예선을 쳤습니다.

 

잘 친건 아니지만 작년보다는 높은 성적이어서 만족스럽습니다. 계속 조금씩 성적이 오르고 있으니 내년에는 본선에 갈 수도 있지 않을까요? 아님망고...

 

까먹기 전에 풀이를 간단하게 남겨봅니다.

 

---

1. 수열 연산

배열에 연속된 구간에 update 쿼리를 통해 값을 1 증가시킬 수 있고, 배열의 모든 수를 $k$ 이상으로 만드는 update 쿼리의 최소 횟수와 그 때의 최소 비용을 구하는 문제입니다. 이 때 쿼리의 비용은 연속된 구간의 길이입니다.

 

잘 생각해보면 update 쿼리의 최소 횟수는 $k$ - 배열의 최솟값이라는 것을 알 수 있습니다. 최솟값을 $k$로 만들어주기 위해서는 $k$ - 최솟값 만큼의 update 쿼리가 필요하고 해당 쿼리를 하는 과정에서 나머지 모든 수를 커버할 수 있기 때문입니다. 이 아이디어에서 시작하면 모든 update 쿼리는 최솟값을 포함해야 하고, 그 과정에서 나머지 수를 최대한 짧은 길이로 포함하면서 update 해주면 된다는 결론에 도달합니다. 따라서 그리디하게 매 update마다 아직 $k$가 되지 않은 가장 왼쪽의 수와 가장 오른쪽의 수를 포함하도록 쿼리를 날리면 됩니다.

 

이는 투포인터를 통해 구현할 수 있습니다. 아직 $k$가 되지 않은 가장 왼쪽 인덱스를 $l$, 가장 오른쪽 인덱스를 $r$, 현재까지의 update 쿼리 수를 $cnt$로 두면 $l$과 $r$이 있을 때 $min(k - l - cnt, k - r - cnt)$만큼의 update 쿼리를 $(l, r)$구간에 날립니다. 이후 $l$과 $r$을 증가/감소시키며 다음 인덱스를 찾으면 됩니다.

 

---

2. 반 협동게임

배열이 하나 주어지고 같은 번호를 가진 인덱스를 짝지어 배열에서 제외할 수 있습니다. 이 경우 $r - l$만큼의 점수를 얻으며 빈 자리는 하나씩 당겨서 채워집니다. 이 연산을 반복하여 가장 큰 점수를 얻으면 됩니다.

 

사실 맞았는데 왜 맞았는지 잘 모릅니다. 이렇게 하면 될 거 같아서 짰더니 맞았습니다.

 

시작 배열 기준으로 가장 점수를 많이 얻을 수 있는 방법으로 짝을 지어준 뒤, 해당 짝들을 얻을 수 있는 점수 기준으로 내림차순 정렬합니다. 그렇게 정렬한 순으로 배열에서 제외해주면 됩니다. 이 때, 앞으로 당겨주는 연산은 $(l, r)$ 구간에서 몇 개의 원소가 제외되었는지 찾는 쿼리로 대신할 수 있고, 이는 세그먼트 트리로 구현할 수 있습니다.

 

나중에 푼 사람들한테 증명을 배워야 할 것 같습니다.

 

---

3. ABC

못 풀었습니다. 머릿속에서 삼각형이 굴러다녀요. 서브테스크도 못 긁은건 조금 아쉬웠습니다.

 

---

4. 직사각형

$n \times n$ 배열에 1부터 $n^2$가 채워져 있을 때, 연속된 수로 이루어진 직사각형은 몇 개인지 찾는 문제입니다. 서브태스크만 긁었습니다.

 

$\mathcal{O}(n^6)$ 풀이는 그냥 하면 됩니다. 모든 직사각형($\mathcal{O}(n^4)$)에 대해 해당 구간의 수가 연속한지 확인($\mathcal{O}(n^2)$)하면 됩니다.

 

$\mathcal{O}(n^4)$ 풀이의 경우 위의 풀이에 누적합을 써서 합을, $\mathcal{O}(1)$ RMQ를 써서 최대최소를 구한 후 연속한지 확인해줬습니다. 2d range minimum query in $\mathcal{O}(1)$의 경우 아래 블로그에 잘 나와있습니다.

 

https://codeforces.com/blog/entry/45485

2D Range Minimum Query in O(1) - Codeforces

 

이렇게 추하게 긁는게 맞는지 모르겠습니다. 하지만 긁었으니 된 거 아닐까요?

 

---

대회 도중에 딴짓도 하긴 했지만 원래 12시간 내내 집중한다는 건 불가능한 일이고 풀 수 있을만한 문제는 다 푼 거 같아서 나름 만족합니다. 더 잘하고 싶기도 한데, 언젠가는 잘하게 되지 않을까요?

 

아무튼 대회 다 쳤으니까 이제 술 마시러 갈거예요. 원래 대회 망하면 술 마시는 거지...