2022 SKKU 프로그래밍 대회 in 소프트의 밤 Open Contest

2022 SKKU 프로그래밍 대회 in 소프트의 밤 Open Contest

서론

요새 바쁘기도 하고 추가적으로 공부할 부분도 많아 업솔빙이 늦어졌다.

조금 늦었지만 후기를 올린다.

 

A - 안녕 클레오파트라 세상에서 제일가는 포테이토칩

단순 구현

00:01 AC

 

B - 장인은 도구를 탓하지 않는다

단순 수학

00:08 AC

완전 탐색은 불필요하다.

 

C - 수렵의 시간이다!

완전 탐색

00:25 AC

보통 이런 문제에서 실수를 많이 하는데 첫 제출에 바로 AC가 나와 기뻤다.

 

D - 양과 늑대

이분 탐색

00:33 AC

 

E - 수열의 합

수학

00:39 AC

추가적으로 O(sqrt N) 풀이를 배웠다.

 

F - 수확의 계절이다!

이분 탐색

00:54 TLE

특정 좌표를 방문하는 시점은 언제나 동일하다.

이를 이용하여 시간 복잡도를 줄일 수 있다.

01:02 AC

 

G - 게이트웨이 정하기

게이트웨이 노드가 u일 때의 전달 비용을 알고 있다면 이웃 노드 v가 게이트웨이 노드일 때의 전달 비용은 쉽게 구할 수 있다.

임의의 노드에서 dfs를 돌리고 각 노드마다 비트 단위로 검사해주면 된다.

01:42 AC

 

남은 시간은 3시간 정도였다.

H랑 K는 내 실력으로 절대 못 풀 것 같아서 바로 넘겼다.

I랑 J가 그나마 희망이 보였는데 스코어보드를 보고 I를 잡았다.

그리고 결국 못 풀었다.

근본적인 원인은 실력 부족이다.

전날 이태원 참사로 잠을 이루지 못한 탓에 집중력도 크게 떨어졌다.

 

H - 현상금 헌터 (not solved)

유사한 문제를 dp로 풀 수 있다는 것은 알고 있었다.

하지만 해당 문제의 정확한 풀이는 알지 못하였고 출처는 지금도 기억이 나지 않는다.

 

이 문제의 핵심은 가능한 상태의 수를 줄이는 것이다.

마지막으로 잡은 도둑과 시간만 메모이제이션하는 것만으로도 충분하다.

모든 좌표와 시간을 2배로 만들어 실수 좌표를 방지하는 것도 중요하다.

체스판의 흑백을 생각하면 실수 좌표가 발생할 수 없음을 알 수 있다.

 

I - 전투 시뮬레이션 (not solved)

수식 정리가 굉장히 오래 걸렸다.

원래 느리기도 하고 전날에 잠을 잘 못 자서 집중력도 다소 떨어졌다.

정리를 마치니 이해할 수 없는 수식이 나와 이게 무슨 의미인가 잠시 고민하였다.

코드로 표현하면 다음과 같았다.

for i = l + (r - l + 1) / 3 - 1 to r - (r - l + 1) / 3

    ans = min(ans, abs(psum[l - 1] + psum[r] - 2 * psum[i]));

 

원리를 이해하는 데 오랜 시간이 걸렸다.

psum[l - 1]과 psum[r]의 평균과 가장 가까운 psum[i]를 찾는다고 생각하면 된다.

 

이를 naive하게 구현하면 O(N)이기 때문에 더 효율적인 방법이 필요하였다.

offline query로 처리하면 가능할 것 같았는데 WA를 받았다.

물론 offline query 풀이가 불가능하다는 것은 아니고 그냥 내가 잘못 풀었다.

 

아무튼 다른 해결책을 찾아야만 하였다.

머릿속에 떠오른 것은 Merge Sort Tree와 Square Root Decomposition이었다.

Merge Sort Tree는 가능해 보였는데 구현이 복잡할 것 같았다.

Square Root Decomposition은 공부해본 적은 없지만 구현이 간단할 것 같았다.

 

결론적으로 Square Root Decomposition을 선택하였고 이것이 패착이었다.

O(N sqrt N)은 접하기 어려워서 굉장히 매력적으로 보였다.

대회 종료가 코앞에 다가와서야 TLE를 받았고 잘못된 선택이었음을 깨달았다.

또한 Merge Sort Tree의 구현은 생각보다 단순하였다.

 

이 문제의 정해는 Merge Sort Tree 또는 Segment Tree + offline query이다.

앞에서 Merge Sort Tree를 선택하였다면 한 문제를 더 풀 수 있었을 것이다.

이 판단조차 나의 실력이니 누구를 원망하겠는가.

Segment Tree + offline query 풀이는 query를 두 번에 걸쳐 처리한다는 발상이 놀라웠다.

 

J - 달나라에 사는 토끼와 우주에서 떨어지는 떡 (not solved)

아이디어는 간단하였는데 효율적인 구현 방법이 떠오르지 않았다.

무언가 다른 알고리즘이 필요하다고 생각하였고 미련 없이 I번을 잡았다.

그리고 에디토리얼을 보고 상당히 당황스러웠다.

에디토리얼에 있는 모든 내용은 대회 시간 중에 이미 도출하였기 때문이다.

 

구현이 어려운 문제이다.

단순히 구현이 어렵다기 보다는 효율적인 구현 방법을 떠올리는 것이 어려운 문제이다.

에디토리얼에는 딱히 이러한 내용이 없는데 나만 이렇게 느끼는 것일 수도 있다.

 

2022년 11월 29일 새로 짰다.

26128번을 풀면서 functional graph에서 위상 정렬을 이용하면 사이클 판별이 가능함을 배웠다.

기존 코드에 비해서 매우 간결해졌다.

그래도 복잡하기는 한데 구현 자체가 복잡한 문제라서 지금은 이게 최선인 듯 하다.

 

K - 커모드 곰의 연어 사냥 (not solved)

단절선 + 그런디 수 문제임을 깨달았지만 두 주제 모두 잘 기억이 나지 않아서 넘겼다.

두 주제 모두 복습하고 업솔빙하였다.

 

끝

끝