Hello, BOJ 2023!

Hello, BOJ 2023!

서론

처음으로 참가하는 오프라인 대회이다.

 

서울대 처음 가봤는데 별 거 없었다.

 

난이도 조절 대실패

 

대회 당일 기준으로 D5였는데 아쉽게도 P1 키링을 받았다.

올해 UCPC에서는 아마도 D1 키링을 받을 듯 하다.

 

깜빡하고 볼펜을 안 가져왔는데 편의점이 멀리 있어서 뛰어 갔다 왔다.

위치 못 찾아서 기숙사생 붙잡고 여쭤봤는데 친절하게 알려주셨다.

 

대회 결과는 전체 92명 참가자 중 28등으로 수상권에는 들지 못하였다.

 

A - 2023년이 기대되는 이유

1과 0으로만 구성되어 있다면 무수히 많은 m이 존재한다.

그렇지 않다면 + 기호를 넣어서 만들 수 있는 모든 값을 미리 구해두자.

이제 가능한 m에 대하여 계산한 결과값이 존재하는지 확인하면 된다.

2^30 > 1e9이기 때문에 m의 최댓값은 29이다.

노트북 키보드가 익숙하지 않아서 코딩이 오래 걸렸다.

00:11 AC

 

B - 청소

set<ii>에 적절히 넣었다 뺐다 하면서 잘 계산해주면 된다.

마찬가지로 노트북 키보드 이슈 때문에 코딩이 오래 걸렸다.

00:23 AC

 

C - 카드 플러리쉬

이 문제는 섞여 있는 카드를 정렬하는 문제로 변형하여 풀이할 수 있다.

현재 카드 배치를 [x (x + 1) (x + 2) ... (x + k) y ... ] 라고 할 때 (x + k) + 1 != y를 만족하는 k가 존재한다고 가정하자.

이때 찰리어 컷 또는 트리플 컷을 사용하면 x부터 (x + k)까지의 묶음을 유지하면서 (x - 1)과 x를 붙일 수 있다.

 

위의 연산을 최대 (N - 2)번 수행하면 카드 배치는 다음과 같은 형태가 된다.

[x (x + 1) (x + 2) ... (x + N - 1)]

이때 찰리어 컷을 사용하면 정렬이 완료된다.

따라서 최대 (N - 1)번의 연산으로 항상 정렬이 가능하다.

 

01:23 WA

위의 풀이에서 일부 경우를 고려하지 않아 연산 횟수가 N 이상이 되는 경우가 발생하였다.

 

01:51 WA

분명 반례가 없어 보였는데 WA를 받았다.

한참 살펴보다가 도저히 모르겠어서 assert 문을 도배하고 다시 제출하였다.

 

02:00 WA

신기하게도 또 다시 WA를 받았다.

뭔가 이상함을 느끼고 문제를 정독하였는데 알고 보니 문제를 잘못 이해하였다.

섞여 있는 카드를 정렬하는 문제인 줄 알았는데 정렬된 카드를 원하는 순서로 섞는 문제였다.

왠지 예제가 다르게 나왔는데 스페셜 저지가 붙어 있어서 중요하게 생각하지 않았다.

다행히 방법만 적절히 역순으로 출력하면 해결되는 문제였다.

 

02:03 AC

이후 D를 잡았지만 별다른 성과 없이 끝나버렸다.

 

D - 컵 쌓기 (not solved)

다음과 같은 점화식을 세울 수 있다.

dp[i][j] = 전체 j개의 컵 중 i개의 컵을 1층에 쌓는 경우의 수

구체적으로는 다음과 같이 계산할 수 있다.

dp[i][j] = dp[i - k][j - l] * F[k + 2] * dp[k - 1][l - k];

여기서 F[k]는 k번째 피보나치 수를 의미한다(F[1] = F[2] = 1).

 

위의 점화식의 원리를 간단히 살펴보자.

가능한 k와 l에 대하여 전체 l개의 컵 중 k개의 컵을 1층에 쌓고 (k - 1)개의 컵을 2층에 쌓는 묶음을 생각해보자.

2층에 컵을 쌓으려면 두 컵 중 적어도 하나는 빨간 컵이어야 한다.

