본문 바로가기

Problem Solving/문제풀이

(45)
[ICPC] Latin America Regional 2017 일부 문제 풀이 A. Arranging Tiles BOJ 15052번: https://www.acmicpc.net/problem/15052 이 문제의 핵심은, 어떤 2개의 다각형을 얼마나 가까이 붙일 수 있는 지 빠르게 계산하는 것입니다. 다각형을 배열하는 순서를 정하고, 그 다각형들에 대해 한 다각형의 x좌표 최댓값이 바로 다음 다각형의 x좌표 최솟값과 같게 배치했다고 합시다. 그렇다면 이 때의 해는 모든 다각형의 x축 길이 합에서, 모든 인접한 다각형 쌍에 대해서 다각형을 얼마나 가까이 이동시킬 수 있는지의 합을 뺀 것이 됩니다. 따라서 우리는 다각형 쌍이 주어졌을 때 이를 서로 붙일 수 있는 최대 길이를 미리 계산해 둔 뒤 가능한 모든 배열에 대해 해 중 최소를 찾아주면 됩니다. 붙일 수 있는 최대 길이를 모두 전..
[BOJ] 15404 Divide and Conquer 문제 요약 $N$개의 정점이 있고, 이 정점을 잇는 스패닝 트리가 2개 있다. 이 두 스패닝 트리의 합집합으로 구성되는 그래프에 대해(간선은 구별된다), $K$개의 간선을 제거하면 그래프를 연결 그래프가 아니도록 할 수 있다. 이 때 $K$의 최솟값을 구하고, 그 경우의 수를 $10^9 + 7$로 나눈 나머지를 출력하면 된다. 문제 풀이 가장 먼저 해야 하는 관찰은 다음과 같다. $K=2$이거나, $K=3$. 증명은 다음과 같다. 임의의 정점에 연결된 모든 간선을 제거하면 그 정점은 다른 정점과 연결되어 있지 않기에, 그래프는 연결 그래프가 아니다. 따라서 $K$는 모든 정점의 degree 중 최솟값보다 클 수 없다. 간선 하나는 정확히 두 개의 정점의 degree를 1만큼 증가시키므로, 모든 정점의 d..
[BOJ] 16910 mex와 쿼리 [문제 링크](https://www.acmicpc.net/problem/16910) 문제 요약 다음과 같은 세 쿼리를 처리해야 합니다. [l,r]에 속하는 모든 자연수를 배열 A에 추가한다. 이미 있는 수는 무시된다. [l,r]에 속하는 모든 자연수를 배열 A에서 제거한다. 없는 수는 무시된다. [l,r]에 속하는 모든 자연수에 대해 있으면 제거, 없으면 추가한다. 각 쿼리를 수행 한 뒤에 이 배열에 없는 수 중 가장 작은 자연수를 찾으면 됩니다. 문제 풀이 일단 문제에서 요구하는 좌표가 크니 좌표 압축을 시도하고 생각합시다. 그 이후 Lazy Propagation 달려 있는 세그로 연산을 처리해주며 특정 구간에 존재하는 수의 개수를 세 주면 됩니다. Lazy 연산 중에 1번 쿼리와 2번 쿼리는 서로 상..
[BOJ] 14591 KUBC League, 17165 Gosu 14591 KUBC League 문제 요약 토너먼트 그래프가 있다. 1번 정점에서 시작해서 모든 정점을 순회하는 단순 경로를 찾으면 된다. 문제 풀이 DFS 스패닝 트리에 의거하여, 그냥 DFS를 1번 정점에서부터 수행 후 마지막부터 출력해주면 된다! 코드 #include #include #include #define all(x) (x).begin(), (x).end() #define endl "\n" #define ends " " #define pb(x) push_back(x) #define fio() ios_base::sync_with_stdio(0); cin.tie(0) using namespace std; typedef long long ll; typedef pair pii; typedef pai..
[BOJ] 13329 Meteor Shower 문제 요약 y>0인 반평면에 다각형들이 있다. 원점에서부터 빛을 쏴서 다각형들을 관측할 때, 어떻게 빛을 쏴도 관측할 수 없는 다각형의 개수를 세서 출력한다. 문제 풀이 이런 류의 문제에서 항상 쓰는 테크닉인 스위핑을 갖고 옵시다. 다만 평소에 쓰는 라인 스위핑이 아닌, 각도 기준으로 스위핑을 진행해야 합니다. 다각형끼리 서로 교차하지 않으므로, 각 다각형을 각도가 가장 작은 점과 각도가 가장 큰 점을 이어주는 선분으로 바꿔줘도 답에는 영향이 없습니다. 그렇다면 문제는 n개의 선분이 주어졌을 때 완전히 가려지는 선분을 구하는 문제로 환원됩니다. 모든 선분의 끝 점을 각도 순으로 정렬합니다. (https://koosaga.com/97) 선분의 시작 지점이 들어올 때 집합에 선분을 추가하고, 종료 지점이 들..
[ICPC] ICL 2016 (GP of Tatarstan) 후기 & 잡설들 Intro 고려대학교 2020 ICPC 팀이 한 팀 결성되었습니다! ryute, 20학번, 퍼플 seyun, 19학번, 오렌지 cheetose, 군인, 오렌지 cheetose님이 저에게 팀 하자는 제안을 주셨고, seyun님도 cheetose님한테 팀 하자는 제안을 드린 것 같아서 영문도 모른 채 3인 팀이 구성되게 되었습니다. 저는 오렌지 둘의 버스를 탈 수 있으니 대만족이고, 현재 음료수와 간식을 배달하고 분배하는 업무에 숙달되기 위해 오늘도 열심히 노력하고 있습니다. 입학하기도 전에 버스팀이 생기는 사람이 있다? 서로 얼굴을 본 적이 없다는 이유로 만나서 밥을 먹기로 했습니다. cheetose님이 밥 먹기 전에 셋을 하나 돌자고 하셔서 솔직히 불안했습니다. 오렌지 2명 사이에 끼어서 노솔브 하면 어..
[BOJ] 10264 Particle Swapping 문제 링크: https://www.acmicpc.net/problem/10264 문제 요약 평면 그래프에서 다음과 같은 쿼리를 처리해야 한다. 어떤 두 정점이 주어질 때, 각 정점에서 반대 정점으로 이동하는 개체 2개가 있다. 이동 중 개체 사이 거리의 최솟값이 가장 최대가 되도록 배치했을 때 거리의 최솟값을 구한다. 단, 경로에서는 간선은 따지지 않고 오직 정점만을 따진다. 문제 풀이 그래프를 적절히 바꿔서 모델링해보자. 정점 A에서부터 출발하는 개체와 정점 B에서 출발하는 개체의 위치를 순서쌍으로 표현해볼 수 있다. 만약 그렇다면 이동 중 개체 사이 거리의 최솟값은, 순서쌍을 정점으로 두고 순서쌍 사이의 상태 전이가 가능한 경우를 적당히 간선으로 이어줬을 때 (A,B)에서 (B,A)로 이동하면서 찾아..
[BOJ] 1396 크루스칼의 공 문제 링크: https://www.acmicpc.net/problem/1396 문제 요약 간선에 가중치가 존재하는 그래프가 존재하는데, 다음과 같은 쿼리를 빠르게 처리해야 한다. 정점 x에서 시작해서 y까지 이동하려고 할 때, 이용해야 하는 간선의 최소 가중치는 얼마인가? 그리고 x에서부터 그 가중치로 방문할 수 있는 정점의 개수는 몇 개인가? 문제 풀이 두 가지 풀이가 존재한다. (1) 병렬 이분 탐색 한 쿼리에 대해서 다음과 같은 문제를 해결한다고 생각해보자. 정점 x에서 시작해서 k 이하의 가중치를 갖는 간선만을 사용할 수 있을 때, 정점 y에 방문할 수 있는가? 또한 이 때 정점 x로부터 방문할 수 있는 정점의 개수는 얼마인가? 이 문제를 해결하는 방법은 쉽다. 말 그대로 k 이하의 가중치를 가지..