qwerasdfzxcl의 ps 블로그 qwerasdfzxcl의 ps 블로그

레드 후기를 올릴 때 IGM을 찍으려면 1년은 걸릴 줄 알았는데 생각보다 빨리 찍게 되었네요. 딱히 적을 말도 없고 아마 코포 레이팅 관련 글은 이게 마지막일 것 같으니 (누텔라를 찍으면 얘기가 달라지지만) 제가 코드포스 IGM을 찍을 때까지 어떻게 공부했는지 정리하려고 합니다. 1. Virtual Contest로 많은 대회를 풀어보기 코드포스 레이팅을 올리는 가장 효과적인 방법은 최대한 많은 코드포스 대회에 참가하는 것입니다. 코드포스에서 제공하는 기능인 virtual contest로 과거 대회를 풀어보면 실제 대회랑 유사한 환경에서 문제를 풀 수 있고, 코드포스에 자주 나오는 유형을 파악하거나 전략을 세우는데 매우 큰 도움이 됩니다. 저는 오렌지이던 시절에 Div.1 contest들을 virtual ..

대회 시작 전 대회가 시작하기 전, 노트북을 점검하는 시간에 코드블럭을 키고 몇가지 코드를 짜서 돌려봤습니다. NYPC는 휴리스틱 문제가 자주 나오는 편이기 때문에, 난수를 생성하는 mt19937을 짜서 돌려봤는데 무슨 이유에선지 컴파일 에러가 났습니다. 그래서 그냥 rand()를 쓰기로 하고 일단 넘어갔습니다. 다른 코드도 몇 개 짜봤는데 range-based for가 작동하지 않고 컴파일 에러가 났습니다. 알고보니 코드블럭 기본 세팅이 c++98로 되어있었고, 스태프의 도움을 받아 c++11로 컴파일을 할 수 있게 되었습니다. 버전을 올리니 mt19937도 정상적으로 돌아갔고, 별 문제가 없었습니다. 0:00~0:30 NYPC 본선은 일반적으로 난이도 순으로 문제가 나오기 때문에, 쉬운 1번과 2번은..

NYPC 2021 예선이 종료되었습니다. 작년에 비해 문제 퀄이 많이 떨어진 것 같아서 개인적으로 좀 아쉬웠습니다. 문제마다 그냥 처음 떠오른 풀이를 바로 짜다보니 세그먼트 트리를 이용한 풀이가 좀 많습니다. 다른 쉬운 풀이가 있을 수 있으니 다른 블로그 풀이도 참고하면서 보면 좋을 것 같습니다. 1일차 1번) 계단 문제 요약 1층부터 $M$층까지 있는 건물의 $F$층에서 시작해서, 계단을 한 층 오르는 것을 $N$번하려고 할 때 엘리베이터를 타는 횟수의 최솟값을 구하는 문제입니다. 풀이 더보기 $M$층까지 올라간 후, 엘리베이터를 타고 1층으로 가는 것을 반복하는 것이 최적의 전략입니다. $M$, $N$이 크기 때문에 식을 세워서 풀면 $O(1)$에 답을 계산할 수 있습니다. 코드 더보기 #includ..

8/1에 코드포스 레드, 8/16에 solved.ac 루비를 찍었는데 여름학교랑 오렌지컵 운영 때문에 시간이 없어서 이제 글을 올리게 되었다. (사실 핑계고 귀찮았음) 코드포스 레드는 Round 732에서 핵을 엄청 많이 성공해서 두 자리 등수를 찍고, Round 736에서 수학 문제들만 나와서 ABC + D1을 1시간 23분만에 다 풀어서 갈 수 있었던 것 같다. 아직 레드를 안정적으로 유지할 실력은 안 되는 것 같고 앞으로 연습을 많이 해야할 것 같다. 8/16에는 클9를 따면서 루비를 가게 되었다. 링컷 비빔밥 + 오렌지컵 문제로 레이팅 N점을 날먹하긴 했는데 뭐 어쨌든 루비를 찍었다. 언젠가 IGM 후기나 solved.ac 마스터 후기를 올릴 수 있게 되면 좋겠다.

