[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일 때의 구간이라고 하자. 단순히 ..
[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에서..