[CF 1512E] Permutation by Sum - 1600 문제 요약 : 1~n수 중에서 (r-l+1)개 중복없이 뽑아서 s만들 수 있는지를 묻고 있다. 문제 풀이 : n부터 1씩 줄여나가면서 누적합을 쌓아가면서 s를 만든다. 이때 만들어진 수의 집합은 최소의 개수이므로 (r-l+1)개보다 적거나 같을 것이다. 만약 크다면 s를 만들 수 없다는 뜻이다. 개수를 늘리기 위해서는 작은 값부터 2개로 쪼개면 된다. 예를 들어 x라는 값을 쪼갠다면 (1,x-1) 또는 (2,x-2) 또는 (3,x-3)...이런 식이다. 이때 쪼개진 결과로 나오는 두 개의 값은 초기 집합과 겹치면 안된다. 겹치지 않는 것이 확인이 된다면 set에서 두 값을 insert 해주고 원래 x값은 삭제해준다. 가장 작은 값부터 쪼개..
[CF 1208B] Uniqueness - 1500 문제 설명 : 배열 a가 주어지고 나는 최대 1번의 연산을 통해 구간 [l,r]에 해당하는 범위의 원소를 제거할 수 있다. 이 결과로 남아있는 배열 a에 존재하는 모든 원소는 고유하게 만들어야 한다. 내가 제거할 구간의 길이가 최소가 되도록 하여라. 풀이 : 두 가지 방법으로 풀 수 있다. 하나는 좌표압축과 이분탐색을 이용해서 모든 구간의 경우의 수(N^2)을 다 돌면서 구간의 lower bound를 찾는 방법이 있다. 좌표압축을 통해 수의 범위가 매우 커서 배열의 인덱스로 활용할 수가 없더라도 O(1)만에 바로 접근할 수 있는 방법이다. 자세한 설명은 아래에 한다. 다른 한 방법은 투포인터를 이용한 방법이다. 배열에서 어느 구간을 삭제한다는 의미는 곧..
[CF 1154E] Two Teams - 1800 문제 설명 : 1~n범위의 숫자가 고유하게 딱 한 개씩 주어진다. 매 시행마다 가장 큰 숫자를 찾아서 그 수와 그 수의 양 끝 k개의 숫자는 같은 team이 된다. team으로 묶인 숫자는 삭제한다. 이 시행을 모든 숫자가 team에 소속될 때까지 반복한다. 풀이 : 그냥 naive하게 생각해봤을 때는 문제 설명 그대로 매 시행마다 가장 큰 수를 찾아서 양 끝의 k개를 지우면 될 것이다. 지운 숫자는 -1로 마킹해놓아서 이미 선택되었다고 표시해놓으면 된다. 하지만 이렇게 할 경우, 지워진 숫자가 연속되서 계속 나타날 수도 있으므로 최악의 경우 시간복잡도가 O(N^2)이 될 수도 있다. 따라서 나는 수를 지울 때의 연산을 좀 더 효율적으로 할 방법을 찾아야..
[Codeforces 962D] Merge Equals - 1600 문제 설명 : n개의 수로 이루어진 수열이 주어진다. 이 수열에서 가장 작으면서 같은 값 2개를 합쳐서 그 수의 합으로 merge하는 연산이 가능하고, 그 결과 값은 두 수 중에서 오른쪽에 있던 수의 위치에 채워지게 된다(왼쪽에 있던 값은 사라진다). 가능한 모든 merge연산을 마친 뒤의 수열의 결과를 구하는 문제이다. 풀이 : stl로 떡칠하면 풀기 수월한 문제이다.일단 n이 최대 15만이므로 O(N^2)안에 풀어야 한다. 따라서 merge연산을 한 번 할 때마다 합친 다음에 다시 처음부터 수를 살펴볼 여유가 없다. 처음부터 모든 수를 저장해놓은 다음에 조건이 맞으면 그때그때 merge를 해야한다. 그래서 처음에 set..
[Codeforces 1163B2] Cat Party (Hard Edition) - 1700 문제 설명 : n개의 숫자가 주어진다. 등장한 숫자가 모두 같은 빈도수로 등장하는 가장 큰 지점(인덱스)을 찾아야 하는데, 딱 1개의 아무 숫자를 삭제할 수 있다(반드시 1개를 삭제해야만 한다). 풀이 : 이 문제에서 정답이 될 수 있는 케이스가 크게 4가지가 존재한다. 1. 단 한 가지의 수만 등장할 때2. 여러 가지의 수가 딱 1번씩만 등장할 때3. 한 가지의 수가 나머지 등장한 수들의 등장 횟수보다 딱 1번 더 많이 등장할 때 4. 한 가지의 수만 1번 등장하고 나머지 수들은 모두 그보다 1번보다 더 많이 등장할 때 이렇게 분류할 수 있다. 1~4번 모두 관건은 각 숫자를 볼 때 지금껏 등장한 수들이 모두 ..
[Codeforces 1108E1] Array and Segments (Easy version) - 1800 문제 설명 : n개의 숫자와 q개의 쿼리(구간)가 주어진다. 각 쿼리는 시작점~끝점으로 표현되며 그 쿼리를 '적용'한다면 시작점~끝점에 해당하는 인덱스의 배열의 값을 모두 1씩 감소시킨다. 여기서 0개 이상의 쿼리를 적용하여 나온 결과 배열에서 가장 큰 값과 가장 작은 값의 차이를 최대가 되도록 만드는 문제이다. 풀이 : 내가 생각해야 할 것은 '어떤 수를 배열에서 가장 큰 값이 되도록 할 것인가'이다. 만약 i번째 수를 가장 큰 값이 되도록 정했다면 그 값은 그대로 고정시키고 다른 값을 빼준다. 즉 쿼리 중에서 i를 포함하지 않는 구간만 적용하여 값을 빼주는 것이다. 어차피 특정 구간 안에 최대..
[Codeforces 1034A] Enlarge GCD - 1700 문제 설명 : n개의 숫자가 주어진다. 이 중에서 숫자 k 개를 삭제한 뒤 나머지 (n-k)개 수들의 GCD(최대공약수)가 삭제하기 이전의 GCD보다 크도록 만들어야 한다. 그러기 위해서는 최소 몇 개의 숫자를 삭제해야 하는지 구하는 문제이다(= 가장 작은 k값을 구하여라). 풀이 : 먼저 N개 수들의 GCD를 먼저 구한 뒤, 다시 모든 수들을 GCD로 나눠준다. 나눠진 수들의 GCD는 당연히 1이다. 이 숫자들을 각각 소인수분해하여 가장 많이 등장하는 소인수의 횟수를 N에서 빼주면 된다. 가장 많이 등장하는 소인수를 포함하지 않은 수들을 모두 삭제하고 나면, 그 소인수를 GCD로 취할 수 있기 때문이다. 그리고 이 문제에서 중요한 is..
[Codeforces 1080C] Masha and two friends 문제 설명 : n*m크기의 체스판이 있다. 이 체스판에 두 사람이 흰색 물감과 검정색 물감을 쏟았다. 물감이 쏟아진 모양이 직사각형일 때 쏟고난 뒤에 체스판에 칠해진 흰색 칸과 검정색 칸의 수를 구하는 문제이다. 풀이 : 처음에 풀 때는 엄청난 솔루션이 존재할 줄 알았는데, 그냥 단순 수학 문제이다. 흰색 물감이 칠해진 영역, 검정색 물감이 칠해진 영역, (만약 존재한다면) 두 물감이 겹치는 영역을 따로 구해서 전체 흰색, 검정색 수에 더하고 빼면 된다. 주의할 점 : 영역에 있는 블럭의 수가 짝수개라면 흰색과 검정색 수가 같지만, (홀수)*(홀수) 영역이라면 블럭의 수가 홀수이므로 흰색과 검정색의 수가 1개 차이나게 된다. 이 부..