seojin0305 PS 블로그

알고리즘 lazy_segtree, coor_comp ( map ) 시간복잡도 $O(QlogQ)$ 풀이 문제 조건 상 x좌표가 증가할수록 색칠되어 있는 칸의 수는 감소한다. 따라서 각 쿼리를 $q_x, q_y$라 하면 (색칠되어 있는 칸의 수가 $q_y$ 이상인 가장 작은 x좌표 ~ $q_x$) 구간을 $q_y$로 업데이트 후 전체 합을 구해주면 된다. 이 때 x좌표 범위가 $10^9$까지이므로 좌표압축을 해줘야 한다. 구간 update를 진행해야 하므로 {x좌표 두께를 고려한 넓이, max, min}에 대한 lazy seg로 구현하였다. 기존 lazy seg의 update에서 추가적으로 구간 min이 update할 값 이상이면 return, update 범위 내에 있으며 구간 max가 update할 값 ..

알고리즘 coor_comp, segtree 시간복잡도 $O((M+N)logN)$ 풀이 우선 주어진 모든 좌표(고기의 시작/끝 좌표, 꼬치의 좌표)를 기준으로 좌표 압축을 진행한다. 가능한 값은 최대 $2(N+M)$ 개이다. 이제 각 쿼리별로 진행해보자. 한 꼬치에 꽂힐 수 있는 고기의 종류를 모두 알아내면 쉽게 정답을 구할 수 있다. 우선 고기를 시작 좌표 기준 오름차순으로 정렬한다. 이 경우 각 꼬치에 대해 1번 고기부터 특정 고기까지만 꽂힐 후보가 됨이 보장된다. 이제 고기 후보들 중 실제로 꼬치에 꽂히는 고기를 찾아보자. {끝 좌표의 최댓값, 해당 고기}에 대한 segtree를 만들면, 위에서의 고기 후보 구간 내 끝 좌표가 가장 큰 고기를 알 수 있게 된다. 끝 좌표가 가장 큰 고기도 꼬치에 꽂히..

알고리즘 (segtree) 시간복잡도 $O(NlogN)$ 풀이 $g(K)$, 즉 배열 중 $1\sim K$만을 고려하는 경우를 생각해보자. $f(K, y, z)$가 가질 수 있는 최댓값은 구간 $[l, r]$ 중 $K$ 이하의 원소의 개수이다. 이를 각 원소 관점에서 생각해본다면, 가능한 $g(K)$의 최댓값은 모든 $K$ 이하의 자연수 $i$에 대해 $i$의 값을 가지는 위치를 $p(i)$라 할 때 $p(i) \times (N-p(i)+1)$의 합임을 알 수 있다. $a_1, a_2, ..., a_N$에서 $K$ 이하의 원소만을 고른 부분수열을 $b_1, b_2, ..., b_K$라 하면, $f(K, y, z)$의 실젯값은 위에서 구한 이론적인 값에서 $b_i < b_{i+1} < b_{i+2}$ 또는..

알고리즘 sorting, segtree 시간복잡도 $O(NlogN)$ 풀이 한 가로선 또는 세로선 기준으로 두 직사각형이 구분됨이 보장됨. WLOG 자르는 선을 세로선이라 하면, 각 직사각형당 가로 길이: 미리 sort 해놓은 배열에서의 차, $O(1)$ 세로 길이: 구간에서의 $max-min$, segment tree로 $O(logN)$ (구간이 시작 또는 끝을 포함하므로 prefix/suffix max/min으로도 가능) 코드 #include using namespace std; #define ll long long int N; pair a[50005]; ll x[50005], y[50005], befans, ans = 1e18; struct z { ll mx, mn; }; z xtree[200005..

알고리즘 greedy, dp 시간복잡도 $O(N)$ 풀이 $ad, b->c)$보다 항상 비용이 작음이 증명된다. 따라서 절대 소가 밀릴 일이 없는 지점에서 시계 방향으로 돌 때 가장 가까운 0으로부터 순차적으로 밀어주면 된다. dp를 통해 가장 많이 밀린 지점을 구할 수 있으며, $O(N)$으로 끝에 있는 0부터 채워주면 된다. 코드 #include using namespace std; #define ll long long int N, a[100005], dp[100005]; ll ans; ll add(ll b, ll n) { ll r = 0; for (ll i = 0; i >N; for (int i =..

알고리즘 dp, two_pointer 시간복잡도 $O(NlogN)$ 풀이 현재 점 왼쪽의 모든 점을 연쇄적으로 터뜨릴 수 있는 최솟값을 $dpl[i]$, 마찬가지로 오른쪽의 경우 $dpr[j]$로 구한다. 임의의 두 점에 대하여 두 점 사이 거리의 절반, 앞에서 구한 $dpl, dpr$ 값들 중 최댓값이 전체 최솟값 후보일 것이다. 이를 $O(N^2)$로 구하면 시간초과가 나기에 맨 끝에서부터 two pointer로 관리해주면 된다. (dp값이 작은 것을 밀도록) 코드 #include using namespace std; int N, a[50005], dpl[50005], dpr[50005]; int ans = 2e9; int main() { cin>>N; for (int i = 1; i >a[i]; a..

알고리즘 random 시간복잡도 $O(TKN^2)$ 풀이 $i$번 정점과 $j$번 정점 사이의 인접 연결 정보를 저장한 행렬을 $A$, $i$번 정점과 $j$번 정점 사이 거리가 2인 연결 정보를 저장한 행렬을 $B$라 하면 $A^2 = B$인지 아닌지를 확인하면 된다. 그러나 일반적인 행렬 제곱 시 $O(N^3)$이므로 시간 제한에 걸리게 된다. $Freivalds' \space algorithm$이라는 신박한 알고리즘이 존재한다. $x \in \mathbb{R}^n$라 할 때, $A^2 x = Bx$인 경우 약 $\frac{1}{2}$의 확률로 $A^2=B$이다. 이 곱셈의 시간복잡도는 $O(N^2)$이다. random한 $x$에 대해 10번 확인 시 적중 확률은 99.9%이다. 코드 #include..