-
[BOJ] 2496: 금강석
2496: 금강석 풀이 (x, y)의 좌표계를 변환하자. (x, y) => (x+y, x-y)로 좌표를 변환시키면 좌표계가 45도 기울어지고, 점 사이의 간격이 root(2)배만큼 늘어난다. 좌표계를 돌리고 나면 마름모가 정사각형이 되므로, 문제를 풀기 한결 수월해진다. T가 100밖에 안 된다는 점을 주목하자. 정답에 포함되는 어떤 금강석들의 집합이 있다고 하자. 이 금강석들을 포함하는 사각형은, 얘네들을 모두 포함하는 선에서 이리저리 잘 옮길 수 있을 것이다. 정답을 벗어나지 않는 선에서, 사각형을 최대한 오른쪽 아래로 땡겨보자. 항상 두 개의 금강석이 왼쪽과 위쪽 변에...
-
[잡담] 최근에 재밌게 푼 유형
최근에 접한 문제들 중에서 재밌게 풀었던 것들을 몇 개 적습니다. 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>...