Good Bye, BOJ 2021!

Good Bye, BOJ 2021!

서론

2022년 대회 예비소집 문제로 출제되었다.

 

A - 2021은 무엇이 특별할까?

전처리

 

B - 예쁜 케이크

a * b = N and (a + b) % 3 = 0인 a와 b가 존재하는지 확인해야 한다.

case work를 해보자.

 

(i) a % 3 == 0 and b % 3 == 0

a와 b 모두 3의 배수이므로 N % 9 == 0이어야 한다.

 

(ii) a % 3 == 1 and b % 3 == 2

a와 b는 각각 (3k_a + 1)과 (3k_b + 2)로 표현할 수 있다.

이때 a와 b의 곱은 (3 * (3 * k_a * k_b + 2 * k_a + k_b) + 2)이다.

따라서 N % 3 == 2이어야 한다.

 

(iii) a % 3 == 2 and b % 3 == 1

(ii)번 case와 동일하다.

 

따라서 N % 9 == 0 or N % 3 == 2인지 확인하면 된다.

 

C - 성싶당 밀키트

이분 탐색

 

D - 횡단보도

dijkstra

 

E - XOR 기계

찍었는데 맞았다.

원리는 대략적으로 이해하였지만 설명할 수 있을 정도는 아니다.

 

F - 미로 설계

편의를 위하여 위상 정렬 순서가 정점 번호 순서와 동일하다고 가정한다.

다음과 같은 배열 A를 정의하자.

A[i] = i번 방에 도착하는 경우의 수

A[1] = 1이므로 1번 방에서 N번 방으로 가는 통로를 x개 추가하면 문제를 해결할 수 있다.

하지만 문제의 제한에 의하여 최대 120개의 통로만 추가할 수 있다.

 

A[i] = 2^(i - 1)가 되도록 통로를 적절히 추가하였다고 가정하자.

이때 추가적으로 최대 log K개의 통로를 추가하면 문제를 해결할 수 있다.

이미 존재하는 통로 때문에 위의 가정을 만족시키는 것은 거의 불가능하지만 이와 유사하게 만들 수는 있다.

i번 방에서 (i + 1)번 방으로 가는 통로를 적절히 추가하여 2 * A[i] <= A[i + 1] < 3 * A[i]를 만족시킬 수 있음을 증명할 수 있다.

결론만 말하자면 최대 4 log K개의 통로를 추가하여 문제를 해결할 수 있다.

 

G - 극장 좌석 배치

복잡한 case work

 

끝

끝