2023 고려대학교x연세대학교 프로그래밍 경시대회 Open Contest
2023 고려대학교x연세대학교 프로그래밍 경시대회 Open Contest
www.acmicpc.net
A - 당신은 운명을 믿나요?
구현
00:02 AC
B - Parity Constraint Closest Pair (Easy)
배열 A, B, C를 다음과 같이 정의하자.
- A = 홀수 좌표를 저장하는 배열
- B = 짝수 좌표를 저장하는 배열
- C = 모든 좌표를 저장하는 배열
서로 다른 두 점의 거리 중 짝수인 최솟값은 배열 A와 B에서 인접한 원소의 차잇값의 최솟값을 구하면 된다.
홀수인 최솟값은 방금 전과 동일하게 배열 C에서 인접한 원소의 차잇값의 최솟값을 구하면 된다.
이때 인접한 두 원소의 parity가 상이한 경우만 고려해야 한다.
00:07 WA
분명히 완벽한 풀이인데 WA를 받았다.
원인을 찾지 못하고 이분 탐색을 곁들이는 뇌절을 하였다.
00:11 WA
좌표 조건을 잘못 보고 INF를 너무 작게 설정한 것이 문제였다.
좌표가 음수일 수도 있으므로 INF는 적어도 2e9보다 커야 한다.
00:14 AC
C - 어깨동무
이분 탐색
00:17 AC
E - 마계안암
dijkstra 돌리고 위상 정렬하면서 세주면 된다.
나는 쉽게 풀었는데 티어가 조금 높게 잡혀 있었다.
00:38 AC
F - 고연전/연고전 기차놀이
dp 점화식은 간단한데 deque을 이용한 최적화가 필요하다.
대회 며칠 전에 공부한 주제라서 쉽게 풀 수 있었다.
00:54 AC
D - 대회 이름 정하기
연속된 카드 중 같은 글자가 써진 카드를 하나의 그룹으로 생각하자.
다음과 같은 배열을 정의하자.
- B[i] = [1 .. i]번 카드만 고려할 때 그룹의 개수
- C[i] = C[i - 1] + (i번 그룹에 속한 카드 중 최댓값)
- L[i] = max(A[(i번 카드가 속한 그룹의 시작 인덱스) .. i])
- R[i] = max(A[i .. (i번 카드가 속한 그룹의 끝 인덱스)])
전처리와 query 모두 O(N)에 해결할 수 있는데 대회 중에는 O(N log N)에 풀었다.
01:27 AC
G - 연고전/고연전 (not solved)
서브태스크 1은 bitmask dp로 간단히 풀 수 있다.
서브태스크 2를 풀기 위해서는 원본 문제를 min-cut 문제로 변형시켜야 한다.
flow 문제임은 금방 눈치챘는데 모델링 경험이 극히 적어서 모델링에 실패하였다.
max-flow min-cut theorem도 너무 오랜만에 마주한 개념이었다.
(남은 연세대 팀원) - (남은 고려대 팀원)을 최대화시키는 것은,
- (남은 고려대 팀원) - (남은 연세대 팀원)을 최소화시키는 것과 동일하다.
- 또한 (남은 고려대 팀원) + (탈락한 연세대 팀원)을 최소화시키는 것과 동일하다.
여기까지 왔으면 모델링은 감이 잡힐 것이다.
고려대 팀원을 최소 한 명 선택해야 한다는 조건이 있는데 그냥 flow 그래프를 M번 만들면 된다.
H - 간단한 쿼리 문제 (not solved)
서브태스크 2까지는 mo's로 간단히 풀 수 있다.
서브태스크 3을 풀기 위해서는 sweepline mo라는 기법을 이용해야 한다.
코포의 이 글과 소멤의 이 글에서 해당 주제를 다루고 있다.
I - 트리 위의 세 사람 (not solved)
Pass
끝
끝