문제풀이
-
PS 일지 (1/3 ~ 1/23)일기장 2023. 1. 24. 17:07
BOJ 17728 (Walls) 각 방벽에 대해 계산하는 쿼리 문제라고 생각하자. 방벽의 이동 경로는 왼쪽 -> 오른쪽 -> 왼쪽 -> 오른쪽 -> ... 과 같은 형태로 나타난다. 시작점이 INF 또는 -INF일 때 경로에서 꺾이는 점을 관리하면 문제를 해결할 수 있다. 방벽의 길이가 증가하면서 꺾이는 지점의 삭제가 일어나고, 이는 연결리스트와 같은 형태로 관리해줄 수 있다. pq를 사용하면 삭제되는 원소를 빠르게 구할 수 있고, 세그를 이용해서 답을 계산할 수 있다. BOJ 17667 (Virus Experiment) 풀이가 다양하다. 풀이 1: https://qwerasdfzxcl.tistory.com/24 (타잔 알고리즘과 비슷하다.) 풀이 2: 풀이 1과 비슷한데, scc를 유파로 전부 들고 있..
-
2022 IOI 국대교육 2주차 (06/27 ~ 07/01)일기장 2022. 7. 3. 15:33
06/27 학교 수업시수 채워야 해서 불참했다. 06/28 BOJ 8243 (POI 12/13 Arch) / O 왕이 1번 노드에서 시작해서 트리 위를 움직이는데, 왕이 도착한 노드는 색칠이 된 상태여야 한다. 현재 왕의 위치는 알 수 있지만, 왕이 어디로 갈지는 모른다. 하루에 칠할 수 있는 노드의 최대 개수를 $X$개라고 할 때, 조건을 만족하도록 할 수 있는 $X$의 최솟값을 구해야한다. $X$에 대한 이분탐색 + 트리 dp로 해결가능하다. BOJ 11746 (Landscape Improved) / O 돌 $N$개를 바위들 위에 적절히 쌓아서 꼭대기의 높이를 최대화해야 한다. 답에 대한 이분탐색을 한다고 가정하고, 각 x좌표에 대해 그 지점에 꼭대기가 있을 경우 돌이 몇 개 필요한지를 세그트리 + ..
-
2022 IOI 국대교육 1주차 (06/21 ~ 06/24)일기장 2022. 6. 25. 02:39
1. 국대교육은 아침연습 3문제, 오후실습 3문제로 구성되어있다. 글에 적힌 순서대로 아침연습 123번, 오후실습 123번이다. 2. O는 대회 시간 내로 AC를 받은 문제, △는 업솔빙을 한 문제, X는 업솔빙 안 한 문제이다. 06/21 이 날은 학교 수행 때문에 교육을 빠졌다. 06/22 BOJ 22491 (Repairing) / X 파이프와 밸브가 여러 개 있고, 밸브를 적절히 잠궈서 끝점에 물이 못 흘러들어가게 해야 한다. 이때, 물이 안 흐르는 구간의 길이의 합을 최소화해야 하고 이 값을 출력해야한다. 대충 그래프를 만들었다고 생각하면 끝점에서 bfs 같은걸 돌려서 가장 가까운 밸브들을 전부 잠근 다음 시작점에서 물을 흘려보내서 계산을 하면 될거같다. AC를 받은 사람이 없어서 맞는지는 잘 모..
-
IOI21 Keys 풀이문제풀이 2022. 6. 17. 23:07
어떤 점 x에서 시작해서 방문할 수 있는 점의 집합을 A_x라고 합시다. A_x의 값이 최솟값이라면, A_x의 임의의 원소 y에 대해 A_y = A_x를 만족합니다. 이러한 집합 A_x들을 "최소 집합"이라고 합시다. 구하고자 하는 집합은 최소 집합의 합집합입니다. dfs를 다음과 같은 규칙에 따라 돌려봅시다. 현재 dfs tree를 만들고 있는 상황이라고 생각하고, dfs(v)가 실행중이라고 합시다. v의 서브트리의 원소를 S_v라고 할 때, 1. S_v와 S_v의 여집합을 연결하는 간선 중, S_v에서 얻은 key를 이용하여 갈 수 있는 간선을 차례로 확인합니다. (주의: S_v는 원소가 계속 추가됩니다.) 2. 그 간선을 타고 가서 나온 정점 w를 방문한 적이 없다면 dfs(w)를 호출합니다. df..
-
NYPC 2021 본선 1519부문 3번 풀이 (BOJ 23347)문제풀이 2021. 11. 1. 12:58
대회장에선 섭태 1만 긁고 접근도 못했는데 백준에 올라왔길래 업솔빙을 했습니다. 서브태스크 2와 3의 풀이를 urd05님에게 듣고 100점 풀이를 찾았습니다. https://www.acmicpc.net/problem/23347 23347번: 수열 연산 모든 수가 $1$ 이상 $K$ 이하의 수로 구성된 수열이 있다. 이 수열에 다른 연속한 부분수열을 삽입하거나 삭제하는 연산을 원하는 만큼 할 수 있다. 단, 이 수열은 길이가 $M$ 이상이어야 하며, 수열 www.acmicpc.net 실제 대회에서의 서브태스크는 다음과 같습니다. 서브태스크 1: $2M \le K$ 서브태스크 2: $M, K, |C|, |D| \le 6$ 서브태스크 3: $M, K, |C|, |D| \le 10$ 서브태스크 4: $M, K,..
-
NYPC 2021 예선 풀이 및 후기일기장 2021. 8. 26. 22:33
NYPC 2021 예선이 종료되었습니다. 작년에 비해 문제 퀄이 많이 떨어진 것 같아서 개인적으로 좀 아쉬웠습니다. 문제마다 그냥 처음 떠오른 풀이를 바로 짜다보니 세그먼트 트리를 이용한 풀이가 좀 많습니다. 다른 쉬운 풀이가 있을 수 있으니 다른 블로그 풀이도 참고하면서 보면 좋을 것 같습니다. 1일차 1번) 계단 문제 요약 1층부터 $M$층까지 있는 건물의 $F$층에서 시작해서, 계단을 한 층 오르는 것을 $N$번하려고 할 때 엘리베이터를 타는 횟수의 최솟값을 구하는 문제입니다. 풀이 더보기 $M$층까지 올라간 후, 엘리베이터를 타고 1층으로 가는 것을 반복하는 것이 최적의 전략입니다. $M$, $N$이 크기 때문에 식을 세워서 풀면 $O(1)$에 답을 계산할 수 있습니다. 코드 더보기 #includ..
-
백준 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를 이용하여 문제를 해결할수도 ..