[CF 1154E] Two Teams - 1800 문제 설명 : 1~n범위의 숫자가 고유하게 딱 한 개씩 주어진다. 매 시행마다 가장 큰 숫자를 찾아서 그 수와 그 수의 양 끝 k개의 숫자는 같은 team이 된다. team으로 묶인 숫자는 삭제한다. 이 시행을 모든 숫자가 team에 소속될 때까지 반복한다. 풀이 : 그냥 naive하게 생각해봤을 때는 문제 설명 그대로 매 시행마다 가장 큰 수를 찾아서 양 끝의 k개를 지우면 될 것이다. 지운 숫자는 -1로 마킹해놓아서 이미 선택되었다고 표시해놓으면 된다. 하지만 이렇게 할 경우, 지워진 숫자가 연속되서 계속 나타날 수도 있으므로 최악의 경우 시간복잡도가 O(N^2)이 될 수도 있다. 따라서 나는 수를 지울 때의 연산을 좀 더 효율적으로 할 방법을 찾아야..
[CF 1155D] Beautiful Array - 1900 문제 설명 : n개의 수로 이루어진 수열과 x가 주어진다. 연속된 수들의 합의 최댓값을 구하면 되는데, 최대 1번에 한하여 수열의 연속된 수들에 x를 곱하는 연산이 가능하다. 풀이 : 처음에 풀 때는 그리디하게 접근하려 했는데 WA를 받았다(반례 4 -1 / -5 10 -3 10).아무튼 dp로 풀어야 하는데, 이 문제의 핵심은 결국 몇 번째부터 몇 번째까지 x가 곱해지냐이다(물론 안 곱할 수도 있다). 그래서 나는 x가 곱해지는 모든 구간의 경우에 대해서 저장하고 그 중에서 최댓값을 구하자는 취지이다. 일반화시키자면, 정답은 (x를 안 곱하는 구간) + (x를 곱하는 구간) + (x를 안 곱하는 구간) 으로 구성될 것이다. 그리고 나는 곱해지..
[CF 1186C] Vus the Cossack and Strings - 1800 문제 설명 : 0과 1로만 이루어진 문자열 a,b가 주어진다. a의 길이는 b의 길이보다 크거나 같다. a문자열에서 b문자열의 길이와 같게끔 모든 substring들을 뽑아냈을 때, b문자열의 각 인덱스와 비교해서 값이 다른 인덱스의 숫자가 짝수개인 substring이 총 몇 개 존재 하는지 구하는 문제이다. 풀이 : 결론부터 얘기하면 a문자열의 각 substring에 존재하는 1의 개수의 홀짝과 b에 존재하는 1의 개수의 홀짝이 같다면 정답이 된다.'값이 다르다'는 얘기는 하나는 0이고 다른 하나는 1이라는 의미이다. 전체에서 이런 케이스가 총 몇 개인지를 세면 되는 것이다. 이걸 세는 방법은 비교할 두 문자열 c,d에서..
[CF 1114D] Flood Fill - 1900 문제 설명 : n개의 수가 주어지고 이 중에서 시작할 수 1개를 고른다. 그리고 매 시행마다 시작 위치가 포함된 똑같은 수로 연결된 한 덩어리를 다른 숫자로 바꿀 수 있다. 이때 모든 숫자를 똑같은 숫자로 바꾸는데 필요한 최소 시행 수를 구하여라. 풀이 : 우선 맨 처음에 n개의 수를 입력받으면 unique연산을 취해서 인접해 있으면서 값이 같은 수를 미리 없애준다. 인접한 같은 수는 어차피 한 덩어리이므로 정답에 영향이 없기 때문이다. unique를 취한 후에는 인접한 숫자끼리는 모두 다를 것이라는 확신을 할 수가 있다. 그러고 난 뒤에 각 시행에서 내가 신경써야할 것은 시행의 가장 왼쪽 수(l)와 가장 오른쪽 수(r)가 같은지 여부이다. 만약에 같다..
[CF 828C] String Reconstruction - 1700 문제 설명 : n개의 부분문자열(substring)과 이 부분문자열이 전체 문자열에서 등장하는 시작 위치가 주어진다. 이 부분문자열의 정보를 바탕으로 전체 문자열을 구성할 때, 사전순으로 가장 앞서도록 만드는 문제이다. (입력되는 정보는 모순되지 않는다) 풀이 : 입력되는 정보는 모순되지 않으므로 단순하게 substring을 i번째 위치에 넣는다고 생각하면 된다. 하지만 naive하게 생각해서 k_i개의 위치에 대해서 substring의 모든 글자를 다 비교해보면 시간초과가 난다. 예를 들어 substring이 "aaa...aa"로 총 100만 글자이고, k_i=100만개 : {1,2,3,...100만}이라면 시간복잡도는 100만 * ..
[CF 1136D] Nastya Is Buying Lunch - 1800 문제 설명 : n명이 줄을 서 있고 문제의 주인공은 줄의 맨 뒤(n번째 인덱스)에 서 있다. 그리고 m개의 정보가 들어오는데 각 정보는 두 정수 a,b로 이루어져있다. 이 의미는 줄의 앞사람이 a번 사람이고 뒷사람이 b번 사람이라면 a와 b가 서로 자리를 바꿀 수 있다는 의미이다. 이 정보들을 바탕으로 n번째 사람은 최대 몇 칸이나 앞으로 움직일 수 있는지 구하는 문제이다. 풀이 : 이 문제에서 관심이 있는 것은 맨 뒷사람(편의상 last라고 두자)이 최대 몇 칸이나 앞으로 움직일 수 있는지를 구하는 문제이다. 따라서 정보들 중에서 내가 관심있게 보는 것은 ( ? , last )라는 정보가 중요하지만 동시에 ? 직전까지 움직일수 있..
[CF 1118F1] Tree Cutting (Easy Version) - 1800 문제 설명 : 빨간색,파란색,무색(색깔 없음)노드로 이루어진 트리가 주어진다. 트리의 간선 (n-1)개 중에서 어느 한 간선을 제거했을 때 만들어지는 2개의 component가 있을텐데, 각 component를 이루는 노드의 색깔이 빨간색과 파란색이 동시에 존재하지 않도록 하는 간선이 몇 개인지 구하는 문제이다. 풀이 : 처음 생각한 것은 각 간선별로 하나씩 지워보고 만들어지는 2개의 component의 노드 색깔을 조사해볼까 생각해봤는데, 노드 수(간선 수)가 최대 30만이므로 이 풀이로는 힘들 것 같았다. 그래서 어떻게든 한 번의 순회만으로 제거할 수 있는 간선을 찾는 것이 유력하다고 생각했다. 정답을 만족시키는 두 ..
[CF 1169B] Pairs - 1500 문제 설명 : 두 개의 정수로 구성된 pair가 총 m개 주어진다. 임의의 정수 2개(x,y)를 선택해서 최소 하나의 정수가 모든 pair에 등장하게 만들 수 있는지 판단하는 문제이다. 풀이 : 정답이 존재하기 위해서는 m개의 pair중에서 임의의 pair 하나를 선택했을 때 둘 중 하나는 반드시 x,y와 동일할 것이다. 그래서 기본 전제로 pair의 0번째 원소(몇 번째 원소인지는 상관없다) 중 하나에 x,y중 하나는 존재한다는 것을 깔아서 이것이 성립할 수 있는지 검증해볼 것이다. pair의 첫 번째 원소의 first와 second를 각각 x라고 가정하고, 다음과 같은 시행을 한다 : m개의 pair에 대해서 두 정수 모두 x와 같지 않다면 need라는 변수..