2024 SKKU 프로그래밍 대회 in 소프트의 밤 1위 후기

대회 결과

소프트의 밤(학과 연례행사) 시기에 같이 하는 프로그래밍 대회에 출전해 (후배들 자리를 뺏는다) 7솔브/1등했다. 하긴 솦밤 프로그래밍 대회에서 상금을 타간 적이 없고 이번 대회가 마지막 교내대회이기도 하고 한창 출제할 시기에 독일에 있었기 때문에 참여자로 나가기로 했다.
학과 지원금, 기업 후원 등 과정에서 여러 어려움이 있었다고 한다. 힘들고 바쁜 상황에도 대회 열어준 재학생 듀오 Coxie, o9j8w7 감사합니다 ㅠㅜ
이번 대회는 특이하게도 문제 난이도 순서가 랜덤이고, 또 이름 달지말고 별명으로 만들어달라고 해서 5분 생각해서 나온 별명 계산기하를레알SAP못함 은 1년 넘게 인턴 하고 있는 회사이름을 넣었고, 기하학 문제에 약해서 이렇게 지었다 (SCPC 1차 예선 CHT문제를 제곱근분할으로 푼 사람 나야..).
아래 풀이는 내가 문제 푼 순서(난이도 순이랑 거의 일치하는 듯)대로 정리했다. 문제 세트는 여기서 확인할 수 있다.

---

D. 동아리비 횡령 (AC+3/+17min)

진짜 바보같이 case work해서 풀었다.... 그냥 1+1부터 100+100까지 쭉 string 만들어서 find하면 되는 문제를 3번이나 틀림ㅜㅜ

---

E. 카드 뒤집기 게임 (AC/+23min)

가장 왼쪽부터 쭉 flip하기 때문에, 0 -> 1로 바뀌는 지점 전까지 혹은 1 -> 0으로 바뀌는 지점 전까지 flip하는게 항상 best이다. $O(N)$에 풀기 위해서는 (000) (1111) (0000) (11) -> 3 4 3 2 와 같이 바꾸고 인접한 두 원소 합 최댓값 구해주면 된다.

---

H. 분할 (AC/+41min)

대회에서는 최소/최대 세그먼트트리 만들어서 풀었다. 근데 그렇게 안해도 되고 브루트포스로 풀어도 시간 내에 통과한다고 한다. 브루트포스로 풀면 $N$의 약수 개수를 $P$라고 할 때 $O(NP)$인데, 100만 이하인 $N$ 중에 약수 개수가 가장 많은건 $N=720720$일 때 240개 있다. 최대 2억4000만회 연산을 하므로 1초 내에 충분하다.

---

G. 신기한 루트 개수 찾기 (AC/+73min)

C, G 모두 풀이가 떠올랐는데, G가 더 쉬울것 같아 G부터 풀었다. 정해는 a의 서브트리 개수, b의 서브트리 개수 구해서 빼주는 것 같은데, 나는 a, b 사이에 있는 정점 개수를 BFS로 풀었다. a에서 b로 가는 최단경로에 포함되는 정점 아무거나 하나를 큐에 넣고, a나 b를 마주치면 탐색하지 않도록 하면 된다.

---

C. 점령 (AC+1/+90min)

다익스트라와 비슷하게 pq에다가 인접한 노드에 방문 시 기력 증가량 $B_i$를 오름차순으로 정렬해놓고 작은 것부터 탐색한다. 한 번 틀린 이유는 push된 정점을 또 push하게 만들어놔서, pushed bool배열 하나 더 만들어서 관리하니 통과됐다.

---

F. 짝사랑 (AC+1/+146min)

현재 노드와 같은 BCC이면 1, 아니면 0으로 풀었다. 사실 BCC를 한 번도 짜본적이 없고 개념도 모르고 있어서(단절점/단절선 개념만 알고 있었음), SCC 코드에서 조금 변형해서 BCC를 짰다. 1번 틀렸을 때는 1번노드와 인접하거나 같은 SCC이면 1, 아니면 0으로 풀었다. 아마 대회때 낸 BCC 코드는 $O(N+M)$이 아닐듯...
또, 이 문제에서 누가 엄청난(?) 반례를 선보였다. 반례 고려하면 난도가 확 높아지는 것 같다.

---

A. 작전 (AC+1/+175min)

처음에 $O(N^2)$ 코드를 제출하고 당연하게도 시간초과가 뜨길래, 답이 $N$인 경우 어차피 최대이므로 break하는 줄을 추가하니 풀렸다. 당연하게도 시간 초과 뜨는 반례(답이 $N-1$인 경우)가 존재한다. 맞았습니다! 떴을 때 놀랐던 기억이... (A 못 풀었어도 1등이라서 고백할 수 있다.)

---

B. Eight 2 Zero

정점이 $N$, 간선이 $N+1$인 그래프는 여러 모양이 있는데, 그 케이스를 모두 고려해주면 된다.
대충 1. 큰 사이클 하나에 중간 다리가 있는 형태, 2. 사이클 2개가 있고 중간 다리가 있는 형태, 3. 사이클 2개가 있고 2개 모두에 포함되는 정점 하나가 있는 형태 를 모두 고려해주면 된다고 한다(아직 풀어보진 않았다.)

---

밀린 블로그 글 과업을 모두 마무리했다. 이제 tistory에는 글 거의 안올릴 것 같다 (현대모비스/해커컵같은 직장인 나갈 수 있는 대회 본선 나가면 후기는 올라올수도 ㅋㅋ)
만들었다 지웠다 3번정도 반복했던 깃허브 블로그 다시 파서 관심있는 도메인들(DB Paper Review, Distributed Algorithm, C++/Rust 등) 정리하려고 한다. 아직 지킬 theme 뭐할지 고민중이라 파진 않았지만 주소는 https://ggyuchive.github.io/ 입니다 ㅎㅎ 많관부!!