2022 연세대학교 프로그래밍 경진대회 Open Contest

2022 연세대학교 프로그래밍 경진대회 Open Contest

A - 연세여 사랑한다

abs(c - 'I') + 84

00:03 AC

 

B - Prime Arrangement

어려워 보였는데 스코어보드를 보고 공식을 찾았다.

RC! / R!

00:07 AC

 

C - 싫은데요

two pointer

00:14 AC

 

D - 북극곰은 괄호를 찢어

stack

00:19 AC

 

E - 건너 아는 사이

Sieve of Eratosthenes 응용

00:25 AC

 

F - 비밀의 레시피

보자마자 숨이 턱 막혔다.

갑자기 BigInteger 문제가 나오니 당황스러웠다.

Gaussian Elimination 코드를 Java로 구현하였다.

01:09 AC

참고로 단 한 번의 query로 단순하게 해결할 수도 있다.

대회 중에는 전혀 보이지 않았다.

 

G - Lost Edge

pq bfs

01:26 WA

사소한 구현 오류를 수정하였다.

01:47 AC

 

H - Yonsei Formula 1

dp + 이분 탐색

02:10 WA

overflow 문제를 발견하여 해결법을 찾다가 그냥 __int128 박았다.

02:22 AC

__int128 없이 hi를 조정하여 overflow를 방지할 수 있다.

 

I - 동아리 박람회

ad hoc

N = 2^k or N = 2^k + 1 or K < 4이면 답이 존재하지 않는다.

그렇지 않다면 최대 이동 거리가 4인 최단 경로가 항상 존재한다.

03:00 AC

 

J - 기러기 토마토 스위스 인도인 별똥별 (not solved)

2차원 구간을 효율적으로 관리할 수 있는 자료 구조가 필요하였다.

2D Segment Tree with Lazy Propagation을 구현해보려고 하였으나 잘 되지 않았다.

실제로 가능한 자료 구조인지도 모르겠다.

인터넷을 뒤지다가 Quad Tree라는 자료 구조를 보았고 아이디어를 그대로 빌려왔다.

대회 종료 10분 전에 구현을 마쳤으나 TLE를 받았다.

다시 생각해보니 적절한 자료 구조가 아니었다.

 

우선 각 비트에 대하여 필요한 연산을 저장하는 배열 B를 구성하자.

가능한 연산은 6개이지만 동일한 연산을 제거하여 3개로 줄일 수 있다.

예를 들어 아래와 같이 정리할 수 있다.

if B[i][j] == 0 then 연산이 필요 없음

else if B[i][j] == 1 then 2사분면과 1사분면을 교환해야 함

else if B[i][j] == 2 then 2사분면과 3사분면을 교환해야 함

else if B[i][j] == 3 then 2사분면과 4사분면을 교환해야 함

중요한 성질은 (i, j)에 연산 k를 수행하면 B[i][j]가 B[i][j] ^ k로 바뀐다는 것이다.

 

실제로 업데이트를 수행하면 O(NMK^2)이므로 TLE를 받는다.

따라서 각 비트에 대하여 실제로 수행한 연산을 저장하는 배열 D를 구성하자.

2차원 누적 합을 응용하면 업데이트를 O(NM)에 수행할 수 있다.

단순히 합 대신 xor을 하면 된다.

 

K - Darkest Dungeon (not solved)

트리의 지름을 이용하는 것이 신기하였다.

아래 변수를 이용하면 보다 간편하게 구현할 수 있다.

cnt1 = min(K, 트리의 지름)

cnt2 = min((K - cnt1) / 2, N - cnt1 - 1)

 

L - 안아줘요 (not solved)

절댓값을 벗기면 두 개의 식으로 나누어진다.

각각의 식을 Segment Tree로 관리하면 된다.

 

M - Parity Constraint Maximum Flow (not solved)

Flow 초심자인 나에게는 너무 어려워서 Pass

 

끝

끝