Good Bye & Hello BOJ, 2021 shake! Open 참여 후기

최근에 참여한 백준 대회 3개에 대해서 간략한 후기를 작성하려 한다.

 

Good Bye, BOJ 2021

A. 2021은 무엇이 특별할까? (1 try, 00:02)

 

실버 하위 난이도의 구현 문제라 가볍게 구현해주었다. 

 

B. 예쁜 케이크 (1 try, 00:08)

 

언뜻 보았을 때 Hard한 소인수분해 알고리즘이 필요해 보여서 당황했지만, 식을 잘 들여다보니 답이 될 수 있는 경우는 \(9k\) 또는 \(3k+2\) 꼴이라는 것을 알 수 있었다.

 

C. 성싶당 밀키트 (1 try, 00:18)

 

최근에 코드포스에서 파라메트릭 문제를 많이 보아서인지, 보자마자 파라메트릭이라는 것을 떠올릴 수 있었다. 오버플로우 처리가 약간의 issue였으나, 오버플로우가 생길 만한 범위라면 어차피 답이 되지 못해 상관없는듯 하다.

 

D. 횡단보도 (1 try, 00:38)

 

전형적인 다익스트라 문제이나, 간선의 가중치를 동적으로 변경해주어야 한다. 여기까지만 떠올릴 수 있다면 구현이나 케이스 처리는 특별히 어렵지 않은 것 같다.

 

E. XOR 기계 (10 try, 02:50)

 

문제를 처음 보고 열심히 그래프로 모델링하려 했으나 잘 되지 않았다. 1시간 정도 삽질한 후에야 선형대수학 문제라는 것을 알게 되었고, 나만의 가우스 소거법을 조악하게 구현해 해결에 성공할 수 있었다. 불온전한 정신 상태 + 처음 짜보는 가우스 소거법이라 시간 복잡도를 \(O(N2^{20})\)로 구현하였는데 맞았다... 덕분에 현재 해당 문제에서 C++ 실행 시간 꼴찌를 차지하고 있다. 

 

4솔까지는 굉장히 잘 풀렸으나, E에서 말리면서 5솔 하위권인 62등으로 대회를 마감하였다.

 

Hello, BOJ 2022

A. 2022는 무엇이 특별할까? (1 try, 00:06)

 

이러한 유형의 문제를 SCPC에서도 본 바 있고, 개인적으로 출제 아이디어를 떠올릴 때에도 생각하고 있었기에 풀이를 빨리 찾을 수 있었다. 구현 자체는 next_permutation을 알고 있다면 굉장히 쉽고 빠르게 할 수 있다.

 

C. 미니 버킷 리스트 (1try, 00:22)

 

문제 자체는 전형적인 조합론 문제이다. 경우의 수가 \(N! _{N+1}{H}_{K-S} \)이라는 것은 조합 문제에 익숙하다면 빠르게 캐치할 수 있고, 이를 정리하면 \(\frac{(N+K-S)!}{(K-S)!}\) 이라는 것을 알 수 있다. 이는 \(N+1\)개의 숫자만으로 이루어져 있으므로 시간 복잡도 \(O(N)\)에 문제를 해결할 수 있다.

 

B. 랜드마크 건설 (5 try, 02:14)

 

C 풀고 중간에 밥을 먹어서 시간이 좀 늦어졌다. 점 하나를 (1,1)에 고정하고 점 세개를 모두 한 직사각형의 테두리에 배치한다는 발상을 하면 맞을 수 있으나, 예외처리가 조금 더럽다. 4틀정도면 나름 선방했다고 생각한다. 

 

D. XOR² (2 try, 03:02)

 

정해는 세그트리를 262144칸으로 잡아 인덱스에서 XOR을 잘 하는 풀이이나, 나는 펜윅 트리를 이용한 다른 풀이로 해결하였다. 풀이의 핵심은 해당하는 인덱스들을 \(logN\)개 정도의 구간으로 나타내는 것이다. 이에 필요한 중요한 관찰은 다음과 같다: 만약 \([0,{2^K}-1]\) 구간과 XOR 연산을 하면, 그 결과는 원래 수에서 마지막 K자리를 자유롭게 변형한 길이 \(2^K\)의 구간으로 나타낼 수 있다. 이를 이용해 한 자리수씩 보며 쿼리를 날려주면 \(O(Nlog^2N)\)에 문제를 해결할 수 있었다.

 

B가 예상 외로 어려웠기 때문인지, 주말 낮이라는 대회 시간 덕분인지 4솔 이상의 참가자가 생각보다 적어 25위라는 높은 순위를 기록했다.

2021 경인지역 6개대학 연합 프로그래밍 경시대회 shake! Open Contest

A. 젓가락 (2 try, 00:02)

 

비둘기집의 원리를 통해 잘 생각해보면 답은 \(2R+N-1\) 이다.

 

B. 모두싸인 출근길 (1 try, 00:21)

 

B번치고 어려워서 당황한 문제이다. 스위핑을 하기 전에 겹치는 판자를 모두 한 덩이로 만들어주고 다시 스위핑을 하면 비교적 깔끔하게 해결할 수 있다.

 

C. 트리 색칠하기 (3 try, 00:33)

 

정해는 BFS, 심지어는 BFS조차 하지 않고 문제를 해결할 수 있다. 하지만 나는 트리 DP 풀이가 바로 보여 오버킬을 해버렸다..

 

D. 해석 (4 try, 00:51)

 

파일 합치기 문제와 같은 전형적인 \(O(N^2)\) DP이다. 다만, 겹치는 경우 처리를 해주어야 해서 생각할 거리가 조금은 있었던 것 같다.

 

H. 유산 (3 try, 01:25, First solve)

 

D까지 풀고 남은 문제들을 보았는데, 이 문제가 가장 머리를 안쓰고 손만 움직여도 되는 문제였기에 잡았다. 컨벡스 헐을 만들고 해당 좌표 범위에서 이분 탐색을 하면 문제를 해결할 수 있다. 다각형의 넓이를 구하려면 컨벡스 헐에 포함되지 않는, 잘라서 나오는 교점의 위치를 구해야 하는데, 결국 컨벡스 헐 위의 점에서 구하는 것이기 때문에 크게 어렵지 않다. 

 

E. 망가진 나무 (3 try, 02:09)

 

진짜 트리 DP 문제이다. 트리 DP를 안다면, 상태 전이는 비교적 쉽게 할 수 있기 때문에 어렵지 않게 해결할 수 있을 것이다.

 

G. 1차원 체스 (3 try, 02:33)

 

역시 전형적인 트라이 문제인데, 인덱스 범위가 꽤 넓기 때문에 map등의 자료구조를 사용해야 한다. 그 외에도, 예외처리를 몇 가지 해주어야 하기 때문에 문제에서 설명하는 정의를 잘 보고 들어가야 할 것 같다. 

 

이후에는 F를 풀려고 시도했지만 잘 되지 않았다. 아직 스코어보드 프리즈가 풀리지는 않았지만, 오전에 Hello BOJ가 있었던 점 / 같은 시간에 앳코더랑 코포가 겹친 점 등등 때문에 잘하는 분들이 좀 빠진 것 같았고, 운이 좋게도 2등이라는 순위를 찍을 수 있었다. 백준 대회에서 이렇게 높은 등수는 처음이라 좀 기쁘다ㅎㅎ