[231104] KUPC 2023 참가 후기

건국대학교에서 교내 알고리즘 경진대회가 KUPC 2023이라는 이름으로 개최됐다!

 

나는 작년에 KUPC 2022를 개최하고 운영한 경험이 있다.

해당 경험에 대한 후기는 아래 블로그 포스팅으로 작성해놓았다.

https://kth990303.tistory.com/400

[221203] KUPC 2022 출제 및 운영 후기

 

하지만 2023년에는 PS 및 알고리즘 공부를 거의 하지 않고 백엔드 개발, 또는 회사일에 전념하곤 했다.

그래서 사실 이번 KUPC 2023은 참가할지 말지 고민을 많이 했다.

 

그러다 문득, KUPC 2023 출제진들이 내 친구 및 지인들(aru0504, riroan, dldyou, pizzaroot 등등)이기도 하고, 친한 친구(delena0702)가 대회 div1에 참전한다고 해서 나도 응시해보았다. 대회에 큰 목적을 뒀다기보단, 끝나고 뒷풀이 때 저녁먹으면서 div1 문제에 대한 얘기를 나눌 겸 참가했다 ㅋㅋ

 

난이도에 따라 div1, div2로 나뉘어져 있다.

나는 PS를 접은지 꽤 됐기 때문에 div2에 참가하는게 좋지 않을까 고민했다.

하지만 div2 참여조건이 4학기 이하 재학생이라, div2에 참여하고 싶어도 못한다. 그래서 div1에 참여했다.

 

 

새천년관 4층에서 대회가 열렸고, KUPC 기념스티커를 받으며 Div1 안내페이지에서 대회 시작을 기다렸다.

이 때 마음은 굉장히 편안했다.

스스로 합리화를 했기 때문이다. 어차피 난 PS 접었으니까, 편안하게 보자~ 라는 마음으로 ㅋㅋ

 

자, 드가자~~

 

https://www.acmicpc.net/category/989

2023 건국대학교 프로그래밍 경진대회 (KUPC)

문제는 위 링크를 클릭하면 볼 수 있다.

---

대회 문제 후기

A번

퍼솔!

A번은 일자형 전장에서 각 캐릭터들이 칸을 이동하여, 상대방을 마주치면 승리하는 문제이다.

각 차례에 한번씩 이동가능하므로, 크게 고민할 거 없이 홀짝성에 따라 건덕이나 건구스를 출력하면 되겠다! 싶어서 고민 많이 안하고 바로 코드를 짰다.

덕분에 약 30초만에 AC를 받았다 ㅎㅎ

 

B번

B번부터는 빠르게 풀기보단 정확성에 집중했다.

1번 틀릴 때마다 패널티가 좀 크기 때문에, 그리고 수상권이 목적이 아니었기 때문에 천천히 정확하게 푸는 것을 목표로 했다.

 

키가 같은 사람이 2명을 넘으면, 그 학생들은 모두 참가할 순 없다. 키가 같은 케이스가 최대 2명까지!

생각을 끝냈으니 코드를 짠다.

나의 경우는 map을 이용했는데, 정렬해서 알잘딱깔센하게 푸는 분들이 많았던 듯.

 

 

C번

C번을 풀 때쯤에 내 윗순위에는 5명 정도가 있었던 걸로 기억한다.

근데 그 5명 중 대부분이 C에서 맞왜틀을 외치거나, D로 건너뛰거나 하는 모습을 보여주었다. 그래서 C는 진짜 틀리지 말고 정확하게 풀자는 마인드로 갔다.

 

브루트포스로 돌리면 100% TLE를 받을 게 뻔한 문제.

말뚝은 1000*1000을 해도 그렇게 크지 않으므로 쭉 나열시킨 후, 깃대 높이를 정렬시켜 이분탐색하면 되겠다는 생각을 했다.

그러면 시간초과는 받지 않을 것 같다는 생각!

여기까지 생각을 마치고 나니, 이분탐색해서 인덱스가 이상하게 잡혀 틀리는 케이스가 많나보다~ 하는 생각이 들었다.

그래서 진짜 안전하게 lower_bound, upper_bound 각각의 경우를 세운 후, 추가로 검증하는 케이스까지 넣어주었다. 그 덕분에 다행히 한번에 AC!

 

 

D번

누적합이긴 한데... 대각선 누적합을 어떻게 하지? 하는 생각으로 조금 당황했다.

짱구를 굴려도 잘 생각이 안났다.

그러다가 DP처럼 생각을 바텀업으로 천천히 해보자... 하면서 맘을 다잡기 시작.

P[i][j]에서 이미 대각선 누적합을 다 구했다고 치자. 그러면 P[i+1][j+1]에서는 P[i][j]를 빼고 정사각형 누적합에서 세로길이만 추가한 값이 되겠다! 

이렇게 점화식을 구하고 나니 식 짜는덴 어렵지 않았다. 그렇게 D번도 한번에 AC!

 

개인적으로 KUPC div1 A~G 꿀잼 탑 중 하나라 생각.

참고로 이 문제 보자마자 `이거 aru0504가 냈을 거 같은데?` 하는 생각이 들었고, 역시 이 문제는 aru0504가 냈었다 ㅋㅋ

 

 

E번

처음에 문제를 잘못 읽어서 최소시간으로 가는 문제인 줄 알고, BFS와 DP 중에 고민했다. 

근데 예제입력1에서 답이 5길래 한참 고민하다가 문제를 다시 보니 최대시간이었다 ㅋㅋ (최소시간으로 가면 답은 2가 된다.)

 

