Eau de Cologne
문제: 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
문제: https://www.acmicpc.net/problem/18621 풀이: 더보기 일단 가장 간단한 문제의 성질을 이용한 hill-climbing 풀이를 생각합시다. 한 점을 잡고, 매 번 주위 8칸을 보면서 더 큰 쪽으로 이동합니다. 이 방법으로 답을 찾을 수 있다는 것은 간단하지만 매우 중요하게 사용될 것입니다. 답이 있는 영역을 절반으로 줄여봅시다. $(\left\lceil N/2 \right \rceil, *)$ 위치에 대해 쿼리를 날린 이후, 해당 가로줄에 있는 수중 가장 큰 수가 있는 위치 $(\left\lceil N/2 \right \rceil, j)$ 근처의 모든 셀에 대해 쿼리를 날립니다. $(\left\lceil N/2 \right \rceil, j)$보다 큰 수가 없을 경우에는..
문제: https://www.acmicpc.net/problem/10513 풀이: 더보기 거리가 가장 먼 것 부터 터트리는 것을 생각합시다. 해당 우주선을 $t$ 시간에 터트리면 해당 $t$ 시간이 포함되는 모든 우주선은 같이 터지게 됩니다. 즉, $t$ 시간이 배제된 ($t$ 시간 이전에 없어지거나 $t$ 시간 이후에 나타나는) 우주선만 고려하면 되고, 이 두 우주선은 따로 고려할 수 있습니다. $D_{a, b}$를 $[a, b)$ 시간에 완전히 포함되는 우주선만을 처치하는데 드는 최소 비용이라고 합시다. ($a-1$ 시간과 $b$ 시간에 폭탄을 터트린 경우입니다. 가장 먼 거리의 우주선이 $[l, r)$ 시간에 있고, 거리가 $d$ 라고 하면 $D_{a, b} = \max_{l \le i < r} (..