목록비둘기집의 원리 (3)
블로그 옮겼습니다
UVa OJ 11898 - Killer Problem
문제 링크 \(N\leq{2\cdot{10^5}}\)\(1\leq{a_i}\leq{10^4}\)\(Q\leq{10^4}\)\(1\leq{l_i},\,{r_i}\leq{N}\) (\(l_i= 10000 일때는무조건 0을 출력, 그 외의 경우에는 그냥 직접 정렬을 해서 순회하며 답을 찾으면된다.그러면 각 쿼리마다 최악의 경우 O(KlgK) (K
Algorithm/Problem Solving
2017. 5. 6. 09:31
Codeforces Round #119 (Div. 1) B. AlgoRace
그래프 + dp 이다. N
Algorithm/Problem Solving
2017. 3. 26. 01:10
Codeforces Round #319 (Div. 2) B. Modulo Sum
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 을 봤는데 두가..
Algorithm/Problem Solving
2017. 2. 25. 12:36