$$\newcommand{\Z}{\mathbb{Z}} \newcommand{\R}{\mathbb{R}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\N}{\mathbb{N}}\newcommand{\C}{\mathbb{C}} \newcommand{\oiv}[1]{\left] #1 \right[} \newcommand{\civ}[1]{\left[ #1 \right]} \newcommand{\ad}[1]{\text{ad}(#1)} \newcommand{\acc}[1]{\text{acc}(#1)} \newcommand{\Setcond}[2]{ \left\{\, #1 \mid #2 \, \right\}} \newcommand{\Set}[1]{ \left\{ #1 \right\}} \newcommand{\abs}[1]{ \left\lvert #1 \right\rvert}\newcommand{\norm}[1]{ \left\| #1 \right\|}\newcommand{\prt}{\mathcal{P}}\newcommand{\st}{\text{ such that }}\newcommand{\for}{\text{ for }} \newcommand{\cl}[1]{\text{cl}(#1)}\newcommand{\oiv}[1]{\left] #1 \right[}\newcommand{\interior}[1]{\text{int}(#1)}$$

본문 바로가기

알고리즘 문제풀이/대회 후기, 문제풀이

(15)
ICPC Preliminary 2020 새 팀인 Swift Turtwig로 2020 ICPC 인터넷 예선에 참가했다. 이번에 워낙 진출티켓이 적고 서울대 팀들이 터무니없이 잘하기 때문에 진출은 어려웠지만, 나름 재밌게 공부하면서 할 수 있었다. 작년 팀이랑은 또 다른 느낌인 듯. Phase -1. Preperation 팀연습은 두번 했다. NCPC 2018이랑 NWERC 2015를 돌았고, NWERC는 아직 블로그 후기는 다 쓰지 않았는데 (문제수가 많다..ㅋㅋ) NWERC 연습은 굉장히 잘 돌았다. 3시간 셋이면 골드 3-4문제와 플레 하나, 잘하면 두개 정도까지는 쳐낼 수 있을 것 같아 보였다. 팀노트는 kactl repository에 기반하여, 작년보다 훨씬 extensive하게 작성했다. geometry 같은 라이브러리가 없어서 실패하..
2020 SNUPC 후기/풀이 SNUPC 2020 Division 2에 참가해서 3등상 (7등) 을 했다. 작년과 성적에는 큰 차이는 없지만 작년보다 Div2 참가자들의 인적인 풀이 더 상승한 것 같으므로 (= 대회가 더 추해진 것 같으므로) 그럭저럭 괜찮았다고 생각한다. 3시간 동안 아무것도 못한건 매우 아쉽지만 풀이를 듣고 보니 그럴만했었다고 생각한다. 대회가 로딩 되자 마자 문제 탭을 쭉 켰는데, A는 Tab이 crash해버려서 B를 먼저 읽었다. B는 구현 문제인데, 일단 대차게 한번 틀리고 시작했다. Frustration은 오늘도 계속된다... 그래도 초반 문제들의 난이도가 어렵지 않으므로 빠르게 제정신을 되찾..는거까진 아니고 그러려고 노력할 수는 있었다. 빠르게 A를 다시 켜서 A를 먼저 풀었다. A. 수면 패턴 AC :..
SCPC 2020 2차 예선 후기 멘탈이 갈려나가고 이래저래 바빠서 후기를 계속 미루고 있었다. 역대급으로 망하고 힘들었던 대회인 듯... 오전 9시 - 오후 9시라서 힘든것도 60% 정도 있지만, 꼭 그것만은 아니다. 3번 문제의 Whining이 역대급이므로 나머지 문제에서의 Whining을 줄이고 (3번 제외) 건조한 느낌으로 써보려고 한다. 다만, 내가 문제를 푸는 과정을 최대한 그대로 따라갈 생각이다. 즉, 한번에 바로 풀이로 접근하기보다는 '이런 과정으로 생각해 봤다' 라는 느낌. 1번 : 실력 맞추기 문제 설명 : $n \leq 300,000$ 명의 팀원이 있는 두 팀이 있고, 이들에게 각각 실력값 $A_i$ 와 $B_i$가 주어져 있다. 이들을 Matching한다. $A_i$ 를 $B_{f(i)}$ 에 매칭했을 때, $\su..
2020 SCPC Online Round 1 : 1-4번 풀이 SCPC (삼성전자 대학생 프로그래밍 대회) 를 처음 참여했다. 약간 K-코드잼 느낌? ㅋㅋㅋㅋㅋ 24시간 동안 치뤄지는 1차 예선을 거쳐서 적당한 인원이 2차에 진출하고, 다시 온라인 2차 예선으로 본선에 진출하는 시스템인데, 뭔가 여러가지로 시스템상 (다른 PS 대회에 비해) 독특한 점이 많다. - 1차 예선은 Scoreboard를 볼 수 없고, 커트라인도 알려져 있지 않다. 정말 푼 사람수 보고 적당히 자르는 건가..? - 부분점수를 받기 위해 버퍼해제 같은걸 직접 해야 한다. 이건 사실 왜인지 잘 모르겠다. - 찾아보니 작년이나 재작년 예선에서는 휴리스틱 문제가 하나씩 나왔던것 같다. 올해는 없던데... 아무튼, 1번부터 4번까지는 만점을 받았고, 5번은 몇시간동안 코딩 사투 끝에 장렬히 전사했다..
2020 UCPC 본선 후기 Little Piplup (어쩌면) 마지막 official한 대회가 생각보다 아쉬운 성적으로 마무리되었다. 내 트롤링이 좀 있었지만, 그래도 스스로 변호를 좀 하자면 트롤링이 페널티를 좀 깎아먹긴 했어도 등수가 별로 바뀌진 않았을 것이다. 항상 그렇듯 대회 끝나고 적는 후기. 이 글을 보는 사람이 solved.ac를 모를 가능성은 별로 없지만, 본문 중 '난이도'를 롤 티어처럼 언급해놓은 것은 모두 solved ac 기준이다. -1. 대회 준비 + 팀연습에 대해 작년 본선은 놀라운 난이도의 대회로, 4문제가 대회 중 풀리지 않는 기염을 토했다. 원래는 작년 대회와 비슷한 난이도의 셋으로 팀연습을 하려고 했는데, 2019 UCPC는 13문제중 solved 기준 5루비 3다이아로, 이정도 난이도의 셋은 Pe..
2020 UCPC 인터넷 예선 후기 / 풀이 * 대회 종료 시간으로 예약 작성하였습니다 :) * 작년의 Little Piplup 그대로 올해도 UCPC에 참여했다. 올해로 3번째 참여하는 UCPC고, 이 팀으로 참여하는 공식대회도 꽤 많았지만 나름 각별한 느낌이 좀 있는데, 팀원들의 병특 시작 등으로 (아마도) 이 3명 그대로 참여하는 마지막 대회일 수도 있어서.... 앞으로도 PS는 같이 할 것 같지만, ICPC에서 휴학생이 참여할 수 없다는 점이 크다. DHdroid의 병특 결과에 따라 내 ICPC 팀도 결정될 예정. 후기 느낌으로 쓰면서 풀이를 Discuss하는 글이기 때문에, 문제 풀이만을 확인하기에는 별로 좋지 않다. 생각하는 흐름 그대로 적는게 나중에 봤을때 제일 기억에 남는거 같다. ㅋㅋ -1. Due to technical issue..
Google Codejam 2020 Round 1B 1, 2번 풀이 Codejam은 구글에서 진행하는, 기업 대회 중에서는 가장 규모도 크고 알려진 PS 대회로 수만명이 참가하는 대회이다. Qualification Round에서 기본적인 코딩 실력 정도로 거르고, 그 인원으로 Round 1을 세 번 치르는데 세 번 중 한 번만 1500등 안에 들면 Round 2에 진출할 수 있다. 1A에서 진출한 사람은 1B를 응시하지 못하므로 1A, 1B, 1C로 갈수록 진출하기는 조금 쉬워진다고 할 수 있겠다. Round 1A같은경우는 아침이라 말려서 (라는 핑계로) 2천등 정도 해서 진출에 실패했고, Round 1B는 어제 새벽에 319등이라는 기대 이상의 좋은 성적을 거두고 진출했다. 푸는데 성공한 두 문제의 풀이를 적으려고 한다. Editorial 과 거의 같지만, 1번의 아이..
Google Hash Code 2020 후기 Google Hash Code 2020 (https://codingcompetitions.withgoogle.com/hashcode) 후기. ICPC 같이 뛰었던 팀 Little-Piplup에 현재 병특 중인 dlwocks31을 영입(?) 해서 4인팀인데, Dlwocks31이 3명보다 구현이 훨씬 좋아서 확실히 팀 전력이 보강된 느낌이 들었다. 4인 팀으로 ICPC 같은걸 뛰었으면 더 잘 했을것 같기도... Team Little Piplup : Coffeetea Diordhd Dlwocks31 Gratus907 Hash code는 일반적인 ICPC / OI 류 대회와는 다르게, NP 문제 같은 뭔가를 가지고 최대한 많은 점수를 긁는 방식으로 치뤄지는 대회이다. 유사한 걸로는 Marathon Match 같..