2023 SUAPC summer 후기

22222222222

2023 SUAPC summer에서 2등했습니다.

팀원은 ICPC까지 같이 나갈 팀 (정용진,김건우,김태윤) - (playsworld16, coconut99, ystaeyoon113)입니다

팀명은 열심히 정하다가 SCC_Sinchon Coding Champions로 정했어요 아마 ICPC때는 글자수 제한이 있어서 SCC긴 한데 SCC_SinChon Coders로 바꿀듯

이번에 강팀들이 많이 나온다는걸 알고 꽤 긴장하고 있었는데, 생각보다 엄청 잘하는 팀도 있었고 생각보다 말린 팀도 보였습니다. 스코어보드 열어보기 전에도 누가 1등인지 예측이 전혀 안됐던 셋이였던 것 같습니다. 개인적으로 예상하던 순위도 많이 뒤집혀서 놀랬고 1등팀이 월파팀이라 그런지 역시 강하네요

많이 아쉽지만 ICPC 이전에 부족한 점을 알았고 공부해서 ICPC때 좋은 결과를 얻을수 있으면 좋겠습니다

 

 

일단 푼 문제들 리뷰

처음 시작할때 문제 배분은 4/5/5 - (용진/건우/태윤) 순으로 했습니다. 늘 그렇듯이

 

L - 나의 FIFA 팀 가치는 ? (00:04) - ystaeyoon113

간단한 구현입니다. 딱봐도 후원문제 같길래 먼저 손댔습니다.

 

G - 개발자 지망생 구름이의 취업 뽀개기 (00:08) - coconut99

간단한 문제인 것 같습니다. 건우가 풀었습니다.

 

K - 케이크 두 개 (00:27) (+1) - ystaeyoon113

간단한 기하 문제고 두 점을 잇는 직선을 만들면 됩니다. m,n을 헷갈려서 페널티를 하나 쌓았습니다. 그리고 출력할 때 살짝 귀찮은 ? 유리수를 정수 연산으로만 다루는 것에 익숙하지 않으면 어려울 것 같습니다.

 

J - 큰 수 만들기 게임 (00:38) - playsworld16

제 영역에 있는 문제인데 제가 K번을 푸느라 바빴고 푼 팀이 있길래 용진이한테 봐달라고 해서 용진이가 풀어줬습니다.

 

H - 탭 UI (00:45) - ystaeyoon113

후원문제인 것 같고 문제 이해가 조금 어려웠지만 약간의 케이스워크를 하면 되고, 숫자가 0.5나 정수로만 나올 수 있어서 모두 2배씩 하고 문제를 풀면 정수 연산으로만 해결됩니다. 근데 세자리에서 반올림하라 그랬나? 아무튼 그래서 의아했는데 낚시였다고 합니다.

 

I - 폭탄 피하기 (00:47) (+2) - coconut99

건우가 풀어준 문제고 꽤 난이도가 있는 문제인 것 같습니다. 중간에 TLE를 몇 번 받았던 걸로 기억합니다.

 

F - 작곡가 A의 시창 평가 (01:09) - ystaeyoon113

문제에서 하라는 대로 적절한 문자열 알고리즘을 이용해서 처리하면 마지막은 Nim으로 끝납니다. 풀때는 쉬운 문제는 아니라고 생각했는데 지금 돌이켜보면 하라는 바가 분명해서 쉬웠을 수도 있을 것 같습니다.

 

B - 기초적인 문제 (01:22) (+1) - coconut99 

그 뭔 씹 . . . 

진짜 건우가 알고 있었던 내용이라서 뚫어주긴 했는데, 여기서 한 문제 벌었다고 생각했습니다. 역시 영재고는 다르다.. 근데 진짜 이런게 나와서 맞으면 한문제 덤으로 얻어가는거고 아마 건우가 없었으면 걍 버렸을거 같습니다. 선대 중간고사에 나와서 폭사해서 기억에 남았다고 했는데 분명 저도 선대 강의 들었는데 이런거 들어본적도 없습니다. ㅋㅋ

 

D - 디지털 트윈 (01:43) - playsworld16

dp풀이를 떠올리기 어려운 문제는 아닌데, 구현에 상당한 귀찮음이 있는 걸로 알고 있습니다. 용진이가 구현해서 맞아왔습니다.

 

E - 성게 밭 (02:03) - ystaeyoon113

성게박사

문제를 이해하는 데 좀 걸렸고, 문제 조건대로 해석하면 deg>=3인 정점과 아닌 정점으로 나뉩니다. 이걸로 새로운 그래프를 만들수 있는데, 굉장히 흥미로운 statement로 그렇게 만들어진 그래프가 이분그래프라는 조건이 주어집니다. (성게 제철이라서 무슨 같은 수컷끼리는 인접하지 않는다였나 ㅋㅋ)

그래서 거기서 최대한 vertex를 고르면 되고, 이는 이분그래프에서 Independent Set을 구하는 문제이고, Konig's Theorem을 잘 응용하면 이분매칭으로 할 수 있습니다. 아마 제한을 보면은 E*sqrt(V)에 하라는 것 같은데 그래프 만들어지는 것 보면은 E*V에도 될거 같기도 하고..

 

이때부터 스코어보드상에서 쭉 1등에 위치해있었고 그냥 남은 ACMN중에서 2문제만 풀어도 1등은 무난히 하겠다는 생각이였습니다. 그래서 천천히 2문제만 풀어보자라는 생각이였습니다.

 

A - A->B (04:28) - playsworld16

