[Codeforces 1176E] Cover it! 문제 설명 :undirected edge로 이루어진 그래프가 주어진다. 이 그래프에서 최대 floor(n/2)개의 node들을 선택하여 '선택된 node들과, 선택되지 않은 node간의 거리가 1'이 되기 위해서 어떻게 node를 선택해야 하는지 묻는 문제이다. 풀이 : 풀이는 매우 간단하다. 아무 노드에서부터 다른 노드들까지의 최단거리를 구한다(bfs나 dfs를 이용하면 된다). 그러면 그 거리가 짝수인 node들과 홀수인 node들로 그룹이 나눠질텐데 두 그룹 중에서 원소의 개수가 더 작은 그룹이 곧 정답이 되는 것이다.이것이 가능한 이유는 짝수 -> 홀수 -> 짝수 -> 홀수 .... 형태가 반드시 반복된다는 확신이 있기 때문이다. 현재의 노드가 ..
[Codeforces 1151B] Dima and a Bad XOR - 1600 문제 설명 : n by m 크기의 행렬이 주어진다. 행렬의 각 열에서 임의의 숫자를 하나씩 뽑아서 xor를 취한다. 그 결과가 0이 나오지 않는 경우가 있다면 각 열에서 몇 번째 수를 xor해야하는지 출력하고, 아니면 반드시 결과가 0이 나올 수 밖에 없는지 구하는 문제이다. 풀이 : xor연산의 간단한 특성을 알아야 한다. a ^ b =0 을 만족한다면 a = b도 반드시 만족한다. 또한 a^b = 0 이고 b≠c라면, a^c ≠ 0 도 반드시 성립한다.이 두 가지 성질을 가지고 문제를 풀자. 이 문제에서의 관건은 어떤 수들을 xor해야 0이 나오지 않게 만드냐이다. 처음에는 일단 각 열의 첫 번째 원소들(mat[i][1]..
[Codeforces 1153C] Serval and Parenthesis Sequence - 1600 문제 설명 : (,),? 로 이루어진 문자열이 주어진다. 이 중에서 ?로 채워진 칸은 임의로 ( 또는 ) 로 바꿀 수 있다. 이때 strict prefix(길이가 0이거나 n일 때는 제외하는 prefix)는 절대로 올바른 괄호열이 되어서는 안되게하면서, 전체 문자열은 반드시 올바른 괄호열이 되어야 한다. 이 두 조건은 만족하는 문자열을 구하는 문제이다. 풀이 : 처음에는 엄청나게 오답을 꼬라박은 문제이다. 처음 풀이는 여는 괄호 '(' 을 +1, 닫는 괄호 ')'를 -1, 이것들의 누적합을 sum이라고 했을 때 sum이 1이나 2 사이에서만 움직이도록 통제하였다. 하지만 이 풀이는 " ???))) "같..
[Codeforces 919D]Substring - 1700 문제 설명 : directed edge로 구성된 그래프가 있다. 그래프의 각 노드에는 알파벳이 배정되어있다. 그래프의 경로를 지나면서 거쳐가는 노드들의 알파벳중에서 최대 빈도수를 구하는 문제이다. 무수히 많은 빈도수가 나올 때는 -1을 출력한다. 풀이 : 일단 그래프에서 사이클이 존재하는 경우 사이클 내에 있는 알파벳은 무수히 많이 등장할 수 있으므로 -1을 출력하면 된다. 만약 사이클이 없는게 확인된 그래프라면 위상정렬 알고리즘을 사용한다. 각 노드는 각 알파벳이 최대 몇 번 등장할 수 있는지 저장할 수 있는 freq[][]배열을 만든다. 그래서 다음 노드(next)에서 freq배열은 현재 노드의 freq배열과 같은 값을 가지면서, 다음 노드..
[Codeforces 950C] Zebras - 1600 문제 설명 : 문제에서 'zebra'라는 특정 문자열을 정의해주는데 이 문자열은 시작과 끝은 반드시 '0'이어야하고, 0과 1이 번갈아가면서 나타나야한다. 그래서 0과 1로만 이루어진 문자열이 주어졌을 때 이 문자열을 적당히 분할하여 모든 substring을 'zebra' 문자열의 조건을 만족시킬 수 있는지 찾는 문제이다. 풀이 : 0 뒤에는 가장 가까운 1을 찾고, 1 뒤에는 가장 가까운 0을 찾는 방식으로 풀면 된다. 이때 substring의 시작과 끝은 반드시 0이어야하므로, 1로만 시작되거나 1로 끝나는 substring이 발견되었을 때는 불가능처리를 한다. 처음에 이 풀이에 대한 구현을 현재 문자에대한 다음(find)문자를 문자열 끝까지 ..
[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..