https://www.acmicpc.net/problem/12797 12797번: 연금술 첫 줄에 정수 n과 m(1 ≤ n ≤ 109, 1 ≤ m ≤ 103)이 공백으로 구분되어 두고 주어진다. 다음 줄에 a1, a2, ..., am (1 ≤ ai ≤ 109)이 공백으로 구분되어 주어진다. www.acmicpc.net 고생 고생 끝에 겨우 풀었다. 정리해둘만한 내용이 많은 문제인 것 같아서 풀이를 기록해 둠. 우선 점화식부터 유도해보자. $ DP(n, m) $ 을 $1 \dots m $ 번 까지의 재료를 써서 $ n $ 개 조합할 때 만들 수 있는 완성품 품질의 총합이라고 정의한다. 이 경우 $ DP(n, m) $의 점화식은 다음과 같이 세울 수 있다. $$ DP(n, m) = a_m \cdot DP(n..
이제 플래티넘 이하 난이도 문제는 총 3개가 남았다. 내일 모레쯤 끝날 듯. 다이아는 천천히 풀어야지(천천히 풀기 싫어도 천천히 풀게 되겠지) 18260. Bessie's Snow Cow 내가 비교적 잘 푸는 유형이라 쉽게 풀었다. 이 문제도 일단 오일러 투어 테크닉을 써서 구간으로 펴서 생각한다. 이렇게 펴서 생각하면, 업데이트는 특정 구간에 색깔 c가 없는 위치에 전부 c를 추가하는 연산으로 생각할 수 있다. 쿼리는 그 구간에 존재하는 색 개수의 합을 구하는 형태가 되는데, 여기까지만 놓고 보면 제일 기본적인 형태의 Lazy propagation Segment Tree로 생각할 수 있다. 다만 색깔 c가 없는 위치만 골라서 c를 추가하는 부분이 조금 어려운데, 여기서 각 구간이 하나의 서브 트리를 나..
한 문제 한 문제가 고역이다 11990. Load Balancing (Platinum) 이 문제는 비교적 뻔한 문제여서 풀이는 금방 생각했다. 우선 모든 점을 x좌표를 기준으로 정렬해보자. 임의의 i번째 점과 i + 1번째 점 사이에 선을 그으면, 1 ~ i번째 점과 i +1 ~ n번째 점은 서로 다른 평면으로 분할이 된다. 이제 여기서 좌우로 선을 어떻게 긋는 경우가 최적인지를 찾아야 하는데, 이 때는 x좌표는 고려할 필요가 없다(x좌표는 이미 평면 분할된 걸 고려했으니). 그래서 y 좌표만 있는 일차원 배열 두 개에서 최적인 경우를 찾는게 되는데, 이 최적 그래프는 unimodal한 형태를 띈다(양쪽 평면 각각을 나눠서 생각했을 때 unimodal한 건 쉽게 생각할 수 있는데, 이 둘에서 다시 최대를..
벌써부터 점점 풀기가 어려워지고 있다. 14446. Promotion Counting 15899번 문제와 완전히 똑같은 문제. 이제는 너무 널리 알려진 테크닉이 아닌가 싶다. 일단 오일러 투어 테크닉을 써서 트리를 배열로 펴주고 나면 각각의 서브트리를 구간으로 나타낼 수 있다. 이제 이 구간에서 루트의 값 x보다 큰 원소의 개수를 세는 문제가 되는데, 이는 여러 가지 자료구조를 이용해서 풀 수 있다. 나는 그냥 머지소트 트리 써서 풀었다. 14522. Modern Art(Platinum) 문제를 잘못 읽어서 약간 헤맸다. N^2개 수를 각각 최소한 한 번씩 쓴다는 조건이 있는데 이것 때문에 생기는 예외를 처리를 안 했음. 우선 각각의 색에 대해 그 색이 칠해진 사각형 영역의 크기를 구한다. 이 사각형 영..
USACO 플래 문제 밀기를 하고 있다. 쉬운 난이도부터 정렬해서 푸는 중. 11979. Fort Moo 부분합을 구해두면 O(N^2M^2)은 쉽게 생각할 수 있다. 사각형을 이루는 네 꼭지점을 정한 뒤 그 네 변의 어디에도 X 표시가 없으면 답을 갱신해주는 걸 반복해주면 되기 때문. 여기서 N 혹은 M을 하나 떼면 시간 안에 돌아가는 시간 복잡도가 된다. 좌우 부분합, 상하 부분 합은 세제곱 베이스로 계산이 가능하기 때문에 부분합까지는 똑같이 구한다. 사각형의 위아래 변만 고정하면 O(N^2)이 되는데, 여기서 윗변과 아래변을 연결하는 X 자 표시가 없는 직선의 위치는 부분합을 이용하면 O(M)에 전처리가 가능하다. 이렇게 구해놓은 각 직선끼리 최대한 윗변 or 아랫변에서 X가 없는 조건을 만족하면서 ..
[16663] Distance Sum
https://www.acmicpc.net/problem/16663 16663번: Distance Sum You are given a connected undirected unweighted graph. The distance d(u, v) between two vertices u and v is defined as the number of edges in the shortest path between them. Find the sum of d(u, v) over all unordered pairs (u, v). www.acmicpc.net 문제 요약 연결된 가중치 없는 무향 그래프가 주어진다. $ d(u,v) $ 를 정점 $u$와 $v$ 사이의 최단 거리라고 할 때, 모든 $(u, v)$ 쌍에 대해 $..
링크 : https://www.acmicpc.net/problem/14454 어떤 문자열 S에 대해 그 문자열을 오른쪽으로 한 칸 민 문자열을 원래 문자열 S 뒤에 덧붙여 2배로 긴 새로운 문자열로 만드는 연산을 F라고 하자. 첫 문자열 S가 주어지고 여기에 F를 무한 반복해서 나오는 어떤 문자열이 있다고 했을 때, 그 문자열에서 n번째 위치에 어떤 문자가 들어갈 지를 구하는 문제다. 얼핏 생각하면 좀 까다로울 수 있는데, n번째 위치를 크게 나눠서 생각하면, 원래 문자열 s에 F를 쭉 반복해서 붙인 문자열 중 길이가 n보다 작으면서 가장 긴 걸 K라고 하자. 그러면 n번째 위치는 K를 오른쪽으로 한칸 민 문자열에서 n - (K의 길이) 위치에 있는 문자가 된다. 그러면 여기서 거꾸로 돌아가 n번째 위치..
링크 : https://www.acmicpc.net/problem/14777 그다지 어려운 문제가 아니었는데 문제 해석이 잘 안 돼서 한참 끙끙댔다. n개의 도시가 있고 첫 도시에서 시작해서 pi시간에 어떤 도시에 있을 수 있으면 그 도시에서 수여하는 상을 받을 수 있고, n개 도시 각각에 대해 움직이는데 걸리는 시간이 주어졌을 때 최대한 받을 수 있는 상 개수를 구하는게 문제다. 처음에 도시 개수 * 최대 시간 으로 모든 도시 왔다갔다하는거 다 계산하는 DP를 생각했는데 이러면 최대 시간 범위가 100만이라 시간 초과가 난다. 좀 더 생각하면 줄일 수 있는데, 각 도시에 대해 그냥 그 도시에서 수여하는 상 받을 지 아닐 지만 고민하면 되고, 이건 어떤 도시에 p[i]보다 일찍 도착한 다음 p[i]까지 ..