반전 횟수도 있고, 현재 앞으로 가는지 뒤로가는지 상태에 따라 메모이제이션이 필요해보여 DP로 접근!

그런데, 맞왜틀을 엄청 했다!

알고보니 ai == 0인 경우에는 아무리 이동해도 도착을 할 수가 없기 때문.

그래서 ai==0인 경우가 존재하면 -1을 출력하게 했는데 또 틀렸다. ai==0인 곳이 있다 하더라도, 여기를 거치지 않으면 상관없기 때문이다.

그리고 ai==0으로 인해 생겨나는 예외케이스가 꽤 있다.

그렇게 해서 반례를 몇가지 만들어가면서 5틀 후에 겨우겨우 AC.

 

하씨 이것도 aru0504가 만들었을거 같은데? 했는데 역시 aru0504. 너 이자식, 맞왜틀 문제 만들지 말란말이야~~

 

 

F번

E번 맞왜틀 고통으로 인해 E를 건너뛰고 도전한 문제.

처음에는 문자열 관련 알고리즘인줄 알고 바로 건너뛸까 싶었다.

그런데 문자를 0~9까지만 준다는 걸 확인! 어? 이거 잘하면 브루트포스도 되겠는데? 하다가, 아예 문자 상태값을 비트마스킹으로 주면 훨씬 최적화도 할 수 있고 시간내로도 통과할수 있겠다 싶었다.

 

그렇게 비트마스킹으로 0~9 등장 여부를 저장.

그리고 O(N^2) 이 아닌, 관점을 틀어서 두 값을 or연산했을 때의 비트상태가 실제로 존재할 수 있는지 체크하였다.

(i, j) 순서쌍 고려하지 않아서 처음에 1틀.

그러다가 이후에 상태가 같을 때 예외처리를 해주어서 AC를 받았다.

 

이문제도 개인적으로 KUPC div1 A~G 꿀잼 탑 중 하나라 생각.

풀고 난 후 이거 무조건 riroan 형이 냈다... 싶었고, 역시나 이 문제는 riroan 형이 냈다고 한다 ㅋㅋㅋ

 

G번

G번도 다들 맞왜틀 엄청 하거나 H로 패스하는 모습이 보였다.

그래서 이문제는 사실 맞출거라는 기대를 하지 않고 도전해보았다.

근데 답이 잘 안보였다. 그렇게 좀 고민하다가...

일단 No가 되는 케이스들을 쭉 정리하자! 싶어서 No가 될만한 것들은 앞에서 예외처리 다 해주었다.

 

그리고 특정 숫자가 반드시 뒤쪽에 존재해야되는 케이스가 보이기 시작.

그래서 B가 주어질 때, 맨앞부터가 아닌 맨뒤부터 스캔하기 시작했다.

맨뒤부터 스캔했을 때, 갑자기 Bi값이 변하면 그 숫자는 해당 인덱스의 뒤쪽에 존재해야됨을 깨달은 후에는 감탄하면서 코드를 작성하기 시작. 나머지 숫자들을 어떻게 할까... 조금 고민하다가 걍 작은순으로 놓든 큰순으로 놓든 상관없다는 걸 깨닫고 queue에 쌓아두었다가 이후에 쭉 나열해주었다.

 

그리고 믿음의 제출! 다른분들은 막 수십번 틀리고 그랬는데, 다행히 1번에 AC!

 

이 문제는 riroan 아니면 dldyou가 냈겠다 싶었다. 누가 냈더라?

 

 

H번

G번 맞춘 후, E번으로 돌아가서 E번 맞왜틀 후 AC받은 후에 시도해본 문제.

투포인터 아니면 펜윅트리를 이용한 inversing count겠다 싶었다.

좀 더 후자일거 같았는데, 일단 펜윅트리랑 세그먼트트리를 내가 다 까먹었다ㅋㅋㅋㅋ

 

그래서 투포인터로 좀 고민해보고 안되면 접자... 싶었다.

그리고 아무리 해도 안되길래 걍 특별상 노릴 겸 런타임에러, 컴파일에러 코드를 내고 대회 끝!

 

나중에 알고보니 fenwick tree 이용하는 문제가 맞다 하더라. 

---

결과

4등인데, 내 위에 한분이 휴학생이어서 비공식참가자였다.

그래서 나는 은상을 받게 됐다!

 

그와중에 delena0702 양학한게 눈에 띈다.

역시 내친구 믿고있었다고~~ 1등이 내친구라는 자부심 ㅋㅋ

 

와~ 10만원이다! 출제 안하고 참가하길 잘했다~

 

사실 처음에는 수상권은 커녕, 중간 이상 등수도 하지 못할 것이라 예상했었다.

대회 시작한 후에 프리즈 전 스코어보드를 봤을 때 나는 5~6등 정도였기 때문에 동상 정도를 예상했다.

 

그런데 프리즈 이후에 E, G를 맞춘게 좀 컸고, 내 위에 한분이 휴학생인게 결정적으로 다가와 은상을 받게 됐다.

 

대회 문제들도 꿀잼이었다.

이번에는 KUPC 역사상 처음으로 백준 오픈컨으로도 열렸고 div1, div2로 나뉘어서 진행됐다.

그래서 그런지 운영진 및 출제진분들이 엄청나게 고생하는 게 느껴졌다. 그리고 그렇게 고생한만큼, 문제 지문 퀄리티나 문제 자체의 퀄리티가 높은게 느껴졌다. 고생했다 아루야.

 

뿌듯해서 인스타에 자랑 좀 했다 ㅋㅋ

 

아 아직 나 PS 감 안죽었네!

너무 기뻤던 하루였다.