이에 대하여 점화식을 세우고 일반항을 구하면 피보나치 수가 나온다.

 

전체 j개의 컵 중 l개의 컵을 쌓았고 i개의 컵 중 k개의 컵을 1층에 쌓았다.

이제 (j - l)개의 컵 중 (i - k)개의 컵을 1층에 쌓아야 하는데 여기서 dp[i - k][j - l]이 도출된다.

그리고 (k - 1)개의 컵을 2층에 쌓을 수 있도록 k개의 컵을 1층에 쌓는 경우의 수는 F[k + 2]이다.

 

묶음 내에서는 전체 l개의 컵 중 k개의 컵을 1층에 쌓았고 (k - 1)개의 컵을 2층에 쌓았다.

재귀적으로 생각해보면 기존의 1층을 무시하고 (k - 1)개의 컵이 쌓인 2층을 마치 1층처럼 생각할 수 있다.

여기서 dp[k - 1][l - k]가 도출된다.

 

E - 신도시 개발 (not solved)

어떤 시점 t에 분양되지 않은 토지를 x라고 하자.

l과 r을 각각 x의 왼쪽과 오른쪽에 있는 분양된 토지의 개수라고 하면 토지 x의 할인된 양은 다음과 같다.

(토지 x의 할인된 양) = |l - r| = l + r - 2 * min(l, r) = t - 2 * min(l, r)

따라서 할인된 양을 최소화하기 위해서는 min(l, r)을 최대화해야 한다.

 

토지를 적절한 순서로 분양하면 항상 min(l, r)이 최대가 되도록 만들 수 있다.

이미 분양된 M개의 토지와 앞으로 분양할 K개의 토지가 결정되었다고 가정하자.

그리고 (M + K)개의 토지를 차례대로 1번, 2번, ..., (M + K)번 토지라고 하자.

이때 1번, (M + K)번, 2번, (M + K - 1)번, ... 순으로 분양하면 모든 min(l, r)이 최대가 된다.

구체적인 분양 순서는 중요하지 않고 min(l, r)이 최대가 되도록 만드는 분양 순서가 존재한다는 것만 알면 된다.

 

편의를 위하여 max(sum(min(l, r)))을 토지의 가치라고 정의하자.

다음과 같은 배열 L과 R을 정의하자.

L[i] = 구간 [1 .. i]에 (M + K) / 2개의 토지를 분양할 때 토지의 가치

R[i] = 구간 [i .. N]에 (M + K) / 2개의 토지를 분양할 때 토지의 가치

(M + K) / 2개의 토지를 분양할 수 없거나 이미 분양된 토지의 개수가 (M + K) / 2개를 초과하는 경우에는 -INF가 된다.

 

배열 L과 R은 sliding window로 각각 O(N)에 구할 수 있다.

구체적으로는 앞으로 분양할 토지들을 queue를 이용하여 관리하면 된다.

queue에는 min(l, r)의 최댓값을 삽입한다.

현재 좌표에 이미 분양된 토지가 있다면 앞으로 분양할 토지 하나를 queue에서 제거해야 한다.

이때 토지의 가치는 (q.front() + q.size() - 1)만큼 감소한다.

현재 좌표에 분양된 토지가 없다면 앞으로 분양할 토지 중 가장 왼쪽 또는 오른쪽에 있는 토지를 현재 좌표로 옮기는 것이 최적이다.

마찬가지로 토지의 가치는 (q.front() + q.size() - 1)만큼 감소한다.

이번에는 새로운 토지를 분양하므로 토지의 가치는 다시 ((M + K) / 2 - 1)만큼 증가한다.

 

배열 L과 R을 이용하면 정가운데 토지의 좌표가 i일 때의 토지의 가치를 O(1)에 구할 수 있다.

따라서 전체 문제를 O(N)에 해결할 수 있다.

 

F - 줄넘기 (not solved)

Pass

 

G - 편지 배달 2 (not solved)

Pass

 

H - 정밀지도 제작 (not solved)

Pass

 

끝

내년 대회에 참가할 수 있을지는 아직 잘 모르겠지만 일단 끝