본문 바로가기

Problem Solving/문제풀이

(45)
USACO 2020 January (Gold) 풀이 Intro 원래 USACO 참여할 생각이 없었는데 브론즈만 밀어야지 실버만 밀어야지 하다가 결국 골드를 키게 되었다. 중간에 뇌절파티를 많이 해서 예상보다 시간이 매우매우 많이 걸렸다. 개인적인 난이도는 2->1->3이라고 생각하나, 증명 없이 뇌를 비우고 푼다면 1번이 2번보다 더 쉬울수도 있다는 생각을 해본다. 세 문제 모두 플5에서 플3 정도의 수준이라고 생각한다. 1. Time is Mooney (time) 문제 요약 정점 1000개, 간선 2000개인 그래프가 있다. 각 정점은 1000 이하의 가중치를 가지고 있는데, 정점을 방문할 때 마다 그만큼의 점수를 얻는다(여러 번 방문해서 점수를 얻을 수 있다). 단, 사용한 간선 개수를 $t$라고 하면 주어지는 1000 이하의 정수 $c$에 대해 $c..
[BOJ] 13309 트리 문제 링크: https://www.acmicpc.net/problem/13309 13309번: 트리 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N과 Q (1 ≤ N, Q ≤ 200,000)가 주어진다. 다음 N-1개의 줄의 i번째 줄에는 정점 i+1의 부모 정점을 나타내는 정수 a가 주어진다 (1 ≤ a ≤ N). 다음 Q개의 줄 각각에는 세 정수 b, c, d가 주어진다. d = 0이면, b와 c를 연결하는 경로가 존재하는 지 묻는 질의만 수행함을 의미한다. d = 1이면, b와 c를 연 www.acmicpc.net 문제 요약: 정점이 20만개인 트리가 주어진다. 이때 어떤 정점 a, b를 잇는 경로가 있는 지에 대한 쿼리 20만개에 응답..
[CF] 100551A Connect and Disconnect 문제 링크: https://codeforces.com/gym/100551/problem/A 문제 설명: 정점 $n$개로만 이루어진 그래프에 $k$개의 쿼리가 주어지는데, 쿼리는 +, -, ? 이렇게 세 종류가 있다. +는 존재하지 않는 간선 하나를 추가하고, -는 이미 존재하는 간선 하나를 삭제한다. ?는 현재 그래프의 컴포넌트 개수를 출력한다. $n$과 $k$는 둘 다 30만 이하이다. 문제 풀이: - 쿼리가 오직 + 와 ?만 들어온다면...?Union-Find Tree를 이용해서 정점들을 쉽게 합쳐줄 수 있고, 시간복잡도는 $O(k alpha(k) )$가 되겠다. - 제거 쿼리가 추가되었을 때 만약에 정직하게 모든 쿼리들을 다 처리해 준다면...?Union-Find Tree를 그대로 첫번째 풀이에 적..
[USACO] 2018 January Contest (Silver) 풀이 [15589] Lifeguards (Silver)문제 링크: https://www.acmicpc.net/problem/15589문제 설명: $N$ 마리의 소가 1부터 10억 까지의 단위 시간 사이의 임의의 구간을 덮고 있다. 이 소들 중 한 마리를 제거할 때, 여전히 덮혀 있는 구간의 길이를 최대화 하는 문제이다.문제 풀이: $N$의 범위가 10만밖에 되지 않으므로, 사용하는 좌표 역시 20만개를 초과하지 않는다. 따라서 정렬 및 좌표압축 후 스위핑 비슷하게 단 하나의 소만으로 덮혀 있는 구간과 하나 이상의 소로 덮혀 있는 구간의 길이를 prefix sum으로 계산해 주고, 이를 바탕으로 각 소를 한 번씩 제거해주면서 기존에는 덮혀 있었지만 이제 덮혀지지 않는 구간의 길이를 $O(1)$로 계산해 줄 수 ..
[BOJ] 10067 수열 나누기 문제 링크: https://www.acmicpc.net/problem/10067 문제 요약음이 아닌 정수 $n$개로 이루어진 수열이 있다. 이 수열을 $k+1$개로 나누어야 하는데, 한 번 나눌 때 마다 새로 나누어진 각 부분의 원소의 합을 곱한 것 만큼의 점수를 얻을 수 있다. 이 때 얻을 수 있는 점수의 최댓값과 그 순서를 구하는 문제이다.$2 \leq n \leq 100,000$, $1 \leq k \leq \min(n-1,200)$ 이다. 풀이 과정 가장 먼저 해야 할 관찰은 어느 순서로 수열을 자르던 간에 최종적으로 얻는 점수에는 변함이 없다는 것이다. 만약 어떤 부분을 2번 잘라 3개의 수열로 나누고, 이 수열의 합을 각각 $S_1$, $S_2$, $S_3$ 이라고 하자. 만약 왼쪽을 먼저 자..
[BOJ] 1693 트리 색칠하기 문제 링크: https://www.acmicpc.net/problem/1693문제 요약$n$개의 정점으로 구성된 트리가 있다. 이 트리를 $1$에서 $n$번까지의 색깔로 칠하는데 $k$번 색깔로 칠하는 데는 $k$만큼의 비용이 든다. 인접한 정점을 같은 색으로 칠하지 않으려고 할 때 최소 비용을 구하는 문제이다.풀이 과정이 문제를 푸는 데 가장 핵심적인 아이디어는, 트리를 색칠하는 데 많아 봐야 $\lg n$개의 색깔만이 필요하다는 것이다. 맨 처음에는 직관적으로 이 성질을 생각했는데, 좀 더 생각해보고 증명을 해 볼 수 있었다. 증명은 아래에!만약 트리를 색칠하는 데 필요한 색깔이 생각보다 적다는 것을 알게 되면, 다음과 같은 동적계획법을 생각해 볼 수 있다. $DP[a][c]=$ $a$번째 정점을 색..
[BOJ] 15977 조화로운 행렬 2018 KOI 고등부 3번이다. 정해는 2d segment tree래서 그렇게 짰는데 사실 set+이분탐색이 훨씬 짧고 깔끔하고 빠르고 메모리 사용량도 적다고 한다. 하여튼 "정해"는 첫째 열 기준으로 정렬한 다음 둘째 열과 셋째 열에서 2d segment tree를 이용해서 pair의 LIS를 구해주면 된다. 메모리 사용량이 문제고 $200000 * (lg200000)^2$ 개만큼 노드 잡았더니 MLE 뜨길래 적당히 줄여서 해봤더니 맞았다. 왜 맞는지 진짜 모르겠는데 실제로 돌리면 같은 노드도 여러번 탐색하고 그래서 최악의 경우에도 노드 개수가 많이 넘어가지는 않는다고 한다. 시간은 5초 제한에 낭낭하게 3.7초 나왔다. (...) 시간복잡도는 $O(n lg n^2)$, 공간복잡도도 마찬가지.다시는 ..
[BOJ] 11377 열혈강호 3 이분 매칭이 변형된 형태로 나는 에드몬드-카프 알고리즘을 사용해서 풀었다.k명은 일을 하나씩 더 할 수 있다는 조건이 있기 때문에, source를 bridge 역할을 하는 s1과 s2에 연결한 다음 각각의 용량을 n과 k로 해주었다. 따라서 s1이 모든 사람이 하는 하나의 일, s2가 k명이 할 수 있는 추가 작업을 뜻하게 된다. 그리고 s1과 s2를 모두 사람을 표현하는 정점에 용량 1로 이어주고, 마찬가지로 사람과 일 사이에도 문제에서 주어지는 대로 용량 1인 간선을 연결해주었다. 마지막으로 일과 sink에도 용량을 1로 하여 이어주었다. 이렇게 네트워크 모델링을 하면 성공적으로 AC를 받을 수 있다. 네트워크 플로우 넘 어렵다 ㅠㅠ 1234567891011121314151617181920212223..