[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 1155D] Beautiful Array - 1900 문제 설명 : n개의 수로 이루어진 수열과 x가 주어진다. 연속된 수들의 합의 최댓값을 구하면 되는데, 최대 1번에 한하여 수열의 연속된 수들에 x를 곱하는 연산이 가능하다. 풀이 : 처음에 풀 때는 그리디하게 접근하려 했는데 WA를 받았다(반례 4 -1 / -5 10 -3 10).아무튼 dp로 풀어야 하는데, 이 문제의 핵심은 결국 몇 번째부터 몇 번째까지 x가 곱해지냐이다(물론 안 곱할 수도 있다). 그래서 나는 x가 곱해지는 모든 구간의 경우에 대해서 저장하고 그 중에서 최댓값을 구하자는 취지이다. 일반화시키자면, 정답은 (x를 안 곱하는 구간) + (x를 곱하는 구간) + (x를 안 곱하는 구간) 으로 구성될 것이다. 그리고 나는 곱해지..
[CF 1114D] Flood Fill - 1900 문제 설명 : n개의 수가 주어지고 이 중에서 시작할 수 1개를 고른다. 그리고 매 시행마다 시작 위치가 포함된 똑같은 수로 연결된 한 덩어리를 다른 숫자로 바꿀 수 있다. 이때 모든 숫자를 똑같은 숫자로 바꾸는데 필요한 최소 시행 수를 구하여라. 풀이 : 우선 맨 처음에 n개의 수를 입력받으면 unique연산을 취해서 인접해 있으면서 값이 같은 수를 미리 없애준다. 인접한 같은 수는 어차피 한 덩어리이므로 정답에 영향이 없기 때문이다. unique를 취한 후에는 인접한 숫자끼리는 모두 다를 것이라는 확신을 할 수가 있다. 그러고 난 뒤에 각 시행에서 내가 신경써야할 것은 시행의 가장 왼쪽 수(l)와 가장 오른쪽 수(r)가 같은지 여부이다. 만약에 같다..
[Codeforces 1036C] Classy Numbers - 1800 문제 설명 : 1부터 10^18까지의 수 중에서 0이 아닌 서로 다른 digit이 3번 이하로 등장하는 수가 몇 개 인지 세는 문제이다. 풀이 : 수의 범위가 최대 10^18이기 때문에 매 쿼리마다 개수를 세는 것은 무리라고 생각해서 어떻게든 전처리를 한 다음에 O(1)이나 O(logN)만에 구해야 한다고 생각했다. 그래서 전처리로 3개의 자리수로 만들 수 있는 수들을 digit 3개, 10의자리 3개로 6중 for문을 구성하여 모두 벡터에다가 집어넣었다. 이렇게해도 최대 10*10*10*18*18*18=583만개이다. 정렬 뒤 unique연산을 취해준다. 그런 다음 쿼리의 L~R값을 구하기 위해서 1~R의 개수에서 1~L의 개수를..
[Codefocres 1061C] Multiplicity - 1700 문제 설명 : 어떤 집합의 원소 N개가 주어진다. 그 집합에서 부분집합(subset)을 만들 건데 부분집합의 원소의 개수는 1개 이상이여야 하고 i번 째 원소는 반드시 i로 나누어 떨어져야 한다. 이 두 조건을 만족하는 부분집합을 만들 수 있는 경우의 수를 구하는 문제이다. 풀이 : 메모리 초과, 시간 초과와 싸워야 하는 문제이다.각 원소가 1~N 사이의 정수 j로 나누어 떨어지는지 확인한다. 나누어 떨어진다면 그 원소는 subset의 j번째 원소가 될 자격이 있는 것이다. 이를 만약 현재 보고 있는 원소가 j로 나누어 떨어진다면 그 경우의 수를 2차원 dp로 나타내면 dp[i][j] = dp[i-1][j] + dp[i-1][j-1]이..
[Codeforces 1096D] Easy Problem 문제 설명 : 알파벳 소문자로 이루어진 문자열이 주어진다. 이 문자열에서 최소 0개이상의 문자들을 삭제해야 하는데 그 조건은 그 문자열에서 순서대로 "h,a,r,d"가 나타나지 않도록 하는 것이다(떨어져 있을 수도 있다). 각 문자에는 가중치(ambiguity)가 존재하여 가중치의 합이 최소가 되도록 제거해야 한다. 풀이 : 처음에는 그리디로 풀려고 했는데 안되고, dp로 풀어야 하는 문제이다.전체 문자열(str)을 살피면서 "h,a,r,d"로 하나씩 매칭해본다.만약 현재 문자 str[i]와 패턴 ptn[j]가 일치한다면 내가 할 수 있는 선택은 두 가지이다. 1. 현재 ptn(패턴)을 삭제하기로 결정한다. 이 경우의 현재 위치의 ambiguity..
[Codeforces 1113C] Sasha and a Bit of Relax XOR 개념에 대한 기본적인 지식이 필요한 문제이다. 전체 n개의 수가 주어지고 길이가 짝수인 어느 구간을 설정할 때 그 구간의 처음~중간까지의 수를 모두 XOR한 값과 중간 이후~끝까지의 수를 모두 XOR한 값이 같은 구간이 총 몇 개 존재하는지 카운트하는 문제이다. 이 문제를 풀기에 앞서 XOR이라는 연산의 특성에 대해서 생각해보자. XOR는 비트 차원의 연산으로 같은 자릿수의 비트 중에서 값이 다른 수가 단 하나라도 존재한다면 1이 되고, 모두 동일해야만 0이 되는 연산이다. 즉 a XOR b의 결과가 0이라면 a==b가 성립하고 이는 필요충분조건이다. 이를 확장해서 생각해보면 가 성립한다면 좌변과 우변의 값이 동일하다는..