2023 고려대학교x연세대학교 프로그래밍 경시대회 Open Contest

2023 고려대학교x연세대학교 프로그래밍 경시대회 Open Contest

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

 

끝

끝