최근에 접한 문제들 중에서 재밌게 풀었던 것들을 몇 개 적습니다.
set에 다항식 넣기
17196: Cow Steeplechase II
선분이 N개 주어집니다. 단 하나의 선분을 제거하면, 어떤 선분쌍도 교차하지 않음이 보장됩니다. 제거해야 하는 선분은?
x축 정렬하고 스위핑 합니다.
선분의 시작점을 만나면 set에 넣고, 끝점을 만나면 set에서 뺍니다.
i번째 선분을 a[i] = { sx,sy, ex,ey }라고 합시다.
-
선분의 시작점을 만나면: (
a[i],a[i].sy에서 위로 가장 가까운 선분), (a[i],a[i].sy에서 아래로 가장 가까운 선분) 두 쌍을 교차판정 합니다. -
선분의 끝점을 만나면: (
a[i].ey에서 위로 가장 가까운 선분,a[i].ey에서 아래로 가장 가까운 선분) 한 쌍을 교차판정 합니다.
관리 중인 선분들의 x에서의 y좌표를 알기 위해서, set operator로 f(x) = ax+b 식을 정리해서 직선처럼 관리합니다.
교차하는 순간 교차하는 두 선분 중에 둘 중 하나가 답입니다.
어떤 두 선분이 교차하면 부분 순서가 깨지기 때문에 바로 break 합니다.
반대로 얘기하면, 교차하지 않으면 부분 순서는 깨지지 않습니다.
int n, cur_x;
struct line {
int idx;
pll u, v;
double ypos(pll u, pll v)const {
if (v.fst == u.fst) return u.snd;
return u.snd+((double)v.snd-u.snd)*(cur_x-u.fst)/(v.fst-u.fst);
}
bool operator <(line a)const {
return (idx != a.idx) && (ypos(u, v) < ypos(a.u, a.v));
}
} a[111111];
17026: Mountain View
1사분면에 (x, y)를 꼭짓점으로 하는 직각 이등변 삼각형이 N개 주어지고, 꼭짓점이 다른 삼각형에 포함되지 않는 것의 개수를 세는 문제입니다.
(아래가 정해는 아니고, 좌표계 45도 기울어서 대충 짜면 됩니다.)
어떤 점 i를 기준으로 왼쪽 점들을 관리하는 set, 오른쪽 점들을 관리하는 set을 둡니다.
변의 기울기가 왼쪽은 -1, 오른쪽은 1이므로, 왼쪽 삼각형들은 오른쪽 변만, 오른쪽 삼각형들은 왼쪽 변만 고려해 주면 됩니다.
하나의 변이라도, a[i]보다 크거나 같으면 안 됩니다. 외에는 모두 됩니다.
식을 잘 정리하면 x = a[i].x에서의 y좌표를 모든 선분에 대해 구할 수 있습니다. (직선이라고 생각합시다.)
set operator를 ‘직선 f(x)에서, f(a[i].x)가 가장 큰 것’을 뽑도록 주면 부분 순서를 유지하면서 스위핑 할 수 있습니다.
struct abc {
int x, y;
bool operator <(abc a)const {
int r1 = y-abs(x-curx), r2 = a.y-abs(a.x-curx);
if (r1 == r2) return x==a.x?y<a.y:x<a.x;
return r1 > r2;
}
} a[111111];
set<abc> lft, rgt;
다시 돌아가서, 이 문제를 좌표계 45도 기울이는 풀이로 갑시다.
좌표계를 45도 돌려놓고 보면, (0, 0)에서 시작하는 직각사각형이 N개 있고, 최외곽에 있는 점들을 세어주면 됩니다.
이렇게 최외곽 점과 내부 점 뭐 이런 느낌으로 잘 관리하는 문제를 Envelope라고 부르는 거 같습니다.
이 문제는 쉬운 편이라 별로 해당은 없습니다.
Envelope
15977: 조화로운 행렬
풀이만 알고 코딩은 안 해 봤습니다.
일단 1행을 기준으로, 열을 통째로 오름차순으로 정렬합니다.
그러면 1행은 오름차순 정렬, 나머지 행들은 비정렬 상태가 됩니다.
행이 2개인 subtask는 2행에서 LIS 구하면 됩니다.
만점 풀이를 봅시다.
각 행을 순서대로 a[], b[], c[]라고 합시다.
a[l] < a[r] && b[l] < b[r] && c[l] < c[r], l < r을 만족하는 최대 길이를 구하는 게 문제입니다.
a[]는 1행을 기준으로 정렬했으므로 조건에서 고려하지 않아도 됩니다.
이제 b[l] < b[r] && c[l] && c[r]을 만족해야 합니다.
이를 나이브하게 구하면 (b[i], c[i])를 2차원 좌표로 보고 2d seg 같은 걸 쓰면 됩니다.
그리고 envelope을 이용하는 풀이는
각 b[i]와 c[i]에 대해 lis[i] = 1~i점만 봤을 때의 LIS 길이라고 둡시다.
여기서 lis[i] 배열을 관찰하면, lis[i] 값이 똑같은 원소들은 i가 증가함에 따라 값이 내림차순임을 알 수 있습니다.
근데 쓰기 귀찮네요 여기에 풀이가 있습니다.
17411: 가장 긴 증가하는 부분 수열 6
이것도 여기
분할정복, 세그트리, 스위핑
5419: 북서풍
얘도 envelope처럼 생기긴 했는데 사실 뭐 그냥 스위핑입니다.
풀이는… 쓰기 귀찮네요…
좌표압축하고 x축으로 스위핑하면서 a[i].y 보다 작은 y좌표 개수 세어주면 됩니다.
16993 : 연속합과 쿼리
10167: 금광
TODO
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이