전체 글
-
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에도 한국어 지문이 없어서 영어 지문을 읽어야 했지만 문제 내용이 간단해 빠르게 읽을 수 있었..
-
백준 18779 풀이 (Help Yourself)문제풀이 2021. 6. 15. 14:02
문제 링크: https://www.acmicpc.net/problem/18779 18779번: Help Yourself (Platinum) Bessie has been given $N$ ($1\le N\le 10^5$) segments on a 1D number line. The $i$th segment contains all reals $x$ such that $l_i\le x\le r_i$. Define the union of a set of segments to be the set of all $x$ that are contained within at least one segment. www.acmicpc.net 문제 설명: [1, 2N] 구간에 선분이 N개 있을 때, 2^N개의 모든 선분의 부분집..
-
백준 9208번 풀이 (링월드)문제풀이 2021. 5. 28. 15:10
문제 링크: https://www.acmicpc.net/problem/9208 9208번: 링월드 링월드는 반지모양으로 이루어진 나라이다. 이 나라에는 도시가 m개 있고, 편의상 0, 1, 2, ... m-1로 번호가 매겨져 있다. 이 도시는 반지모양을 이루고 있으며, 0, 1, 2, m-1, 그리고 다시 0 순서이다. www.acmicpc.net 풀이) 일단 그래프 모델링을 해봅시다. 이분그래프 G = (A, B)를 생각할건데, |A| = N, |B| = M이고, i번째 구간이 [j, k]일 때, A에서 i번째 점을 B에서 [j, k] 점들과 연결합시다. 이렇게 하면 문제가 "그래프 G에서 A를 덮는 매칭이 존재하는가?"로 변하게 됩니다. 이 상태로 segment tree를 이용하여 문제를 해결할수도 ..
-
단계별로 풀어보기 올솔일기장 2021. 5. 23. 14:10
백준에 있는 "단계별로 풀어보기" 문제들을 모두 풀었다. 작년 9월쯤부터 c++로 PS 공부를 하기 시작하면서 단계별로 풀어보기로 공부했는데 드디어 모든 단계를 전부 해결했다. 대충 난이도를 정리해보면 1~10: 기본 문제들 (언어 연습용) 11~24: 기본적인 알고리즘들 (여기까지만 알아도 코포 딥2C~D까지 풀 수 있음) 25~40: 조금 더 어렵지만 많이 쓰이는 알고리즘들 (여기까지만 알아도 코포 퍼플~오렌지 수준의 지식은 된다) 41~46: 약간 십덕인 알고리즘들 (icpc 같은 곳에는 나오지만 플로우, fft처럼 oi범위가 아닌게 많다) 47~50: 어려운 알고리즘 공부하고 싶은 십덕들을 위한 단계 단계마다 기본문제랑 연습문제들이 들어있어서 알고리즘 공부하기 좋은 것 같다.
-
백준 8481번 풀이 (Generator)문제풀이 2021. 4. 29. 02:53
http://boj.kr/8481 8481번: Generator Your program should print the content of the file geni.out to the standard output. Your output may contain additional white space at the end of some lines or at the end of the file. www.acmicpc.net solved.ac 티어: D3 다3짜리 구현(+규칙찾기)문제다 ㅋㅋ; 계속 플래~다이아만 밀다보니까 머리도 아프고 문제도 잘 안 풀려서 잠깐 휴식하면서 구현 연습하려고 이 문제를 풀기 시작했는데 절반쯤 풀었을때부터 후회되기 시작했다. ㅋㅋㅋㅋㅋ 이 문제 풀지 마세요 풀이) 데이터 분석을 하기 ..
-
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) 같은데 맞는지 잘 모르겠다. (얼마인지 알면 댓글로 알려주세요.) 참고..