[Codeforces 1082C]Multi-Subject Competition 문제 설명 : 여러 명의 학생들이 대회에 참가하려고 한다. 대회에는 총 m가지의 종목이 있다. 입력으로 각 학생들이 할 수 있는 종목의 종류와, 그 종목에서의 능력치가 주어진다. 각 종목에 참가하는 학생의 수는 모두 동일해야한다고 할 때, 참가하는 학생들의 능력치의 합이 최대가 되도록 하는 문제이다. 풀이 : 풀이가 엄청 간단한 문제인데 왜 이렇게 어렵게 생각했나 싶은 문제이다. 우선 2차원 벡터를 선언해서 각 종목별로 학생들의 능력치를 저장한 다음 각 종목 별로 능력치 순으로 내림차순 정렬을 한다. 그리고 sum[]이라는 배열에다가 현재 종목의 누적합이 0이상일 때만 더해준다. 이 과정이 끝나면 sum배열의 1~n번까지의 인..
[Codeforces 1082B] Vova and Trophies 문제 설명 : n개의 'G'또는 'S'로만 이루어진 문자열이 주어진다. 여기서 연속된 'G'로만 이루어진 substring의 최대 길이를 구해야 하는데, 최대 한 번 문자열에서 아무 두 인덱스를 골라서 문자를 swap하는 것이 허용된다. 풀이 : swap하는 조건이 없다면 단순히 연속된 문자열의 개수가 몇 개인지 세면 될 것이다. 그런데 swap 조건이 끼어들어서 문제가 조금 까다로워졌다. 예를 들어서 문자열 "GGSGSG"가 있을 때 swap이 없다면 최대 길이는 2 지만, swap을 한다면 3번 째(S)와 6번 째(G)를 swap하면 최종적으로 "GGGGSS"가 되어서 최대 길이는 4가 된다. 이처럼 swap조건이 있을 때는 연속된 '..
[Codeforces 1136C] Nastya Is Transposing Matrices 문제 설명 : ( n x m ) 크기의 행렬 A, B가 주어진다. 여기서 A행렬 안에 속하는 부행렬(sub-matrix)를 임의로 선택하여 Transpose 연산을 수행할 수 있다. 여기서 부행렬의 크기는 반드시 정사각행렬이어야 한다. Transpose 연산을 무제한으로 많이 수행할 수 있다고 할 때 A행렬이 B연산으로 바꾸는 것이 가능한지를 묻는 문제이다. 풀이 :일단 행렬의 Transpose 연산의 특성상 대각선 성분에는 변화가 없고, 그 외에 성분들만 서로 위치를 바꾸게 된다. sub matrix의 크기를 마음대로 설정할 수 있으므로, '행'+'열'을 만족하는 대각성 성분들끼리는 자리를 바꾸는 모든 경우의 수가..
[Codeforces 1133D] Zero Quantity Maximization - 1500 그닥 어려운 문제는 아니지만 stl을 잘 사용하는게 중요한 문제이다. 문제는 c=d*a+b=0을 만족시키는 특정 d값이 있을 때 그 d를 가지는 (a,b) pair가 최대 몇 개인지를 구하는 문제이다. 간단하게 생각해보면 a/b를 실수형으로 구해서 해당 a/b와 동일한 값을 가지는 pair가 총 몇개인지 구하면 되는데 a,b의 범위가 최대 10억씩이기 때문에 소수의 정밀도 오차문제가 생긴다. 따라서 단순하게 a에서 b를 나누는 방식은 위험하다. 그래서 나는 소수형태가 아닌 분자와 분모형태로 표현할 수 있는 분수로 표현해야 한다. 분수로 표현을 하기 위해서는 모든 분수를 기약분수의 형태로 표현해야 한다. 1/2나..
[Codeforces 1132C] Painting the Fence [1,n]구간의 펜스가 있고 총 q개의 painting(색칠) query가 들어온다. 이 q개의 query중에서 2개를 제외한 (q-2)개의 query만 선택해서 색칠된 구간의 수가 최대가 되도록 만드는 문제이다. 구간의 합과 관련된 문제라서 lazy propagation을 써야하는 문제 같았는데 그렇게 하면 시간복잡도가 O(N^2 * logN)시간이 아슬아슬하게 터진다. 게다가 이 문제는 c번 문제였고 푼 사람수도 꽤 있었기 때문에 어떻게든 더 간단히 풀 수 있는 방법이 있다고 생각했다. 콘테스트 당시에 생각한 풀이는 총 q개의 query중에서 색칠의 기여도가 가장 적은 2개의 query를 계산해내는 것이었다. 이러면 q개 중에서 2개..
1100B-Build a contest B번 난이도 치고는 조금 고민해볼 문제였다. 문제는 총 1~n까지 총 n개 종류의 수가 m개 주어진다. 여기서 1~n까지의 숫자가 모두 등장할 때마다 1을 출력하고 그렇지 않을 때는 0을 출력하는 문제다. 만약 모두 등장했다면 다시 1~n까지의 등장 횟수를 모두 1씩 차감해주어야 한다. 가장 naive한 풀이는 매 숫자가 들어올 때마다 1~n까지의 숫자가 모두 유효한지를 검증해보는 것인데, 그러면 시간복잡도는 O(N*M)이다. 이 문제에서 n,m은 최대 10만이므로 이 풀이는 불가능하다. 핵심은 각 시행에서 1~n까지의 숫자가 모두 등장했는지를 어떻게 하면 빠르게 확인하느냐이다. 이 과정을 O(N)보다 빨리 수행하여야 한다. 나는 이를 위해서 cur라는 변수를 추가..
[Codeforces]1102D-Balanced Ternary String 구현력이 얼마나 중요한지 일깨워 주는 문제. 길이가 3의 배수이고 오직 0,1,2로만 이루어진 문자열이 주어진다. 이 문자열에서 등장하는 0,1,2의 빈도는 3개 모두 같도록 만들기 위해서 각 문자를 replace할 수 있는데, 이 때 replace 횟수가 최소가 되도록 하면서 동시에 사전순으로 가장 앞에 있는 문자열을 구하는 문제이다. 문제 난이도는 D번 치고 그렇게 어렵지는 않고, 실제로 이 문제를 접했을 때 솔루션도 금방 나왔다. 0,1,2의 등장 횟수가 n/3이 되도록 맞춰주기 위해서 많이 등장한 숫자는 적게 등장한 숫자에게 자신의 자리를 양보해주는 식이다. 그러면서 사전순 정렬도 고려해야 하기 때문에, 0이 제일 먼저 나..
1085C-Connect Three 격자무늬 상에서 좌표 3개가 주어지고 그 좌표 3개를 모두 이으려고 할 때, 방문해야 하는 격자의 수를 최소로 해야하는 문제이다. 논리적으로 이러이러해서 이렇게 풀어야 한다기보다는, 스스로 여러가지 테스트케이스를 만들어보면서 끄적이다보니 규칙을 자연스럽게 발견하게 되는 문제라서 이런 문제는 참 설명하기가 어렵다. 일단 솔루션을 먼저 설명하고 밑에서 왜 다른 케이스는 정답이 될 수 없는지(최소가 아닌지)에 대해서 설명하겠다. A(1,2) B(4,3) C(5,1) 이 있다고 가정해보자. 1. 세 점 중에서 x좌표가 가장 큰 점과 가장 작은 점을 찾는다.(나는 정렬을 사용했다)2. 그런 다음, 다시 세 점 중에서 y좌표가 중간(가장 크지도 않고, 가장 작지도 않은)점을 찾는..