상위 99.99%의 PS

BOJ 26268 문제 링크 $D{P}_N$을 '$N$번째 은행을 반드시 털었을 때, 최대로 벌 수 있는 돈'으로 정의하자. $i$번째 은행을 털고, 그 다음에 $j$번째 은행을 털기 위해서는 $X_j-X_i\le 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$가지의 모든 쌍들에..