2023 중앙대학교 CHAC (ChAOS Hello2023 Algorithm Contest) Open Contest
2023 중앙대학교 CHAC (ChAOS Hello2023 Algorithm Contest) Open Contest
www.acmicpc.net
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인 경우 원판의 순서가 뒤바뀐다.
이를 이용하면 다음과 같이 쌓인 순서 그대로 원판을 옮길 수 있다.
- 크기가 N 미만인 원판을 세 번째 막대기로 옮긴다.
- 크기가 N인 원판 중 (M - 1)개를 두 번째 막대기로 옮긴다.
- 크기가 N 미만인 원판을 두 번째 막대기로 옮긴다.
- 크기가 N인 원판 중 나머지 하나를 세 번째 막대기로 옮긴다.
- 크기가 N 미만인 원판을 첫 번째 막대기로 옮긴다.
- 크기가 N인 원판 중 (M - 1)개를 세 번째 막대기로 옮긴다.
- 크기가 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
결과는 오히려 페널티 차이로 우승을 차지하였다.
누추한 핸들에 우승 기록을 한 번 더 채워 넣을 수 있어서 기쁘다.
끝
끝