[Codeforces 962D] Merge Equals - 1600 문제 설명 : n개의 수로 이루어진 수열이 주어진다. 이 수열에서 가장 작으면서 같은 값 2개를 합쳐서 그 수의 합으로 merge하는 연산이 가능하고, 그 결과 값은 두 수 중에서 오른쪽에 있던 수의 위치에 채워지게 된다(왼쪽에 있던 값은 사라진다). 가능한 모든 merge연산을 마친 뒤의 수열의 결과를 구하는 문제이다. 풀이 : stl로 떡칠하면 풀기 수월한 문제이다.일단 n이 최대 15만이므로 O(N^2)안에 풀어야 한다. 따라서 merge연산을 한 번 할 때마다 합친 다음에 다시 처음부터 수를 살펴볼 여유가 없다. 처음부터 모든 수를 저장해놓은 다음에 조건이 맞으면 그때그때 merge를 해야한다. 그래서 처음에 set..
[Codeforces 954D] Fight Against Traffic - 1600 문제 설명 : 그래프에서 이미 길이 설치되어 있지 않은 두 노드 사이에 길을 추가했을 때, s에서 t로가는 최단거리의 값에 변함이 없도록 만드는 두 노드를 고르는 경우의 수를 구하는 문제이다. 풀이 : 전처리로써 처음에 모든 노드에서 s까지의 거리, 모든 노드에서 t까지의 거리를 모두 구해놓는다. a에서 b로 가는 도로가 생긴다는 의미는 곧 a->b 최단거리가 1이 됨을 의미한다. 따라서 s->a거리, b->t 거리만 추가로 더해주기만 하면(역도 고려해야 하긴 하지만) 'a,b 노드에 길을 추가함으로써 최종 s->t로 가는 최단거리'를 구할 수 있다. 그래서 새롭게 구한 최단거리가 원래의 최단거리보다 더 짧아졌는지 그대로..
[Codeforces 1006E] Military Problem - 1600 문제 설명 : 군대의 위계를 나타내는 트리가 주어지고, 쿼리가 주어진다. 각 쿼리는 두 개의 정수 u,k로 이루어져 있는데 쿼리마다 노드 u부터 시작해서 k번째로 방문하는 노드가 몇 번인지를 찾는 문제이다. 방문하는 원칙에는 반드시 현재 노드보다 위계가 낮은(아래)노드로만 방문이 가능하며, 자식이 여럿일 때는 노드 번호가 작은 순부터 방문한다. 풀이 : 트리의 노드가 최대 20만개, 쿼리도 최대 20만개이므로 매 쿼리를 계산할 때 최대 O(logN)이내에 수행해야 한다. 따라서 전처리 단계부터 쿼리에 빠르게 답할 수 있도록 처리해야 한다. 그러기 위해서 나는 두 개의 배열을 마련할 것이다. 하나는 (밑의 소스코드와 같이) cnt..
[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의 개수를..
[Codeforces 1011E] Border - 1800 문제 설명 : 각 금액별 banknote가 충분히 많이 있다. 이 banknote들을 적당히 조합하여 만들 수 있는 정수들의 경우의 수를 구하는 문제이다. 풀이 : 베주 항등식을 활용하는 문제이다. 베주 항등식이란 두개 이상의 정수들의 최대공약수는 그 수들의 정수 곱으로 반드시 표현될 수 있다는 이론이다. 증명은 어려우니깐 패스하고 그냥 가능한가보다 라고 생각하겠다. 이 문제의 관심사는 각 banknote의 금액(a_i)를 k로 나머지 취한 값들을 적절하게 정수배하여 만들 수 있는 모든 금액의 경우의 수를 구하는 것이다. 주의할 점 : - 배운 점 : n개의 수들을 적절히 정수배한 값의 합의 모든 경우의 수를 구하기 위해서 베주 항등식을 활용하였..
[Codeforces 1163B2] Cat Party (Hard Edition) - 1700 문제 설명 : n개의 숫자가 주어진다. 등장한 숫자가 모두 같은 빈도수로 등장하는 가장 큰 지점(인덱스)을 찾아야 하는데, 딱 1개의 아무 숫자를 삭제할 수 있다(반드시 1개를 삭제해야만 한다). 풀이 : 이 문제에서 정답이 될 수 있는 케이스가 크게 4가지가 존재한다. 1. 단 한 가지의 수만 등장할 때2. 여러 가지의 수가 딱 1번씩만 등장할 때3. 한 가지의 수가 나머지 등장한 수들의 등장 횟수보다 딱 1번 더 많이 등장할 때 4. 한 가지의 수만 1번 등장하고 나머지 수들은 모두 그보다 1번보다 더 많이 등장할 때 이렇게 분류할 수 있다. 1~4번 모두 관건은 각 숫자를 볼 때 지금껏 등장한 수들이 모두 ..
[Codeforces 1025B] Weakened Common Divisor - 1600 문제 설명 : 문제에서 WCD라는 연산을 정의한다. 이 연산은 양의 정수 2개로 구성된 pair가 총 n개 주어질 때 두 수 중에서 최소 1개는 나누어 떨어지는 공약수를 전체 n개의 pair에 대해서 찾을 수 있으면 그 공약수를 구하거나 불가능함을 밝히는 문제이다. 풀이 : pair가 최대15만개 주어지므로 숫자는 총 30만개이고 각 수의 최대 범위는 20억이다. naive하게 생각하면 30만개 수를 모두 소인수분해해서 그 수들의 공약수를 찾으면 되는데, 소인수분해 알고리즘의 시간복잡도는 단발성 소인수분해는 O(sqrt(RANGE)), 전처리 소인수분해는 O(N*RANGE*log(log(RANGE)))이다(RANGE..