2023 중앙대학교 CHAC (ChAOS Hello2023 Algorithm Contest) Open Contest

2023 중앙대학교 CHAC (ChAOS Hello2023 Algorithm Contest) Open Contest

A - 찬반투표

단순 구현

00:01 AC

 

B - 시프트 연산

다음 4가지 경우만 고려하면 된다.

• L-시프트
• R-시프트
• L-시프트 후 R-시프트
• R-시프트 후 L-시프트

00:14 AC

 

D - 버섯 농장

dfs

대회 참가 직전에 푼 문제랑 비슷해서 코드 복붙하고 살짝 수정하였다.

00:20 AC

 

F - 연산자 파티

right shift 이후 X는 항상 0이 됨에 주목해야 한다.

00:25 AC

 

H - 월드컵 조별리그

이분 탐색

00:43 WA

이분 탐색 범위를 잘못 잡았다.

00:44 AC

 

C - 견제 미로찾기

게임 이론 dp

대회 중에는 그런디 수까지 사용하며 뇌절하였다.

00:52 AC

 

E - 어려운 하노이 탑

M = 1이라면 일반적인 하노이 탑 문제와 동일하다.

이 경우 답은 (2^N - 1)이 된다.

 

M > 1일 때 크기가 동일한 원판을 구분하지 않는다면 답은 (M * (2^N - 1))이 된다.

이때 크기가 i인 원판에 대하여 i % 2 = N % 2인 경우 원판의 순서가 뒤바뀐다.

이를 이용하면 다음과 같이 쌓인 순서 그대로 원판을 옮길 수 있다.

1. 크기가 N 미만인 원판을 세 번째 막대기로 옮긴다.
2. 크기가 N인 원판 중 (M - 1)개를 두 번째 막대기로 옮긴다.
3. 크기가 N 미만인 원판을 두 번째 막대기로 옮긴다.
4. 크기가 N인 원판 중 나머지 하나를 세 번째 막대기로 옮긴다.
5. 크기가 N 미만인 원판을 첫 번째 막대기로 옮긴다.
6. 크기가 N인 원판 중 (M - 1)개를 세 번째 막대기로 옮긴다.
7. 크기가 N 미만인 원판을 세 번째 막대기로 옮긴다.

이때 이동 횟수는 (2 * M * (2^N - 1) - 1)이 되며 이보다 적은 횟수로 원판을 옮길 수 없다.

증명 난이도에 비하여 찍어 맞추는 난이도는 낮은 편이다.

증명 과정은 에디토리얼을 참고하자.

물론 나는 안 읽어봤다.

01:27 AC

 

G - 수열 재배열

문제를 잘못 읽어서 마지막으로 풀게 되었다.

먼저 다음과 같은 배열 B와 C를 정의하자.

B[i] = 구간 [1, i]에서 A[i]를 포함하는 연속된 증가하는 부분 수열의 최대 길이

C[i] = 구간 [i, N]에서 A[i]를 포함하는 연속된 증가하는 부분 수열의 최대 길이

 

구간 S = [i, i + K - 1]을 재배열하였다고 가정하자.

이때 다음 세 가지 경우만 고려하면 된다.

• B[i - 1] + (구간 S에서 A[i - 1]보다 큰 원소의 개수)
• C[i + K] + (구간 S에서 A[i + K]보다 작은 원소의 개수)
• A[i - 1] < (구간 S의 최솟값) && (구간 S의 최댓값) < A[i + K]인 경우 B[i - 1] + K + C[i + K]

N 제한이 작기 때문에 특별한 자료 구조가 필요하지는 않다.

 

xiaowuc1님이 이미 모든 문제를 풀이하였고 나는 2등에 위치하고 있었다.

3등도 단 한 문제만을 남겨 놓고 있었기에 마음이 조급해졌다.

01:46 RTE

01:47 WA

마음이 조급해지니 실수를 남발하였다.

01:51 AC

 

결과는 오히려 페널티 차이로 우승을 차지하였다.

누추한 핸들에 우승 기록을 한 번 더 채워 넣을 수 있어서 기쁘다.

 

끝

끝