블로그 옮겼습니다

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부터 시작)만약 답이 여러개라면 가장 작은 길이의 배열을, 그래도..