블로그 옮겼습니다

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

unordered_map, unordered_set 과 같은 해쉬맵 자료구조에서 해쉬값을 만드는데에 사용하는 해쉬 함수의 디폴트가 컴파일러 마다 다른데MSVC++ 에서는 어떤상황에서든 잘 돌아가는데G++ 에서는 디폴트 함수가 하위 16비트만 보고 해쉬값을 만들기때문에 해쉬값은같지만 실제 값은 다른 값들이 많이 존재하는 상황이 발생할 수가 있다고 한다. 이런 최악의경우에 시간 복잡도가 O(N) 이 걸리게 된다는 문제가있다..... 그러므로 입력 데이터가 골고루 나오는경우가 아니거나 hack 이 가능한 탑코더나, 코드포스와 같은 CP 환경에서는 직접 해쉬함수를 정의하여 unordered 의 세번째 인자로 넣어주거나, 굳이 O(1) 에 계산할 필요가없고 편하게 하려면 그냥 set, map 을 쓰자.. 세번째 ..