상위 99.99%의 PS

https://www.acmicpc.net/problem/18619 18619번: Alakazam The first line contains two integers n, q (1 ≤ n ≤ 250 000, 1 ≤ q ≤ 250 000) — the number of Alakazam in the line and the number of actions during the training. The following line contains n integers a1, a2, . . . , an (1 ≤ ai ≤ 106) — the www.acmicpc.net [알고리즘 분류] Segment Tree with Lazy Propagation 레이지 세그 활용으로 매우 좋은 문제라고 생각한다. 구간을 섞어주면, 이 구..

Convex Hull 2차원 평면 위의 점들을 모두 포함하는, 넓이가 최소인 볼록 다각형을 구해보자. 이는 볼록 껍질이라는 것을 구하면 해결된다. 볼록 껍질을 구하는 것은 여러 방법이 있지만, 나는 반껍질 두 개를 구하는 방식을 선호한다. 한 쪽 반껍질을 구하고, 다른 반껍질은 반대로 구하면 되기 때문이다. (저번 게시글에서 볼록 껍질을 구할 때 각도 정렬이 필요하다고 했지만..) 이 방법은 각도 정렬을 하지 않아서 편하다. 일단 반껍질을 구하기 전, x좌표, y좌표 순으로 증가하도록 점들을 정렬하자. 점들을 정렬했다면, 이제 볼록 껍질을 만들 수 있다. 점들을 스택에 넣으며, 마지막 세 점의 방향이 반시계 방향이 되도록 적절히 스택에서 pop을 하면 된다. 글로 쓰는 것은 내가 봐도 설명이 구리기 때문..

기하를 싫어하는 이유 ps를 하는 사람 중 기하를 싫어하는 사람은 꽤나 된다. 물론 나 또한 그랬기에, 기하를 싫어하는 이유가 무엇인지는 대충 알고 있다. 내가 기하를 싫어했던 이유는 이렇다. 1. 코드가 깔끔하게 나오지 않는 편이다. 2. 실수 연산이 까다롭다. 3. 예외처리가 많다. 1번의 경우, 함수를 최대한 많이 사용하면 그나마 깔끔해진다. 사소한 계산이라도 함수를 사용해서 따로 빼주는 게 눈버깅에도 편하다. 2번의 경우, 최대한 정수로 계산하는 편이 낫다. 근데 보통의 문제들은 double형으로 그냥 계산해도 정답이 나올 정도의 오차 범위를 주기 때문에 이를 신경 쓸 일은 그렇게 많지 않...다. 3번의 경우를 내가 진짜 싫어했다. 노트에 대충 끄적이면 그대로 코딩을 하는 매우 나쁜 습관이 있어..

https://www.acmicpc.net/problem/18032 18032번: Dazzling Stars The first line contains an integer N (3 ≤ N ≤ 1000) indicating the number of stars in the constellation. Each of the next N lines describes a star with three integers X, Y (−104 ≤ X, Y ≤ 104) and B (1 ≤ B ≤ 1000), where X and Y are the coordi www.acmicpc.net [알고리즘 분류] 정렬 기하학 어떤 두 점의 방향성이 정해졌다면, 인쇄 방향은 저 파란색 부분의 각도에 들어있어야 한다. 즉, 다른 점들의 ..

BOJ 3881 - 말파티 원 (P5) 더보기 https://forumgeom.fau.edu/FG2003volume3/FG200308.pdf 화이팅.. BOJ 3843 - 볼록 정다각형 (G1) 더보기 정다각형의 모든 꼭짓점을 지나는 원은 유일하다. 가능한 모든 정n각형에 대해, 이 정다각형의 점들에 입력으로 주어진 점이 존재하는지를 확인하면 된다. BOJ 20041 - Escaping (P5) 더보기 도둑은 일자로 이동하는 것이 최선이다. 경찰이 무조건 이기는 경우라면, 만약 도둑이 방향을 틀어도 경찰도 이를 따라 이동하여 도둑을 막을 수 있다. 즉, 좌표 (-INF, 0), (INF, 0), (0, -INF), (0, INF)를 기준으로 잡고 4가지 경우 각각 맨해튼 거리를 비교해주면 된다. 도둑이 ..

