상위 99.99%의 PS

BOJ 26268 문제 링크 \(DP_{N}\)을 '\(N\)번째 은행을 반드시 털었을 때, 최대로 벌 수 있는 돈'으로 정의하자. \(i\)번째 은행을 털고, 그 다음에 \(j\)번째 은행을 털기 위해서는 \(X_j - X_i \leq T_j - T_i\)여야 한다. 이걸 그냥 다 찾아보면 \(O(N^2)\)가 되므로, 부등식을 건드리자. \(X_i - T_i\)보다 작거나 같은 \(X_j - T_j\)를 가지는 \(j\)에 대해서만 확인해주면 된다. 세그를 섞어주자. BOJ 8149 문제 링크 이분 탐색을 걸어주면, 결정 문제로 바뀌게 된다. 가장 가벼운 \(mid\)개의 추를 뽑아주자. 여기에서, 공간이 가장 많이 남은 컨테이너에 가장 무거운 추를 넣어주는 것이 이득이므로, 우선순위 큐를 이용해 열..

https://www.acmicpc.net/problem/12746 12746번: Traffic (Large) 사람들이 가장 많이 이용하는 구간을 출력하고, 몇 명의 사람들이 그 구간을 거쳤는지 출력한다. a b c 꼴로 출력하면 되는데, 이는 사람들이 가장 많이 이용하는 구간이 a번 역과 b번 역을 연결하 www.acmicpc.net [알고리즘 분류] LCA Topological Sort DP 웰노운 비빔밥 문제다. 먼저, 트리 위의 경로는 LCA를 이용하여 두 경로의 합으로 쪼갤 수 있다. 이 위에 값을 1씩 올려주는 과정은 imos법을 사용하면 된다. 아래에서 위로 올려주며 값을 더해줄 것이다. 이렇게 하기 위해서는 정점 \(u\)와 정점 \(v\)에 \(1\)을 더해주고, \(lca(u, v)\)..

https://www.acmicpc.net/problem/1376 1376번: 민식우선탐색 첫째 줄에는 정점의 개수 N(

https://www.acmicpc.net/problem/23750 23750번: Leader-based Team Distribution 플레이어 $N$명이 $M$개의 팀으로 나누어 게임을 진행하려 한다. 각 팀의 인원수는 $t_1,$ $t_2,$ $\cdots,$ $t_M$이며, $i$번째 플레이어는 리더 점수 $L_i$와 플레이어 점수 $P_i$를 가진다. 각 플레이어는 www.acmicpc.net [알고리즘 분류] Greedy 꽤 웰노운 그리디인 것 같다. 가장 중요한 관찰은 \(L_i\)가 가장 높은 사람이 무조건 리더가 된다는 것과, 여기에서 어떤 사람을 팀에 할당해도 리더는 변하지 않는 것이다. 그러면 이 성질을 활용하여, 계속하여 적절한 \(L_i\)를 뽑아보자. \(L_i, P_i\)에 대..

https://www.acmicpc.net/problem/26104 26104번: Empty Quadrilaterals Your program is to read from standard input. The input starts with a line containing an integer $n$ ($1 ≤ n ≤ 300$), where $n$ denotes the number of points in the set $P$. In the following $n$ lines, each line consists of two integers, ranging from $-1 www.acmicpc.net 대회 당시 못 풀어서 한이 맺힌 문제다. 너무 화나서 대회가 끝난 이후로 계속 고민해서 풀었다. 어떤 다각형 내..

https://www.acmicpc.net/problem/20306 20306번: 블랙홀 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. ($3 \le N \le 100\ 000$, $1 \le K \le M \le 100\ 000$) 둘째 줄에 블랙홀의 특이점의 좌표가 주어진다. 셋째 줄부터 $N$개 줄에 걸쳐 블랙홀의 꼭짓점들의 좌표가 반시 www.acmicpc.net [알고리즘 분류] 이분 탐색 + 스위핑 일단 정해는 점과 직선의 거리를 이용하여 각 점이 블랙홀에 먹히는 시간을 구하는 것이다. 나는 귀찮아서 그냥 파이썬을 이용해 이분 탐색으로 시간을 구했다. 먼저 360도 정렬을 한다. 블랙홀이 커질 때, 각 집이 어떤 선분에 제일 먼저 닿는지 구할 수 있다. 이 선분이 언제 집을 집어삼키는지..

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 레이지 세그 활용으로 매우 좋은 문제라고 생각한다. 구간을 섞어주면, 이 구..

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가지 경우 각각 맨해튼 거리를 비교해주면 된다. 도둑이 ..

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