일기장
-
KOI 2021 고등부 후기일기장 2021. 7. 25. 19:57
오늘 고등부 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의 값을 마음대로 설정할 수 있는데, 최솟값을 찾기 위해 저는..
-
CEOI 2019 Day 1일기장 2021. 7. 22. 02:44
어제 저녁 7시부터 12시까지 지인들이랑 CEOI 2019 Day 1 셋 버춸을 돌았다. 버춸 돌기 전에 내가 너무 못할까봐 걱정이 많이 됐는데 생각보다 점수가 엄청 잘 나와서 기분이 좋다. 특히 3번문제는 백준에서 다1문제인데(Dynamic Diameter) 운이 좋아서 풀이를 빨리 찾을 수 있었다. 참고로 플랫님은 3번 73점까지 풀이를 아는데 구현을 안 했다고 하고, 이환님도 73점 아는데 귀찮아서 안 했다고 한다 ㅋㅋ; 0:00 ~ 0:13 난이도 순서를 모르기 때문에 문제를 차례대로 읽으면서 나이브 + 인간섭태를 차례로 긁고, 그나마 쉬워보이는 문제에서 더 점수를 긁는 방식으로 전략을 세웠다. oj.uz에도 한국어 지문이 없어서 영어 지문을 읽어야 했지만 문제 내용이 간단해 빠르게 읽을 수 있었..
-
단계별로 풀어보기 올솔일기장 2021. 5. 23. 14:10
백준에 있는 "단계별로 풀어보기" 문제들을 모두 풀었다. 작년 9월쯤부터 c++로 PS 공부를 하기 시작하면서 단계별로 풀어보기로 공부했는데 드디어 모든 단계를 전부 해결했다. 대충 난이도를 정리해보면 1~10: 기본 문제들 (언어 연습용) 11~24: 기본적인 알고리즘들 (여기까지만 알아도 코포 딥2C~D까지 풀 수 있음) 25~40: 조금 더 어렵지만 많이 쓰이는 알고리즘들 (여기까지만 알아도 코포 퍼플~오렌지 수준의 지식은 된다) 41~46: 약간 십덕인 알고리즘들 (icpc 같은 곳에는 나오지만 플로우, fft처럼 oi범위가 아닌게 많다) 47~50: 어려운 알고리즘 공부하고 싶은 십덕들을 위한 단계 단계마다 기본문제랑 연습문제들이 들어있어서 알고리즘 공부하기 좋은 것 같다.
-
PS 일지 (4/7~4/19)일기장 2021. 4. 19. 06:21
숫자 놀이 (BOJ 1187) 푼 날짜: 4/7 solved.ac 티어: D5 풀이: N=2^k이기 때문에 간단한 아이디어로도 풀린다. 일단, N=2일 때는 기우성(홀짝성)이 같은 2개의 수를 고르면 된다. N=2^k (k>=2)인 경우, 수 N-1개를 고른 후, N=2^(k-1)인 경우에서 그 집합에 대해 답을 구해놓는다. 이를 S_1이라 하자. 원래 수들의 집합에서 S_1을 빼고, 방금 했던 시행을 한다. 이 시행을 2번 더 해서 집합 S_2와 S_3를 얻을 수 있고, 이 세 개의 집합의 합들을 2^(k-1)으로 나눴을 때 기우성이 같은 두 집합의 합집합이 답이 된다. 구현은 분할정복처럼 하면 된다. 시간복잡도는 대충 O(3^k) 같은데 맞는지 잘 모르겠다. (얼마인지 알면 댓글로 알려주세요.) 참고..
-
코드포스 오렌지 달성 후기일기장 2021. 4. 10. 18:01
4/3~4/4에 있었던 Round #712(Div.1)에서 3솔하고 256등을 하면서 코드포스 오렌지를 찍었다. 작년 8/2에 처음으로 파이썬으로 프로그래밍을 접하고, 그 이후로 PS에 중독돼서 백준과 코드포스에서 800문제가량을 풀면서 실력을 길렀고, 드디어 오렌지를 찍게 되었다. 코드포스를 시작하고 4번째 라운드(20/10/24)에 블루를 찍었고, 20/12/04에 퍼플을 찍어서 오렌지는 1달~2달 정도 코포하면 바로 갈 줄 알았다. 하지만 내신대비와 학원 등의 이유로 1월에 대회를 한 번도 참가하지 못했고, 그 이후로 보는 대회마다 망하거나 시스텟이 터져버리는 바람에 레이팅이 1950 근처에서 변동이 거의 없었다. 그러다가 최근 두 대회에서 2200~2400 정도의 퍼포먼스가 나왔고, 레이팅이 71..