문제링크 - http://codeforces.com/problemset/problem/785/E문제 풀이순열 \(a[ \ ] = \{1, 2, ..., n\} \ (1 \le n \le 200000)\) 에 대하여 특정 위치 \(l_i\) 과 \(r_i\) 의 값을 바꾸는 연산이 \(q \ (1 \le q \le 50000)\) 번 수행될 때, 매 연산 후 순열에 존재하는 역접(inversion)의 수를 세는 문제다. 역접의 수는 크기가 \(a[x] > a[y] \ (x a[r]\) 이면 역접의 수가 1 감소한다. 위의 내용들에서 서로 상쇄되는 것들을 제거하고, 통합하면 아래와 같이 간결하게 역접의 수 변화를 확인할 수 있다. \(a[l] < a[r]\) 이면, \((l 0) { ret += tree[p..
문제링크 - http://codeforces.com/contest/777/problem/E문제 분류난이도 - 중태그 - dynamic programming, data structure, segment tree문제 풀이내부 반지름의 길이 \(a_i\), 외부 반지름의 길이 \(b_i\), 그리고 높이 \(h_i\)가 주어진 여러 개의 링들을 최대한 높게 쌓는 문제다. 일단 아래와 같이 2차원 평면으로 보면 (1) \(b_i\)가 증가하는 순으로, (2) \(b_i\)가 증가하는 순으로 정렬해야할 필요성을 느낄 수 있다. 완전 탐색을 할 경우 \(O(2^n)\)으로 문제를 해결할 수 있다. 너무 느리므로 동적계획법을 고민해보면 아래와 같은 점화식을 찾을 수 있다. \(dp[i]\): \(i\)번 링을 맨 밑..
- Total
- Today
- Yesterday
- Heap
- tree
- Square root decomposition
- karatsuba
- greedy
- Segment Tree
- sort
- Strings
- branch and bound
- BFS
- sliding window
- implementation
- pattern matching
- Data structure
- Fenwick Tree
- parametric search
- kmp search
- Dynamic Programming
- Binary search
- suffix array
- constructive algorithms
- search
- Graph
- math
- Minimum Spanning Tree
- divide and conquer
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |