구사과

Example 1 (https://koosaga.com/319 마지막 단락) 그래프가 주어질 때 이 그래프의 maximal independent set 을 구하는 문제를 생각해 보자. maximal independent set은 maximum independent set을 approximate할 수 없다. 하지만 maximal matching과 $\Delta+1$ edge coloring을 구하는 데 사용할 수 있고 이들은 각각 그들의 optimal variant의 constant approximation이다. 다음 과정을 정점이 1개 이상일 때까지 반복하면 된다: 각 노드에 $[0, 1]$ 사이의 random real을 배정한다. 이를 $r(v)$ 라고 하자. 만약 어떠한 노드에 대해 $\max_{w ..

PA 2016. Shuffle 문제에서 주어진 셔플 연산은 카드 덱을 뒤집는 연산과 동일합니다. 이 사실은 수학적 귀납법으로 증명 가능합니다. $2$ 개의 카드에 대해서는 자명히 뒤집는 연산과 동일합니다. $2^k$ 개의 카드에 대해서는, 덱을 절반으로 나눈 후 각각을 뒤집고 둘의 순서를 바꾸는 것이니, 이 역시 뒤집는 연산과 동일합니다. 카드 덱을 두번 뒤집는 건 아무것도 안하는 것과 동일하니, $t$ 가 홀수일 때 배열을 뒤집은 후 출력해 주면 됩니다. ROI 2022 P5. Максимизация выигрыша 입력으로 주어진 문자열의 길이가 $19$ 이하일때만 문제를 해결할 수 있어도 됩니다. 만약 맨 앞 문자가 전체 문자열의 최댓값이 아닐 경우, 가장 가까운 최댓값을 맨 앞 문자로 옮깁니다. ..

https://dl.acm.org/doi/pdf/10.5555/982792.982916 Cut-cycle duality에 의해 $G$ 에서 minimum cut을 찾는 것은 $G^*$ 에서 minimum cycle을 찾는 것과 동일하다. 아이디어는, $G^*$ 에서 적당한 사이클 $C$를 찾은 다음, $C$의 *안* 과 *밖* 에 대해서 분할 정복을 하고, 이후 $C$의 안과 밖을 오가는 사이클을 찾는 것이다. 분할 정복이 성립하려면 일단 $C$가 $G^*$ 의 Face들을 공평하게 쪼개야 할 것이다. 이런 $C$는 $O(n)$ 시간에 찾을 수 있다. $G^*$ 의 모든 Face를 대각선에 $\infty$ 가중치 간선 넣고 대충 triangulate하자. 다음, $G^*$ 에서 아무 정점을 잡고, sho..