9월 1주차 PS 정리 (8.31 - 9.6)

Rounds

- SCPC 2020 Round 2 : 별도 포스팅 (쓰고 있다). 크게 망했고 정말 힘들었다. ㅋㅋ;;; 

- Codeforces Round 666 (Division 1) : 별로 재밌는 문제는 없었다. AB는 쉽고, C번은 너무 케이스가 많아서... +51점 (2051)

- AtCoder Beginner Contest 177 :  F번을 어떻게 풀지 전혀 감을 못 잡았다. 흠... +37점 (1921)

- ICPC 신촌 Summer Camp Open : SCPC 망하고 다음날이기도 하고, 각종 과제가 있어서 조금만 하고 나올 생각이었는데 아무튼 힐링하면서 8문제를 풀고 3시간 만에 도망쳤다.

 

 

문제/풀이

(8월 중에 푼것도 포함되어 있다)

 

---

BOJ 19559, Baltic Olympiad of Informatics 2020 Graph

난이도 : Solved AC 기준 Platinum 2

재밌게 풀었던 문제. OI 문제가 역시 재밌긴 하다.

간단히 설명하면 그래프가 주어지고, Edge는 가중치가 1이거나 2인데, 노드마다 실수값을 할당해서 모든 에지에 대해서 양쪽의 노드 가중치의 합이 에지의 가중치와 같게 하는 문제이다. 답이 여러 개라면 가중치 절대값의 합을 최소화.

어떤 노드들은 가중치가 반드시 특정 값으로 확정되어야 한다. 대표적으로, self-loop의 경우, 가중치가 1인 self-loop이 있다면 반드시 가중치가 0.5여야 한다. 또한, 하나의 노드가 확정되면 그 노드가 포함된 connected component에 대해 전부 가중치가 확정되게 된다. 만약 multi-edge가 있다면, 두 에지의 가중치가 다르면 어차피 불가능하고 같으면 하나만 있는 것처럼 생각해도 된다. 따라서, simple connected graph에서만 풀면 된다.

임의의 정점 하나를 잡고 가중치를 $x$로 부여하자. 그러면 그 옆 정점은 필요에 따라 $2 - x$ 또는 $ 1- x $ 이고... 이런 식으로 모든 정점에 $x$를 이용한 가중치를 부여할 수 있고 모든 가중치는 $x + k$ 또는 $-x + k$ 형태가 된다.

다시, 간선을 하나 잡고 양쪽의 $x$ 계수를 확인하여, 둘다 +거나 -이면 $x$의 값을 확정할 수 있고 이를 다시 전파해 줄 수 있다. 어떤 간선도 $x$를 확정지어 주지 못한다면, 절대값의 합을 최소화하면 된다. $\sum \abs{k_i-x}$ 형태의 식이 있을 때 이를 최소화하는 $x$의 값은 $k$들의 중간값임이 알려져 있다.

코드 [링크]

---

BOJ 5977, USACO US Open 2011 Gold Mowing the Lawn

난이도 : Solved AC 기준 Platinum 2

Deque를 이용한 Dynamic Programming 최적화를 연습하는 문제. 별로 어렵지 않은데, 이 테크닉 자체가 약간 Overrated 되었다는 개인적인 생각이 있다. 난이도만 보면 Convex Hull Trick과 비슷한 급인데, 정말 그런가? Convex Hull Trick이 이론상으로나 구현상으로나 훨씬 난이도가 높다고 생각한다. 

역시 간단히 설명하면, $a_1, a_2, \dots a_n$ 수열의 합을 취하되, 연속한 $k$개를 골라서는 안 된다. 

$D_i$를 $i$번까지 볼 때의 최적값이라고 생각하면, 우리가 원하는 식은 다음과 같음을 알 수 있다. 

$$D_i = \max_{i - K \leq j \leq i} D_{j-1} + \sum_{k = j}^{i} a_k$$

합 부분은 Prefix sum array $P_i$를 미리 관리하면 쉽게 해결할 수 있다. 이를 그대로 Evaluate 하는 것은 $O(nk)$ 시간이 걸리지만, 이를 $O(n)$ 으로 줄이는 테크닉으로 deque 최적화가 알려져 있다. 이를 이용하면 된다.

언젠가 deque 최적화에 대한 글을 쓸수도 있고...근데 이미 내가 안 써도 좋은 글들이 많이 있다.

참고로, deque 최적화를 하지 않아도 multiset을 이용하면 $O(n \log k)$ 시간에 풀 수 있는데, $n, k \leq 1e5$ 라서 이렇게도 쉽게 풀릴 것 같다. multiset을 쓰는 방법은 훨씬 자명하다.

코드 [링크]

---

BOJ 19647, 신촌 ICPC Camp Open contest

난이도 : Solved AC 기준 Platinum 2

이분 매칭이 유일한지 판단하는 문제. 

이분 매칭이 유일한지는 다음 기준으로 판단할 수 있음이 잘 알려져 있다.

1. 이분 매칭을 아무거나 하나 찾는다.

2. 그 매칭에 포함된 간선은 정방향으로, 그렇지 않은 모든 간선을 역방향으로 연결한다.

3. 만들어진 Directed Graph에서, Cycle이 존재하는지를 찾는다.

코드 [링크]

---

BOJ 4008, APIO 2010 Commando (특공대)

난이도 : Solved AC 기준 Platinum 1

PS를 일정 이상 공부한 사람들이라면 아마 '특공대' 라는 문제를 적어도 들어는 보았을 듯 하다. 나도 처음 들어본 다음 코딩해서 푸는데까지는 한참 지났으니... 

이 문제는 Convex Hull Trick이라는 널리 알려진 테크닉을 사용하는 Dynamic Programming 문제이다. (CHT가 본격적으로 알려지기 전 문제고, 이 문제로 인한 것도 크니 사실 Well-known이라고 까기는 좀 그렇다) 워낙 유명한 문제이므로 아마도 CHT를 다룰때 다룰 예정이다.

 

참고로, 10년 전 문제이기 때문에 메모리 제한이 64MB라서, Li-Chao Tree같은 오버킬이 어렵다. (나는 어렵더라)

코드 [링크]

---

BOJ 7890, ICPC CERC (Central Europian Regional) 2008

난이도 : Solved AC 기준 Diamond 1

 

평면상에 10만 개의 정점이 주어진다. 각 정점에 대해, Nearest Neighbor을 찾는 문제.

 

DO YOU KNOW KD-TREE?

KD-Tree는 K차원 공간상에서 Nearest Neighbor search를 빨리 하기 위한 자료 구조이다. 기본적으로는 공간을 잘 분할해서 박스로 만드는 식의 접근인데, 처음 구현 해봤다. (매우 빡세다) 

 

알려진 바에 따르면, 정해는 KD-Tree가 아닌 뭔가 잘 뚜까뚜까하는 분할 정복이라고 한다. 사실 KD-Tree 구현이 다이아 1씩이나 될 필요는 없는것 같긴 하다. 

코드 [링크]