목록Algorithm/Problem Solving (95)
블로그 옮겼습니다
http://codeforces.com/contest/776/problem/C 1 ≤ n ≤ 105, 1 ≤ |k| ≤ 10 sequence 의 길이 n과 k가 입력으로 주어지고 n개의 원소가 입력으로 주어질때 원소의 합이 k^x 의 형태인 non-empty, continuous subsequence 의 개수를 찾는 문제 우선 모든 경우를 다 따져준다면 O(n^2) 로 TLE 가 난다. 우선 누적합 pSum 을 모든 인덱스에 대해 다 구해준다. 그러면 [l,r] 의 subsequence 의 원소의 합은 pSum[r]-pSum[l-1] 로 나타낼수있다. 즉pSum[r] - pSum[l-1] = k^x 인 (l,r) 쌍의 수를 찾으면 되는데 만약 위의 식이 성립한다면 항을 적절히 넘겨서 이런식을 도출해 낼 ..
http://codeforces.com/problemset/problem/577/B n and m (1 ≤ n ≤ 106, 2 ≤ m ≤ 103) sequence의 길이 n과 m 이 주어지는데 원소의 합이 m 으로 나누어 떨어지는 subsequence 가 있는지 없는지 판별 하는 문제이다. 처음엔 일종의 dp 로dp[i][j] = subArray[~i] 의 subsequence 중 원소들의 합을 m으로 나눈나머지가 j 인 subsequence 가 있는지로 매 배열의 원소마다 선택을 하는 경우와 선택을 하지 않는경우로 나누어서 배열을 update 해주는 식으로 했는데생각해보니 그렇게 되면 시간 복잡도가 O(n*m) 이어서 TLE 가 난다. 좀 생각을 해봤는데 잘 모르겠어서 Editorial 을 봤는데 두가..
https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/practice-problems/algorithm/winter-is-coming-12/description/ 1 ≤ Elements of array ≤ 109 1 ≤ T ≤ 10 1 ≤ N ≤ 100000 여러 테스트케이스에 대해 배열의 크기 N 이 주어지고 N개의 원소가 입력으로 들어온다.각각의 배열의 원소는 1~10억이다.연속된 부분 배열들 중 부분 배열의 원소의 합이 N으로 나누어 떨어지는 부분배열의왼쪽과 오른쪽 인덱스를 구하는 문제이다(인덱스는 1부터 시작)만약 답이 여러개라면 가장 작은 길이의 배열을, 그래도..
http://codeforces.com/contest/767/problem/C 이 문제는 트리가 주어지고 트리의 각각의 노드에 온도가 주어질 때 노드들의 온도의 합이 같은 세 개의 덩어리로 나누는 문제이다. 나눌수 없다면 -1을 출력 있다면 나누는 두 지점을 (답이 여러개일 경우 아무거나) 출력 하는것이다. 이 문제는 크게 세 단계로 나눌 수 있다. 1.루트 노드에서 dfs를 돌리면서 w[i] = i번 노드를 포함하는 서브트리 의 모든 노드들의 온도의 합을 구한다. 2.w[v] 가 w[root] 의 3분의 1이 되는 지점 v들을 모두 구하여 조상들에게 모두 전달해 준다.만약 노드 u 의 자식이 a,b,c 라고 했을때 a,b,c 를 각각 루트로 가지는 서브트리들에 대해 이러한 지점 v 를 가지는 자식들이 ..