https://codeforces.com/contest/1735 Dashboard - Codeforces Round #824 (Div. 2) - Codeforces codeforces.com 진짜 오랜만에 했다. 그리고 C에서 말렸다. A는 식 하나로 답을 확정 가능했고, B는 문제가 뭐였는지 기억이 나지 않는다. C (01:12) 그리디하게 가장 작은 알파벳부터 확인하고, 사이클이 형성되는지 dfs 등으로 확인을 해주면 된다. 26*26*100000=67600000 이지만, 간선 추가는 26번만 이루어지므로 더 빠르게 동작한다. D (01:33) 두 카드가 고정되면 다른 한 카드는 확정된다. 게다가 카드의 종류가 모두 다르기 때문에 5개의 카드에서 최대 두 쌍의 set이 존재한다. 두 개의 카드를 알 ..

피곤하다 BOJ 25569 - My뷰 꾸미기 (P4) 더보기 Vandermonde's identity를 사용하는 문제다. 위키에 있는 걸 그대로 사용하면 됨 BOJ 15634 - Glen (P5) 더보기 우측으로 쭉 이동 -> 한칸 아래로 -> 쭉 왼쪽으로 ... 이렇게 반복하여 내려가면 된다. 그리고 지금 보고 있는 칸이 원하는 상태와 다르다면, 앞으로 갔다가 뒤로 가주고, 다시 앞으로 가주면 된다. BOJ 25201 - 보드 뒤집기 게임 (P5) 더보기 각 행, 각 열의 기우성은 변하지 않는다. 각 행마다 타일의 등장 횟수를 세고, 기우성이 동일한지를 확인해주면 된다. 좋은 문제라고 생각한다. BOJ 1047 - 울타리 (P5) 더보기 N의 값이 매우매우 작다. 가능한 \(N^4\)가지의 모든 쌍들에..

잘해지고 싶다 BOJ 24618 - Robot Instructions (P4) 더보기 N

이걸 밀고싶었는데, 너무 어려워서 결국 포기했다.. BOJ 18184 - 분할하기 (P4) 더보기 가장 높은 곳에서 켜진 비트가 k번째에서 켜졌다고 하면, 이러한 수는 \(2^{k-1}\)개 존재한다. 또한 모든 수는 2의 거듭제곱의 합으로 나타낼 수 있으므로, 답은 항상 존재한다. BOJ 18193 - 비행기 타고 가요 (D4) 더보기 구간 간선 테크닉 + 다익스트라. https://www.acmicpc.net/problem/25392 BOJ 18194 - Bad Hair Day와 기댓값 (P1) 더보기 \(i\)번째 소보다 작은 소가 \(k\)마리라면, 이들보다 큰 소들 \((n-k)\)마리를 먼저 세워볼 수 있다. 여기서 사이사이에, 즉 \((n - k + 1)\)칸에 소 \(k\)마리를 잘 배정할..

최근들어 제대로 된 PS를 하기로 했다. 그냥 무지성으로 웰논 골플 문제를 푸는 것이 아닌, 깊은 생각을 요하는 문제를 풀어야겠다... BOJ 18287 - 체스판 이동 (P2) 더보기 행렬식 dp문제다. 홀수 행렬과 짝수 행렬을 곱해준 행렬을 N제곱하면, 2N번 이동했을 떄의 경우의 수가 된다. 여기에서 \(2k+1\)꼴로 이동하기 위해서는, k제곱한 행렬에 홀수 행렬을 곱해주면 된다. BOJ 24894 - 내적 (P1) 더보기 식을 잘 건드리면 \(\frac{y_i}{x_i}\)에 대한 cht를 할 수 있다. BOJ 10847 - 자카르타의 마천루 (D4) 더보기 그냥 다익스트라 돌리면 된다. 다만 b+kp (k는 자연수)에 동일한 p값을 가진 도게가 있다면 이보다 더 큰 b + (k+1)p부터는 볼..