-
[잡담] 최근에 재밌게 푼 유형
최근에 접한 문제들 중에서 재밌게 풀었던 것들을 몇 개 적습니다. 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에서 아래로 가장 가까운 선분) 두 쌍을 교차판정 합니다. 선분의 끝점을...
-
[BOJ] 10759: 팰린드롬 경로3
10759: 팰린드롬 경로3 풀이 d[i][j] = 문자열의 길이가 k이고, i행에서 시작해서 j행으로 끝나고, 그 문자열의 중심이 배열의 대각선(왼쪽 아래~오른쪽 위)에 있을 때, 그 문자열이 팰린드롬인 경우의 수 d[k][i][j] = d[k-2][i][j]+d[k-2][i+1][j]+d[k-2][i][j-1]+d[k-2][i+1][j-1] 식은 위와 같고, 배열은 k를 토글링 해서 n^2개만 사용할 것이다. (1,1)~(n,n)의 문자열은 길이가 항상 홀수이다. 중앙의 diagonal 대각선을 기준으로, 팰린드롬의 길이를 앞뒤로 2씩 확장해 나갈 수 있다. (a,b)~(c,d)의 중심이 대각선에 겹치려면, (a-1)+(b-1) = |(c-n)+(b-n)|을 만족해야 한다. (두 점이 각 끝점으로부터 떨어진 거리가 같아야 한다.) a와...
-
[BOJ] 11745: King’s Inspection
11745: King’s Inspection 풀이 M <= N+20이므로, 주어지는 그래프는 최대 20개의 간선만 제거하면 트리가 된다. 즉, 트리와 아주 유사하게 생겼다는 뜻이고, 이는 대부분 노드의 in/out degree가 1이라는 뜻이다. indegree 또는 outdegree가 2 이상인 노드를 special node로 두자. special node에서 다른 speical node까지의 경로를 압축하자. in/out degree가 1인 노드들을 모두 압축해서 하나의 간선으로 치는 것이다. 그러면 노드가 많아야 40개인 그래프가 나온다. 이 그래프에서 TSP를 하면 된다. 코드 #include <bits/stdc++.h> using namespace std; typedef long long ll;...
-
[BOJ] 10167: 금광
10167: 금광 풀이 이 문제와 비슷하게 분할정복으로 접근한다. x축을 기준으로 정렬해서, 모든 [l, r] 구간에서 최댓값을 하나씩 찾을 것이다. 시작점을 하나 정해놓고, 끝점까지 스위핑 하면서 최댓값을 찾아 주자. 스위핑이 하나 전진할 때마다 분할정복 트리를 업데이트 해 주면 된다. 이러한 구간이 많아야 3000^2개이므로 여기에 로그 붙여도 충분하다. 세그트리 업데이트 하는 느낌으로 분할정복을 하면 된다. 나는 멍청하게 구간합 업데이트를 펜윅트리 써서 했는데 여러분들은 그러지 말자. ㅋㅋㅋㅋ 까다로운 반례가 있으므로 주의하자. 코드 #include <cstdio> #include <algorithm> #include <vector>...
-
[BOJ] 16993 : 연속합과 쿼리
16993: 연속합과 쿼리 풀이 분할정복 하는 느낌, 혹은 세그트리 짜는 느낌으로 접근하면 된다. 노드 하나에 3개의 값이 들어가는데, mmax(s, e) = 가운데를 지나는 구간의 최대 합 lmax(s, e) = s를 포함하는 구간의 최대 합 rmax(s, e) = e를 포함하는 구간의 최대 합 위의 것들을 분할정복 하듯이 전처리해서 들고 있는다. 그리고 재귀 세그트리 짜듯이 쿼리를 날리면 쿼리 당 O(log N)에 답을 계산할 수 있다. 코드 #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll...