Syphon의 자기개발 일지

입대를 한 2021년 이후 전반적으로 competitive programming 공부를 하지 않은 것이 사실이다. 그럼에도 불구하고 대회를 참여해서 손해볼 것은 없기에 SCPC를 다시 한번 신청하였다. 결과적으로 망하기는 했는데(나는 SCPC류의 well-known 문제들을 풀어내는 능력보다 이전 Google Code Jam 느낌의 ad hoc 문제에 더 강하다 - 그냥 공부를 안해서 그럴지도) 기록은 남긴다. 사실 요즘 기록을 남기는 것을 많이 소홀히 하고 있다. 대회 기록이 밀림은 물론이고, 평소 열심히 쓰던 일기와 강의 평가 또한 밀렸다. 뭔가 기록을 하자니 밀린 기록들부터 다 작성해야 할 듯한 기분이고, 또 기록을 퀄리티 높게 하려고 하다보니 부담이 되어 자꾸 미루게 된다. 그래서 그냥 앞으로는 ..

군대 사지방에서 짬내서 열심히 긁은 예선. 중간에 점호받으러 가고... 폰으로 보고.. 외출도 나가면서 디버깅 할 시간이 많이 부족했다. 특히나 익숙하지 않은 C++을 써야해서 디버깅이 너무나도 오래 걸렸다. 라운드 2가 걱정된다. 현재 더 이상 문제들을 열람할 수가 없어서 기억에 의거해 상당히 대충 작성하는 후기가 될 예정이다. 1. 개미 개미들을 stable sort하면 된다. 2. K 등분 맞웨틀. 총합을 k등분 한 값을 기준으로, k의 정수배인 지점들은 potential split point들이다. DP 느낌으로, 이러한 potential point마다, 그 위치보다 앞서 온 split point까지의 경우의 수를 다 더해주면 된다. 사실 코드 다시 열어보기도 싫어서 설명도 대충 했다. 끝까지 점..

대회를 너무 캐주얼하게 진행했더니 캐주얼하게 망해버렸다. 원래 같았으면 대충 윗공대에서 치렀을텐데, 두 대의 카메라를 동원해 Zoom에 접속해 컴퓨터 화면과 팀원들이 나오도록 설치해 둔 상태로 대회를 진행해야 한다는 번거로운 온라인 대회 규칙 때문에 서울대입구역의 토즈 스터디룸을 빌려 대회를 진행하게 되었다. 대회에서 시도한 문제 순서대로 정리하겠다. I: Project Teams 스코어보드를 참고해 제일 쉬운 문제인 I를 먼저 잡았다. 문제를 다 읽기도 전에 정렬 후 앞뒤로 짝지어주는 well-known 풀이가 떠올랐다. E: Cycle Game 그래프를 그려나갈 때, 사이클이 생기는 시점을 감지하면 된다. 읽자마자 UFDS를 떠올렸으나, 문제를 잘못 이해한 Nyso가 다른 방법으로 시도한 후 한번 실..

대학을 와서 치는 두번째 SNUPC다. 작년, 나의 레이팅 상승 추이를 보며, 2020년에는 SNUPC의 Division 1에 출전할 수 있으리라 생각했던 것이 기억난다. 안타깝게도 1년 사이에 큰 폭의 실력 상승은 없었고, Division 1에 출전할 용기 또한 없었다 ㅋㅋ 요즘 들어 CP에 조금 소홀해진 듯한 느낌이 드는데, 이런 와중에 치른 대화라 그런지 작년의 열심은 없었던 것 같다. 코로나의 여파로 인해 집에서 치뤄서 그런가..? 이제 시작한 2학기에는 작년처럼 조금 더 열심히 실력을 업그레이드할 수 있으면 좋겠다. 암튼 대회 스타트..! A: 수면 패턴 구현 문제다. 파이썬으로 퍼솔 달성!! B: 단어 개수 세기 역시 구현 문제다. 파이썬으로 퍼솔 달성!! C: 넴모넴모 2020 이진탐색 기본..

Round 1, 2에 참여했으나 완전 망해버려서 기록을 남기기 귀찮아졌다. 그래도 참여를 하긴 했다는 기록 차원에서 연습지를 올린다:

더 늦어지기 전에 본선 후기를 남긴다. 이미 뒷북 후기... A: 전단지 돌리기 짧은 문제 description이었지만, 거리 $D$ 이하의 모든 노드에 전단지를 돌릴 수 있다는 말이 무슨 뜻인지 이해가 되지 않아 반복해 여러 번 읽어야 했다. 결국 가볼 필요가 없는 노드들을 찾아내기만 한다면, 나머지 노드들을 전부 포함하는 subtree의 모든 간선 길이를 왕복으로 지나가게 되므로, 간단하게 정답을 구할 수 있다. 갈 필요가 없는 노드들을 제외하는 동시에 필요한 간선 길이들을 세기 위해서, 모든 leaf node로부터 출발하여 루트(출발지)를 향해 거꾸로 올라오며 거리 $D$ 이상 올라온 시점부터 간선들의 길이를 더해주기 시작했다. 같은 간선을 두번 세 주지만 않으면 된다. 파이썬으로 풀었다. B: 던..

올해는 예선/본선 모두 온라인으로 진행되는 까닭에 조금은 아쉽지만, 그래도 1년 전 [Syphon/Nyso/MathAmp] 팀이 출발하게 된 계기가 된 UCPC이기에 올해도 기대와 함께 출발하였다. 올해 우리의 팀명은 이다. 너무 잘 지은 것 같아서 만족스럽다. 솔직히 말해 작년의 팀명은 기억하기에는 너무 길었던 것 같다. 대회 시작 전부터 백준 서버가 터져서, 본선 진출 조건이 "4 솔브 팀 전부"로 완화되었다. 아쉽게도 긴장감이 다소 떨어지는 대회가 되어버렸다. J를 제외한 문제 5개는 대회 문제지를 받아본 3시부터 6시 반까지 3시간 반 동안 설렁설렁 풀었다. 결국 J는 내가 밤에 구현하여 제출했다. 그럼 이제 문제 설명 시작..! A: 수학은 비대면강의입니다 Trivial. 보자마자 나와 Math..

드디어 Round 2다. 세번의 기회가 주어졌던 Round 1과는 달리 이제는 단판승부이기 때문에 정말 정신 차리고 필요한 모든 연료(?)까지 옆에 비축해두고 대회를 시작했다. 1. Incremental House of Pancakes There are two stacks of pancakes. The height of each stack is given as input. You are to serve customers. The $i$th customer requires $i$ pancakes to be served. $i$ pancakes will be given from the stack of higher height. If the two stacks are of equal height, the le..

작년의 코드잼에서는 Round 1A를 놓치고, 1B를 늦게 참여해서 결국 1C에서 779등으로 Round 2 진출에 성공했었다. 올해는 지난 1년간의 발전이 있었던 만큼, 첫 Round 1 대회에서 진출을 기대해보았다. Round 1A 링크이다. 1. Pattern Matching Question Wildcard character인 *가 포함된 문자열들이 입력으로 들어온다. 입력으로 들어온 모든 패턴들을 동시에 만족시키는 문자열을 찾아 출력하면 된다. Solution 예제 입력에 주어진 패턴들이 모두 *로 시작하고 알파벳으로 끝나는 형식(e.g. *abc)이길래, asterisk 기준으로 문자열을 분할했을 때 가장 앞과 뒤에 남는 'prefix'와 'suffix'에 우선 집중하기로 했다. Suffix 만..

코드잼이 돌아왔다는 뜻은 나의 CP 커리어가 만 1년이 되었다는 뜻이다 ㅎㅎ QF 라운드 링크이다. 1. Vestigium 구현 문제이다. 2. Nesting Depth 구현 문제까지는 아니지만 거의 시키는대로 괄호를 열고 닫고 하면 끝난다. $O(n)$ 풀이. 3. Parenting Partnering Returns Worker 2명 스케줄링 문제. 그리디 문제로 유명한 well-known이다. 4. ESAb ATAd 여기서부터는 머리를 좀 썼다. 일정한 규칙으로 변화하는 길이 100의 이진문자열의 현재 상태를 맞추면 끝난다. 제한 조건은 쿼리 150번 이내이다. 쿼리란: index를 물어보면, index의 값을 알려준다. 변화의 규칙은: 쿼리 10번마다 네개의 변화 방법 중 하나가 랜덤하게 일어난다...