본문 바로가기

Computer Science/Algorithms & Problem Solving

Minimums on the Edges 풀이

최근에 푼 문제 중 가장 재미있는 것 같아서 풀이를 기록해둔다.

 

Link: www.acmicpc.net/problem/18664

 

18664번: Minimums on the Edges

Print n numbers a1, a2, . . . , an (0 ≤ ai ≤ s), where ai is the number of tokens you put on the i-th vertex. The sum of printed integers must be equal to s. The sum of capacities of all edges must be the maximum possible. If there are multiple optimal

www.acmicpc.net

$N$개의 정점이 있고, $M$개의 간선 $(u_1, v_1), \cdots, (u_M, v_M)$ 이 있는 그래프 $G$가 주어진다. (루프는 없고, parallel edge는 있을 수 있다.) 그래프의 정점들에 총 $S$개의 토큰을 놓아 다음 식의 값을 최대화 하는 문제이다. (단, $c(i)$는 정점 $i$위에 놓인 토큰의 수를 의미한다.)

$$ \sum_{i=1}^M \min(c(u_i), c(v_i)) $$

단, $N \le 18, M \le 100000, S \le 100$ 이다.

 

관점을 바꾸어 보면, 토큰을 다음과 같은 과정을 거쳐 차례로 놓는다고 생각할 수 있다.

 

  • 토큰을 $1$개 이상 놓을 정점들에 토큰을 하나씩 놓는다.
  • 토큰을 $2$개 이상 놓을 정점들에 토큰을 하나씩 놓는다.
  • ...
  • 토큰을 $S$개 이상 놓을 정점들에 토큰을 하나씩 놓는다.

각 시행에서 토큰을 놓은 정점 집합을 $V_1, V_2, \cdots, V_S$라 하면, $V_1 \supseteq V_2 \supseteq \cdots \supseteq V_S$가 된다. 그리고, 이 경우 문제의 답은 $\sum |E(G[V_i])|$가 된다. ($G[X]$는 $G$의 induced subgraph on $X$를 의미한다.)

 

$f: 2^{[N]} \to \mathbb{Z}$를 $f(X) = |E(G[X])|$로 해서 정의하자. 각 $1 \le i \le N$에 대해, $S_i$를 다음과 같이 정의하자:

$$ S_i = \arg\max_{|X| = i} f(X).$$

문제의 답부터 말하자면, 크기 $S$인 가방에 크기가 $i$이고, 값어치가 $f(S_i)$인 상품들을 넣는 냅색 문제로 이 문제를 환원하여 해결할 수 있다. 그리고 이의 정당성은 submodularity에서 나온다.

 

문제 제한이 작으므로, naive하게 $O(2^N \cdot N^2 + NS)$ 정도에 해결해주면 된다.

'Computer Science > Algorithms & Problem Solving' 카테고리의 다른 글

2021-08-01 Problem Solving  (0) 2021.08.01
Generalized Sorting with Predictions  (0) 2021.05.05
Minimums on the Edges 풀이  (0) 2020.10.19
최대 부분합과 쿼리  (0) 2020.06.06
Patience Sort  (0) 2020.05.24
Kruskal's Algorithm과 MST의 성질  (0) 2020.03.13