문제풀이
-
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,..
-
백준 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를 이용하여 문제를 해결할수도 ..
-
백준 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짜리 구현(+규칙찾기)문제다 ㅋㅋ; 계속 플래~다이아만 밀다보니까 머리도 아프고 문제도 잘 안 풀려서 잠깐 휴식하면서 구현 연습하려고 이 문제를 풀기 시작했는데 절반쯤 풀었을때부터 후회되기 시작했다. ㅋㅋㅋㅋㅋ 이 문제 풀지 마세요 풀이) 데이터 분석을 하기 ..
-
백준 18799번 풀이 (이상한 편집기)문제풀이 2021. 3. 26. 18:14
문제 링크: www.acmicpc.net/problem/18799 18799번: 이상한 편집기 스택에 전체 문자열을 추가한 뒤, 한 번 출력하는 것이 최적이다. www.acmicpc.net 문제를 보고 dp문제 느낌이 나길래 dp로 풀었습니다. 제한이 2000이기 때문에 O(N^3)으로는 안 풀리고, O(N^2logN)으로 풀기 위해 slope trick을 사용했습니다. 근데 이걸 slope trick이라 해도 되나? 풀이) 처음에 naive한 dp 풀이를 만든 후, 최적화하는 방식으로 풀이를 설명하도록 하겠습니다. 입력으로 들어온 문자열을 str, str의 길이를 n이라 하겠습니다. O(N^4) Solution 다음과 같은 dp배열을 정의합시다. dp[l][r]: 마지막으로 붙여넣은 문자열이 구간 [l..
-
백준 13515번 풀이 (트리와 쿼리 6)문제풀이 2021. 3. 17. 17:08
문제 링크: www.acmicpc.net/problem/13515 13515번: 트리와 쿼리 6 N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다. 가장 처음에 모든 정점의 www.acmicpc.net 다음 2가지 쿼리를 처리하는 문제입니다. 1 i. i번 정점의 색을 바꾼다. 2 u. u와 연결된 정점의 개수를 출력한다. (단, 두 정점이 연결되었다는 것은 두 정점을 연결하는 경로상의 모든 정점의 색이 같다는 것을 의미한다.) 이 문제의 정식 풀이는 Tree DP를 heavy-light decomposition으로 최적화하는 것이고, sqrt decomposition을 통해 오프라인 ..
-
백준 20535번 풀이 (Good bye, BOJ 2020! G번)문제풀이 2021. 1. 3. 20:45
굿바이 boj 2020 대회에 참가하지 못해서 혼자 문제를 풀어보던 중 G번을 접하게 되었습니다. 문제를 보고 풀이가 금방 떠올랐는데 제 풀이가 알려져 있는 풀이들과는 다른 방식이여서 블로그에 올리게 되었습니다. (이 풀이는 정해보다 복잡한 방법이기 때문에 이렇게 푸는건 추천하지 않습니다. 그냥 이렇게도 풀 수 있구나 하고 재미로 봐주세요.) 문제에 대해 간략하게 설명하자면, 쿼리마다 몇개의 점 v_1, v_2, ... , v_k가 들어오는데 가능한 모든 점의 순서쌍 (v_i, v_j)에 대해 lca의 깊이의 합을 계산해서 출력하는 문제입니다. (단, i