[CF 1092F] Tree with Maximum Cost - 2100 문제 설명 : 각 노드별로 가중치가 정해져있는 트리가 주어진다. 이 트리에서의 최대 cost를 구해야 하는데 cost는 (기준노드~다른노드까지의 거리) * (다른 노드의 가중치) 의 총합으로 정의된다. 여기서 거리는 기준노드~다른노드까지 거쳐야 하는 간선의 개수이다. 풀이 : 어떤 임의의 노드 i를 기준으로 cost를 구한다고 하자. 그리고 i에서 j로 기준노드를 변경할 때 어떠한 연관성이 있는지 살펴볼 것이다. $cost_i= 1*(a1+a2+...a_p) + 2*(a_(p+1)+...a_q) + 3*(...) + 1*(b1+b2+..b_s)+2*(...)$이다. 이 식에서 a1,a2...a_p는 노드 i에서 거리가 1만큼 떨어진..
[CF 1082E] Increasing Frequency - 2000 문제 설명 : 배열 내의 임의의 구간에 대해서 임의의 수를 더하거나 빼는 연산을 할 수 있다. 이 연산을 수행한 뒤 c가 가장 많이 등장할 수 있는 빈도수를 구하는 문제이다. 풀이 : 두 가지 풀이가 있다. 하나는 dp를 이용한 풀이이고 다른 하나는 그리디를 이용한 풀이인데, 그리디를 이용한 풀이가 짧고 간결하지만 아이디어적이라서 떠올리기가 쉽지는 않다. 그래서 dp를 이용한 풀이를 먼저 설명하겠다.cnt(l,r,x)를 구간 [l,r]에서 x의 등장 빈도수라고 정의하자. 그러면 이 문제는 연산을 수행한 뒤에 cnt(l,r,c)의 최대를 구하는 문제가 된다. 여기서 나는 연산을 수행할 것이기에 c가 아닌 수 d에 특정 수를 더함으로써 c..
[CF 1208B] Uniqueness - 1500 문제 설명 : 배열 a가 주어지고 나는 최대 1번의 연산을 통해 구간 [l,r]에 해당하는 범위의 원소를 제거할 수 있다. 이 결과로 남아있는 배열 a에 존재하는 모든 원소는 고유하게 만들어야 한다. 내가 제거할 구간의 길이가 최소가 되도록 하여라. 풀이 : 두 가지 방법으로 풀 수 있다. 하나는 좌표압축과 이분탐색을 이용해서 모든 구간의 경우의 수(N^2)을 다 돌면서 구간의 lower bound를 찾는 방법이 있다. 좌표압축을 통해 수의 범위가 매우 커서 배열의 인덱스로 활용할 수가 없더라도 O(1)만에 바로 접근할 수 있는 방법이다. 자세한 설명은 아래에 한다. 다른 한 방법은 투포인터를 이용한 방법이다. 배열에서 어느 구간을 삭제한다는 의미는 곧..
[CF 1194D] 1-2-K Game - 1700 문제 설명 : 0번째부터 n번째 칸이 있는 판이 있다. n번째 칸부터 시작하여 두 사람이 번갈아가며 게임을 하면서 매 시행마다 1칸 혹은 2칸 혹은 k칸을 현재 칸에서 왼쪽으로(작은 값)움직일 수 있다. 그래서 본인 차례에서 말이 0번째 칸에 위치한 사람이 패배하게 되는 게임이다. 두 사람은 최적으로 게임한다고 할 때 누가 이기는지 찾는 문제이다. 풀이 : 이런 게임문제의 유형에서 누가 이기냐를 정할 때는 항상 두 사람이 최적으로 플레이한다고 하는데 이 말을 풀어쓰면 이렇다. '맨 처음에 시작하는 사람이 반드시 이길 수 있는가?'를 묻는 것과 같다. 만약 반드시 이길 수 없다면 그 다음 사람이 이기게 되는 것과 같다 이 문제에서는 처음 시작하는 사람이 ..
[CF 1215C] Swap Letters - 1500 문제 설명 : a와 b로만 이루어진 길이가 같은 두 문자열이 주어진다. 이 문자열에서 한 가지 연산을 할 수 있는데, 첫 번째 문자열에서 한 인덱스와 두 번째 문자열에서 한 인덱스를 골라서 서로 swap을 할 수가 있다. 이 연산을 최소한으로 사용하여 두 문자열을 같도록 만들어야 한다. 풀이 : 두 문자열이 다를 수 있는 경우는 첫번째 문자열이 'a', 두번째 문자열이 'b'이거나 그 반대의 경우밖에 없다. 따라서 그 두가지 경우에 대해서 따로 저장을 해 놓는다. 문자열이 다르다는 것은 현재 문자와 다른 문자를 서로 swap해야 하므로 한번 swap을 했을 때, 총 다른 횟수는 2가 줄어들 것이다. 따라서 ab의 개수+ba의 개수가 짝수가 아니면 불..
[CF 1076D] Edge Deletion - 1800 문제 설명 : 풀이 : 다익스트라 알고리즘의 원리를 얼마나 잘 알고있는지를 물어보는 문제이다. 다익스트라 알고리즘을 돌면서 매 번 dist[]값이 가장 작은 노드를 찾아가서 그 노드에서 갈 수 있는 edge들을 갱신하는 반복을 작업하게 된다. 이때 중요한 성질은, 다익스트라에서 한 번 방문한 노드는 방문한 순간 dist[]값이 최소라는게 보장된다(여기서 말하는 '방문'이란 min heap의 top에 있는 노드로써 말하는 것이다). 따라서 이 문제에서 최대 k개의 edge를 남겨서 최단경로가 여전히 존재하는 노드의 개수를 최대한 많이 남기라는 것은 다익스트라를 돌리면서 방문하게 되는 k개의 노드를 저장하면 되는 것이다. 그리고 본인이 어떤 edge를..
[CF 1163C2] Power Transmission (Hard Edition) - 2000 문제 설명 : 풀이 : 주의할 점 : 배울 점 : 2차원 좌표평면 상의 직선을 표현하기 위해서는 일반적으로 기울기와 y절편이 필요하다. 그런데 기울기나 y절편 모두 정수가 아닌 유리수 형태일 수도 있다. c++에서는 소수의 정밀도 문제 때문에 유리수를 그대로 사용하는 것은 위험하다. 따라서 이런 경우에는 일반적으로 두 정수로 표현되는 기약분수 꼴로 나타낸다. 여기서 나는 기울기와 y절편 모두 유리수가 될 수 있으므로 (기울기의 분모,기울기의 분자, y절편의 분모, y절편의 분자) 총 4개의 dimension이 필요할 것 같아서 너무 복잡하다고 생각했다. 그런데 사실 일차함수에서는 단 3개면 된다. 우리가 일반적..
[CF 1187C] Vasya And Array - 1800 문제 설명 : n개의 수로 이루어진 수열이 있다. 이 수열에 대해 설명하는 m개의 정보로 수열을 추청해야 하는데 정보는 다음과 같다. t=0일 때는 구간 [l,r]에 해당하는 수가 non decreasing(같거나 오름차순)이고, t=1일 때는 not non decreasing이다. 풀이 :테스트 케이스를 직접 손으로 쓰면서 계산해보면 솔루션은 쉽게 나온다. t=1일 때 나온 구간[l,r]들의 합집합을 구해서 t=0일 때의 구간이 이 합집합에 완전히 포함되지 않기만 하면 된다. 문제는 이를 어떻게 구현하느냐이다. 나도 이 문제를 풀 때 여기서 애를 먹었다.예를 들어 구간[2,3]가 합집합이고 [1,4]가 t=0일 때의 구간이라고 하자. 단순히 ..