7월 2 ~ 4주차 PS 정리

주로 UCPC 2020을 위해 팀원들이랑 공부한거랑, 일주일에 한번씩 도는 dlwocks31과의 1:1 세션에서 푼 문제들이다.

 

BOJ 8903, ICPC Daejeon Regional 2011 D번 "Equipment" (장비)

난이도 : Solved AC Platinum 3

최대화해야 하는 지표가 5개뿐임을 관찰하자. 또한, $\binom{n}{k}$ 개의 조합을 모두 볼 필요가 없는데, $k >= 5$ 이면 지표 $a, b, c, d, e$에 대해 각각을 최대화하는 장비 5개를 모두 고를 수 있고 나머지 전부는 무의미하기 때문이다. 즉, $k = 2, 3, 4$ 에 대해서만 풀자. 

$k = 2$ 일 때를 예로 들어 생각해 보면, 5개의 stat 중, 몇개는 장비 1에서, 나머지는 장비 2에서 올 것이다. 만약, "스탯 1, 3, 4는 장비 1에서, 2, 5는 장비 2에서" 라고 미리 정해 버린다면, $n$개의 장비 중 1, 3, 4가 최대인 것과 2, 5가 최대인 것을 골라서 더하면 된다.

이처럼, 5개의 stat을 2개의 장비로 분할해서 나눠주는 방법은 $2^5$개이다. 이를 bitmasking해서, bitmask[14]는 어떤 장비든 하나만 골라서 14=8+4+2이므로 3번, 2번, 1번 스탯을 최대화하는 방법 (0-index) 처럼 생각하면 된다. 이렇게 하면, $O(n+k^5)$에 해결할 수 있으며, $k \leq 4$, $n \leq 10^5$ 이므로 무난하다. 사실은 bitmasking을 쓰면 시간 복잡도가 $k^5$를 맞추기는 쉽지 않고 $2^{5(k-1)}$ 이 좀더 자연스러운데, 이것도 $2^{15}$가 겨우 3만 정도이므로 무난하다. Distinct bit를 골라야 한다는 점에 주의. 예를 들어, 17과 1을 최대화할 수는 없다 (0번 최적화가 겹치므로)

---

BOJ 9276, CTU Open contest 2013 "Fence Orthogonality"

난이도 : Solved AC Platinum 3

BOJ 번역명 "채소 보호"

$N$ 개의 점이 주어질 때, 이 점들을 모두 덮는 최소 둘레의 직사각형을 찾는 문제.

우선, $N$개의 점을 생각하는 대신 이들의 convex hull 만을 생각해도 된다는 것이 자명하다.

그다음은, 직사각형의 한 변이 이 convex hull의 한 변에 맞닿았을 때가 최소임을 이용하여, Convex hull의 각 변 $l$ 에 대해 $l$과 $l$에 수직인 방향으로 직사각형을 만든다면 그 상/하/좌/우 위치가 어때야 하는지를 $O(n)$ 에 벡터의 내적/외적으로 판정하면 된다.

그게 최소임을 아는 방법은...사실 난 잘 모르겠고, 믿음으로 코딩해서 맞긴 했는데 뭔가 증명이 있는것 같다. 삼각함수를 열심히 써서 덧셈정리로 식정리 매드무비를 찍는거 같아서 던지기로 했다.

---

BOJ 10849, GCPC 2015 "A Journey to Greece"

난이도 : Solved AC Platinum 3

정점 수만개 크기의 그래프가 주어지고, 이중 반드시 밟아야 하는 점 $p \leq 15$개가 주어진다. 0번에서 시작, $p$개의 점을 모두 밟고 돌아오되, 딱 한 번 택시를 타고 원하는 점에서 원하는 점까지 $t$ 시간에 이동할 수 있을 때, 어떤 정해진 시간 안에 돌아올 수 있는지 묻는 문제.

정점이 15개밖에 없다면 이 문제는 TSP로, Bitmask DP를 이용해서 $O(p2^p)$에 풀 수 있다. 

정점이 수만개라고 해도, 실제로는 나머지 정점을 별로 상관이 없다. 이 문제를 TSP로 바꾸기 위해 필요한 것은, $p_i$에서 $p_j$로 가는 거리인데, 이 거리는 같은 정점을 여러번 밟지 말라고 한적이 없으므로 항상 최단거리만 이용해서 이동해도 된다. 즉, $p$에 들어있는 정점들에 대해 모두 Dijkstra 를 이용해서, $p_i \to p_j$ 최단경로 행렬을 구한 다음, 이 위에서 TSP를 Bit DP로 풀면 된다.

택시의 존재 때문에, 함수를 약간 고쳐서 택시를 아직 타지 않은 경우와 이미 탄 경우로 나누어서 돌면 된다. 유의할 점은, 쉽게 코딩하기 위해 정점을 2배로 늘리면 TSP가 시간안에 안들어오기 때문에 그런 트릭을 쓰기 어렵다는 것 정도? 사실 그냥 구현해도 비교적 Straightforward 하다.

---

BOJ 16123, 대구과학고 2018 "Dgeu-Learning"

난이도 : Solved AC Platinum 2

대략적인 문제 설명을 하자면, 무방향 가중치 그래프에서, Q(A, B) = A에서 B로 가는 경로들 중, '경로에 포함된 가중치의 최솟값'을 최대화하였을 때 그 가중치라고 정의한다. 이 쿼리를 빨리 처리하는 문제.

LCA를 이용해서 잘 할 수 있다고 하는데, 나는 Parallel Binary Search를 이용하는 방법을 생각해서 구현했다. 각각의 쿼리들을 쭉 늘어놓고, 값이 $x$ 이하인 간선만 써서 두 점 $A, B$ 사이의 경로가 존재하게 할 수 있는지를 Disjoint set을 이용하여 쉽게 할 수 있다. 여기에 Parallel Binary Search를 적용하여, 모든 쿼리를 한번에 절반씩 범위를 줄일 수 있다. 전체 복잡도는 $A =  1e9, N, Q = 2e5, M = 5e5$일 때, 한번 미는데 $O(M \alpha(M) + N \log N)$ 시간이 들고, 이를 $\log A$ 번 해야 하므로, 대략 $O(N \log N \log A)$ 정도 된다. 짜보니까 생각보다 느리던데 왜인지 잘 모르겠다. :( 

---

BOJ 8872, IOI 2013 Day 1 Problem 1 "Dreaming"

난이도 : Solved AC Platinum 2

BOJ 번역명 "빌라봉" (정식 번역이 따로 있는데, 어쩌다 BOJ에 저렇게 등록되었는지 모르겠다)

별도 포스팅 예정.

---

+ CERC 팀연습, UCPC (이것도 각각 별도로 포스팅할것 같다)