ps 대회 후기 (11) 썸네일형 리스트형 2024 KAIST 14th ICPC Mock Competition 문제 출제 후기 조금 늦었지만 이번 카이스트 가을대회에 출제한 문제들의 비하인드를 이야기해보자 한다. 1. Same segment원래 골드 문제를 위한 문제였다. 가볍게 풀 수 있는 문제를 생각하기 위해서 익숙한 토픽들을 여러 개 훑는 중에 "주어진 구간 몇 개의 합이 자연수 K로 같은 음이 아닌 정수의 수열"이라는 토픽이 떠올랐다. 포함관계에 있는 구간이 없으면 그리디하게 앞에서부터 K/0을 채우면 되고, 포함관계에 있는 구간이 존재한다면 두 구간의 차집합에 0을 채우면 되는 아주 쉬운 문제였다. K가 답에 영향을 미치지 않는다는 아이디어도 괜찮아서 다항시간 풀이를 떠올리면 문제를 풀 수 있도록 N 이 문제를 발전시키기 위해 포함관계에 있는 두 구간의 차집합에 0을 채우는 과정을 더 빠르게 할 수 없을까 생각했지만, .. 2024 KAIST 14th ICPC Mock Competition 풀이 A. Automata Embedding더보기1. $f(i+1) \leq f(i)+1$이는 kmp failure function의 특징 중 하나이다. $S[1...f(i+1)] = S[i+1-f(i+1)+1...i+1]$이라면 $S[1 ... f(i+1)-1] = S[i+1-f(i+1)+1 ... i]$이기 때문이다. 2. $f(i)$와 $i$를 잇는 화살표들을 평면 위에 그릴 수 있다는 것과 동치인 것은, 구간 $[f(i), i]$들을 정점으로 하고 두 구간이 겹치지만 포함관계에 없는 경우 간선으로 이은 그래프가 이분그래프인 것이다.pf) 각 화살표를 위에 그리면 그룹 1, 아래에 그리면 그룹 2라고 하자. 같은 그룹에 있는 화살표들은 겹치면 안 되고, 이는 구간으로 만들어진 그래프에서 두 구간이 겹치지.. $\prod_{i=1}^N(R_i-L_i+1)$개의 트리 출제 후기 이번에는 UCPC에 문제를 성공적으로 출제했다. 문제가 만들어진 과정을 알아보자. 문제 출제처음에는 쉬운 플래티넘 문제를 만드려고 했다. 플래티넘 문제는 대회중에 많은 사람들이 풀고, 대회가 끝나고도 많은 사람들이 풀어서 좋다. 세팅하기도 쉽고, (기하 문제나 실수 문제를 내지 않는 이상) 검수하기도 쉽다. 단점은 대회의 승패를 가르는 문제가 아니라는 것과, 나중에 문제를 돌아봤을 때 문제 출제에 대한 뿌듯함이 줄어든다는 것이다. 하지만 나는 문제를 만들 당시에 2개의 어려운 문제가 있었기 때문에 무난한 문제를 만들고 싶었다. (2문제는 런 봄대회에 출제되었다) 처음에 생각한 문제는 LFIS 와 같이 exponential하게 증가하는 조건을 주고 특정 수열의 길이가 logN 이하라는 성질을 이용해서 푸는.. One, Two, Three 출제 후기 2024년 1월 2일에 군대를 가게 되었다. 군대에 가게 되면 대학생이 아니게 되니 대학생 대회들에 멋진 문제를 내서 대학생들에게 풀리겠다는 생각으로 훈련소와 후반기 교육을 하면서 문제들을 만들게 되었다. One Two Three는 ainta님의 문제 스타일에 영향을 받은 문제이다. 신탁, 하나 둘 셋, 점 연결하기, comparing plants를 풀면서 인위적이지 않은 설정들에서 재미있는 관찰들을 추가하면서 문제를 풀어나가는 것이 재미있었다. 특히 신탁이라는 문제를 풀면서 하나의 시행을 다양하게 변환하면서 점점 문제를 풀어나가는 과정이 인상깊었다. 그래서 나도 ainta님처럼 간결한 문제를 만들고 싶었다. 점 연결하기, 돌 가져가기 문제들을 보면 길이 N의 수열을 주고 적당한 시행을 줘서 문제를 완성.. 2023 icpc 본선 후기 I를 잡고 호다닥 짜서 맞았다. J가 스코어보드에서 풀리길래 팀원에게 풀어보라고 넘기려고 했는데 문제 설명해주다가 풀이가 떠올라서 짰다. 그리고 2시간 반동안 맞왜틀을 했다. 맞왜틀하면서 코드를 간결하게 하기 위해서 110줄의 코드를 80줄의 코드로 줄였다. 줄이는 과정에서 혹시 모르기 때문에 계속 제출을 했고, 8틀을 적립했다. K가 11 이상의 소인수를 가질 때에 답이 0이 아니라는 것을 너무 늦게 깨달았다. 맞고 나니까 시간이 30분 남았다. 올해 대회장에서 맞왜틀하는 경우가 너무 많다.그래도 맞왜틀하는 동안 팀원들이 문제를 잘 밀어줘서 덕분에 풀 문제들은 다 푼 것 같다. 팀원들 고마워요~ 시간이 좀 남았으면 C, K, L 보는 거였는데 아쉽다. 문제 출제하기 오늘은 여태까지 출제한 문제들에 대해서 문제 출제 과정을 알아볼 것이다. 고등학생 때 플래티넘 열심히 풀던 시절에 문제를 만들고 싶었지만 문제를 하나도 만들지 못했던 과거의 나를 생각해보면 처음 문제 만드는 것이 가장 어려운 것 같다. 그래서 문제를 처음 만드는 사람들에게 조금이나마 도움이 되고자 내가 문제를 만들었을 때 어떠한 방식으로 문제를 만들게 되었는지 써보겠다! 옛날에 만들어서 조금 까먹었을지도... 최신순으로 적어보자. 카이스트 가을대회이때 4문제 냈다. 각각 어떻게 풀었는지 적어보자.1. HLD이 문제는 Heavy Light Decomposition 이라는 알고리즘에 대해서 생각하다가 나온 문제이다. HLD는 트리를 여러 개의 체인으로 쪼개서 하나의 path 최대 2logN개의 체인으로 쪼개.. 2023 icpc 예선 후기 평소와 같은 팀(maruii, kimjihoon)과 함께 예선 대회에 참가했다. 본선에 진출하는 팀의 수는 예선에 참가하는 팀의 수와 비례하는데, 이번에 카이스트에 참가하는 팀이 늘어나서 예선은 안정적으로 통과할 수 있을 것이라고 생각했다. 풀리는 대로 풀겠다는 마음으로 예선에 임하게 되었다. 대회가 시작하고 문제를 보기 시작했다. ICPC 예선에는 쉬운 문제 3개가 한글로 되어있다는 경험을 지난 예선때 했기 때문에 이번 예선에서는 한글 문제 3개를 풀고 시작하기로 했다. C D G가 한글 문제였다. 가장 처음 읽은 문제가 G인데, 분모가 N 이하인 기약분수 중 K번째 분수를 출력하라는 문제였다. 예전에 검수하면서 페리 수열을 사용할 일이 있어서 분모가 N 이하인 모든 기약분수를 개수에 선형으로 정렬하는.. 2023 ucpc 본선 후기 UCPC 본선에 "김앤장" 팀으로 출전했다. 팀원들은 나, 김지훈(etyu), 장보규(maruii)이다. 요즘 열심히 CCO도 밀고 현대 모비스 대회도 쳐서 감이 나름 살아있다고 생각해서 ucpc 전에 특별히 ps 연습을 안 했다. 팀연습은 했어야 하나 싶기도 한데 평소에도 대회 전에 특별히 연습을 안해서 그냥 안 했다. 대회 전날에 일찍 자려고 노력했지만 체스를 두느라 새벽 5시에 자버렸다. 아침 8시 반에 일어났음에도 불구하고 컨디션이 괜찮았다. 평소에도 4시에 자서 그런 듯하다. ucpc는 문제 퀄리티가 항상 좋으니까 재미있는 문제 풀 생각에 신이 났다. 대회 장소에 도착하니까 평소에 온라인으로만 보던 사람들을 볼 수 있어서 좋았다. 잠깐 돌아다니다가 세팅을 시작했다. 대회 장소가 SK 판교 사옥이.. 이전 1 2 다음