애드혹/구성적 ? 문제였고 이런건 용진이가 잘 해서 그냥 맡겼다가, 살짝 고민하는것 같길래 도와주려다가 제가 별 도움이 안되는 것 같아서 원래 보던 NM으로 돌아갔습니다. 그래도 시간안에 풀 수 있을것 같다고 해서 그냥 믿고 맡겼고 적당히 패턴을 찾아서 맞아왔습니다. 저는 규칙 찾는거 굉장히 못하는데 용진이는 뭔가 IQ 테스트같은거 하면 굉장히 높게 나올 것 같습니다.

 

C - 2048 - Not Solved

일단 얘기해 보면서 풀이 자체는 나왔습니다. state를 52개로 줄일 수 있다는 것도 알았고, 그렇게 해서 행렬을 구성해서 행렬dp를 채우면 된다는 사실도 알았는데.. 문제는 행렬을 채우는 난이도가 상당히 어려운 것 같습니다. 한 1시간 정도 구현을 할 시간이 있었는데 행렬식 내의 계수를 채우는 데 쓰다가 폭사했고 제한도 상당히 빡빡해서 이게 맞냐는 의심과 함께 C번은 코드가 완성되지 않았습니다. 풀이를 몰랐던 것도 아니고 이 문제는 무조건 풀었어야 한다고 생각하는데 상당히 아쉽습니다. 쿠키팀도 아마 C번과 E번에서 말린 것으로 알고 있습니다.

 

N - 북극여우는 괄호를 뒤집어 - Not Solved

사실 저는 여기가 가망 있다고 생각해서 이걸 계속 봤는데 뒤집는 쿼리를 어떻게 처리할지 전혀 모르겠어서 용진이한테 좀 물어봤는데 스플레이 트리 얘기를 해서.. 만약 그게 맞다면 어차피 우리 짤줄 모르니까 걍 틀리자라는 생각이였고, 저는 그래도 쿼리를 처리하는 무슨 lazy한 방식이 있을 것이라는 믿음이 있었지만 아니였고 sqrt decomposition이였습니다. 왤캐 sqrt decomposition은 떠올리기가 어려운지 모르겠어요 ㅠㅜ 아 그리고 스플레이 트리로도 풀수는 있다고 합니다. 조만간 공부해봐야 될듯

 

M - 트리와 케이 - Not Solved

ㅡㅡ

이번 대회에서 가장 분한 문제

이게 뭔 웰논 .. ;

읽자마자 이건 걍 버릴 문제라고 생각해서 버렸고 그리고 계속 유기해왔는데 대회 끝나자마자 lky7674에게 M번 걍 센트로이드 기본형인데 왜 안풀었냐는 연락을 받고 어이가 없었습니다.

이게 뭔 웰논 ... ;  ;

결국 서강대 팀들은 M번을 다들 풀었고 저희는 2등이 됐습니다.ㅋㅋ

그래서 이 대회 이후로 분해서 매일 자기전 센트로이드 문제를 2문제씩 풀었고 급기야 오픈콘에도 난입하고 만다.

 

ㅋㅋ

센트로이드 다시 나오면 진짜 죽여줌. 아 근데 우리팀에서 하드알고리즘 담당은 저한테 좀 지분이 있긴 한데 그냥 제가 풀었어야 된다고 생각합니다. 그래서 ICPC 전까지 미뤄뒀던 토픽들을 좀 보고 들어갈 생각이에요

 

 

 

결론은 2등

1등 상품에 키보드가 있길래 운영진들한테 키보드에 미리 이름 각인좀 부탁한다고 했는데 너무 까불었고 역시 월파팀(Redshift)은 강하네요. 3등에 위치한 서강대 2시드도 너무 잘해서 놀랬고 사실 이 팀이 세다는건 대회 전에도 저는 알고 있었습니다.

 

오히려 쿠키팀(1등하러왔습니다)이 너무 말려서 아쉬웠고 이 팀이 현재로는 가장 센 팀(찐렌지, 오렌지,퍼플)이라고 생각하는데 셋이 안맞았던 것 같습니다. 약간 맞왜틀 당해서 말린 것도 있고.. 아마 ICPC에서는 이 팀은 제대로 실력이 측정될 것 같습니다.

 

가오당 팀은 비교적 최근에 결성된 팀인데, (퍼플,블루,블루)인 팀인데 최근에 만들어진 팀임에도 불구하고 밸런스가 좋은 것 같습니다. 쿠키팀을 넘고 4등까지 한 것 보면 ICPC때도 좋은 결과가 있을 것 같습니다. 

 

그리고 22학번 팀은 이번에 싹다 출제진으로 들어갔고.. 헬문제 ABCMN을 출제했다고 한다.. M번 .. M번 ..

 

그리고 16등에 위치한 뉴비들의유쾌한반란 팀은 연대 특별상을 수상했습니다. 축하합니다!

 

 

 

대회 끝나자마자 동아리 사람들과 고기 먹으면서 문제 욕도 좀 하면서.. 스코어보드도 같이 봤는데 겨울과 비슷한 축제 분위기는 아니였고 분한 사람들이 모여서 신촌연합 뒷풀이에도 참가했습니다. 저는 한 3시간 중에 2시간 57분 정도는 센트로이드 분할 출제자를 술자리에서 괴롭혔던 걸로 기억합니다. 다들 만나서 반가웠어요~~

 

 

그리고 이 팀들을 ICPC에서 다시 만나게 되겠지..

그때는 더 강해져서 돌아올 생각입니다

안녕