오늘 고등부 KOI 2차 대회가 있었습니다. 시험을 보기 전엔 은 중상위권 정도만 했으면 좋겠다고 생각했는데, 점수가 생각보다 잘 나와서 기분이 좋네요. 0:00 ~ 0:20 일단 1번을 열었는데, 1번이 생각보다 어려웠습니다. 가능한 동심원 크기의 최댓값은 루트(N)에 비례한다는 사실과, dp 전처리를 잘 섞으면 O(N루트N) 정도에 풀 수 있습니다. (N = A+B) 0:20 ~ 0:57 어려웠던 1번과 달리, 2번은 풀이가 바로 보였습니다. 1번 정점의 가중치를 x라고 두면 dfs를 돌면서 나머지 정점들의 가중치를 x에 대한 식으로 나타낼 수 있고, 이분그래프가 아닌 케이스들만 처리를 해주면 쉽게 해결이 가능합니다. 이분그래프인 경우, x의 값을 마음대로 설정할 수 있는데, 최솟값을 찾기 위해 저는..

어제 저녁 7시부터 12시까지 지인들이랑 CEOI 2019 Day 1 셋 버춸을 돌았다. 버춸 돌기 전에 내가 너무 못할까봐 걱정이 많이 됐는데 생각보다 점수가 엄청 잘 나와서 기분이 좋다. 특히 3번문제는 백준에서 다1문제인데(Dynamic Diameter) 운이 좋아서 풀이를 빨리 찾을 수 있었다. 참고로 플랫님은 3번 73점까지 풀이를 아는데 구현을 안 했다고 하고, 이환님도 73점 아는데 귀찮아서 안 했다고 한다 ㅋㅋ; 0:00 ~ 0:13 난이도 순서를 모르기 때문에 문제를 차례대로 읽으면서 나이브 + 인간섭태를 차례로 긁고, 그나마 쉬워보이는 문제에서 더 점수를 긁는 방식으로 전략을 세웠다. oj.uz에도 한국어 지문이 없어서 영어 지문을 읽어야 했지만 문제 내용이 간단해 빠르게 읽을 수 있었..

백준에 있는 "단계별로 풀어보기" 문제들을 모두 풀었다. 작년 9월쯤부터 c++로 PS 공부를 하기 시작하면서 단계별로 풀어보기로 공부했는데 드디어 모든 단계를 전부 해결했다. 대충 난이도를 정리해보면 1~10: 기본 문제들 (언어 연습용) 11~24: 기본적인 알고리즘들 (여기까지만 알아도 코포 딥2C~D까지 풀 수 있음) 25~40: 조금 더 어렵지만 많이 쓰이는 알고리즘들 (여기까지만 알아도 코포 퍼플~오렌지 수준의 지식은 된다) 41~46: 약간 십덕인 알고리즘들 (icpc 같은 곳에는 나오지만 플로우, fft처럼 oi범위가 아닌게 많다) 47~50: 어려운 알고리즘 공부하고 싶은 십덕들을 위한 단계 단계마다 기본문제랑 연습문제들이 들어있어서 알고리즘 공부하기 좋은 것 같다.

퍼플->오렌지는 4달이나 걸렸는데 오렌지->찐렌지는 1달 밖에 안 걸렸다 ㅋㅋ 최근 본 코포 전부 퍼포가 찐렌지~레드 수준으로 나와서 3번만에 찐렌지를 찍을 수 있었던 것 같다. 특히 round #718(div1+div2)에서 운 좋게 159등을 해서 한 번에 115점이 올랐다. 아직 내 실력으로 레드 가는건 무리일 것 같지만 최대한 노력해봐야겠다.