Eau de Cologne

문제: https://www.acmicpc.net/problem/5477 풀이: 전반 더보기 우선, 무조건 제거되어야 하는 간선들을 찾아줍니다. 간선 $(u, v, w)$에 대해 트리에서 $u \rightarrow v$ 경로의 길이가 홀수이면, $(u, v, w)$와 트리 경로만 이용해서 짝수 사이클을 만들 수 있습니다. 그렇기 때문에 무조건 삭제되어야 합니다. 이제, 짝수 사이클이 만들어지는 조건을 찾아봅시다. $(u_1, v_1, w_1)$ 간선이 트리를 통해 만드는 사이클과, $(u_2, v_2, w_2)$ 간선이 트리를 통해 만드는 사이클은 모두 홀수 사이클입니다. 이제 두 사이클을 XOR하면 (즉, 간선 중 둘 중 한 쪽에만 포함된 간선을 찾아서 새로운 그래프를 만들면), 새로운 그래프는 사이클..

HTML 삽입 미리보기할 수 없는 소스

문제: https://www.acmicpc.net/problem/17146 힌트 1 (Subtask 1): 더보기 $D_{i, j} = 1$ 인 두 $i, j$ 정점들을 모두 합치고 (같은 색으로 칠해주고) 나면, 모든 $i \ne j$에 대해 $D_{i, j} = 2$가 됩니다. 이 경우에는 색을 번갈아가면서 칠하면서 문제를 해결할 수 있습니다. 트리의 모양은 아무렇게나 정해도 상관 없습니다. 힌트 2 (Subtask 2): 더보기 $1, \cdots, N-1$ 까지의 색을 정했을 때 $N$의 색을 정한다고 해 봅시다. $i$에서 $N$까지 가는 경로 위에 있는 정점의 색 집합은 $i$에서 $N-1$까지 정점의 색 집합에다가 $N$의 색을 추가한 것입니다. 만약 $D_{i, N} \ne D_{i, N-..

링크: https://atcoder.jp/contests/abc287 gs18115, IBory, JooDdae 님이랑 같이 돌았습니다. 제 코드는 https://atcoder.jp/contests/abc287/submissions?f.User=cologne1723 에서 확인할 수 있습니다. ABC287A Majority 풀이: 더보기 For와 Against의 개수를 세 주어서, For가 더 많으면 Yes, 아니면 Against를 출력합니다. 대회 중에서는 For가 $N/2$ 이상인지 이하인지를 판단했습니다. ABC287B Postal Card 풀이: 더보기 S의 마지막 3글자로 리스트를 만들고, T의 마지막 3글자로 set을 만들어서, S의 원소 중 T에 속한게 무엇인지 세주었습니다. ABC287C P..

문제: https://www.acmicpc.net/problem/20662 힌트 1: 더보기 모든 $i r_1$, 초록색이면 $g_2 > g_1$, 파란색이면 $b_2 > b_1$을 만족해야합니다. 수가 증가하는 방향으로 간선을 긋는 것이 좋을 것 같으니, $0$부터 $N-1$까지의 수를 $4$진법으로 표현해봅시다. $r_2 \times 4^2 + g_2 \times 4^1 + b_2 \times 4^0 > r_1 \times 4^2 + g_1 \times 4^1 + b_1 \times 4^0$를 만족한다는 의미는, $r_2 > r_1$, $g_2 > g_1$, $b_2 > b_1$ 중 하나 이상을 만족한다는 의미입니다. 만족하는 색을 이용해서 간선을 그리면 간선의 할당에 따른 DP값이 올바르게 할당이 ..

HTML 삽입 미리보기할 수 없는 소스 Sample Usage: Problem: https://www.acmicpc.net/problem/17429 Code: https://www.acmicpc.net/source/share/29df4fc631d14b97ba84e21bea6a2d87