Good Bye, BOJ 2022!

Good Bye, BOJ 2022!

서론

전체 599명의 참가자 중 35등으로 오프라인 본선에 진출하였다.

수상 가능성은 0에 가까워서 가볍게 여행 다녀온다고 생각해야겠다.

 

A - 2022년이 아름다웠던 이유

구현

00:06 AC

 

B - 나무 블럭 게임

ans = max(avg, A[N - 1]);

00:12 AC

 

D - 이미지 보정 작업

이분 탐색 + bfs

00:38 AC

 

C - 데이터 순서 복원

임의의 단계 a와 b에 대하여 a와 b의 서열을 알 수 있다.

이를 이용하여 위상 정렬하면 된다.

00:46 AC

정해는 직관적이지 않아서 Pass

 

2023/01/10 추가

위상 정렬은 overkill인데 단순히 사용자 정의 함수로 정렬하면 된다.

 

E - 리그전

상위 (k - 1)개의 팀과 하위 (n - k)개의 팀을 별도로 case work 해주면 된다.

시작에 앞서 a >= c라고 가정한다.

 

(i) 최댓값 구하기

하위 (n - k)개 팀과의 경기 결과는 다음 중 하나이다.

• 모두 이긴다.
• 모두 비긴다.

상위 (k - 1)개 팀과의 경기 결과는 다음 중 하나이다.

• 모두 비긴다.
• ((k - 1) / 2)번 이기고 ((k - 1) / 2)번 진다.
• 위의 경우에서 (k - 1)이 홀수인 경우에는 추가적으로 비기거나 진다.

코드로 표현하면 다음과 같다.

ans = max(a, b) * (n - k) + max(b * (k - 1), (k - 1) / 2 * (a + c) + ((k - 1) % 2) * max(b, c));

 

(ii) 최솟값 구하기

상위 (k - 1)개 팀과의 경기 결과는 다음 중 하나이다.

• 모두 비긴다.
• 모두 진다.

하위 (n - k)개 팀과의 경기 결과는 다음 중 하나이다.

• 모두 비긴다.
• ((n - k) / 2)번 이기고 ((n - k) / 2)번 진다.
• 위의 경우에서 (n - k)가 홀수인 경우에는 추가적으로 이기거나 비긴다.

코드로 표현하면 다음과 같다.

ans = min(b, c) * (k - 1) + min(b * (n - k), (n - k) / 2 * (a + c) + ((n - k) % 2) * min(a, b));

 

01:13 WA    01:18 WA    01:30 WA    01:35 WA    01:40 AC

WA를 받은 이유는 일부 case를 고려하지 않았거나 괄호를 잘못 여닫았기 때문이다.

괄호를 잘못 여닫는 실수는 처음 해보는데 늦게나마 발견해서 다행이다.

 

F - 전설의 고대 광산 탈출

못 푸는 문제 같아서 인터넷 하면서 놀고 있었다.

심심해서 식 정리를 하였는데 knapsack dp 형태가 되었다.

02:41 AC

 

G - 크루스칼 알고리즘 (not solved)

Kirchhoff's theorem

 

H - Maxtrix (not solved)

분할 정복 + cht

 

끝

끝