상위 99.99%의 PS

https://blog.naver.com/vermeil_ Torch : 네이버 블로그 버메일 / 올리고 싶은 것들 올림 blog.naver.com 여러 이유들로 인해 블로그를 옮겼습니다. 여기에 있던 글들을 옮길 자신은 없어서 글을 옮기지는 않습니다. 서로이웃 추가 환영합니다 ㅎㅎ

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\)에 대..

업솔빙을 다 할 때까지 후기를 쓰지 않으려 했고, 그렇게 업솔빙을 끝낸 지금 후기를 쓴다. 대회 결과는 4등이다. F에서 말린 것을 풀지 못하여 H도 못 풀었고, 꽤나 아쉬움이 남았다. 대회 때 무슨 일이 있었는지와 풀이는 간략하게만 쓰도록 하겠다. 문제는 앞에서부터 풀었다. A 시작하자마자 A 지문을 건너뛰고 예제를 보고, 바로 사칙연산 식을 만들어서 코드를 제출하고 AC받았다. B B는 그냥 빡구현 문제였기에, 열심히 코딩했다. fastio가 빠져서 1틀 적립. C 조합론 기초 문제다. \(k\)개가 같은 경우, \(k!\)으로 나누어주기만 하면 된다. D 맨 처음에 한 쌍을 지울수만 있다면, 0과 1의 개수가 짝수인 한 모든 쌍을 지울 수 있다. 불가능한 경우에 -1이 아닌 0을 출력해서 1틀 적립..

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/workbook/view/13280 문제집: 기하 한 스푼 (lem0nad3) 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도 정렬을 한다. 블랙홀이 커질 때, 각 집이 어떤 선분에 제일 먼저 닿는지 구할 수 있다. 이 선분이 언제 집을 집어삼키는지..

Half Convex Hull 문자 그대로 반껍질이다. 볼록 껍질을 구할 때처럼 하면 된다. BOJ 14745 - Jeong Lab 문제를 다르게 바꾸면 다음과 같다. 용액을 하나의 좌표로 보고, 점 \(Q(c_i, d_i)\)가 반껍질 내에 존재하는 지의 여부를 확인하기. 이는 매우매우 간단하다. lower_bound를 사용하여, 점 \(P_{l}, P_{l+1}, Q(c_i, d_i)\)의 ccw를 확인해주면 된다. 반껍질에 점 추가하기 그러나 이 문제에서 요구하는 것이 하나 더 있다. 반껍질 내에 점이 존재하지 않는다면, 이 반껍질에 점을 추가해주어야 한다. 그리고 반껍질을 다시 구성해야 한다. 먼저, 점이 들어갈 위치를 구한다. lower_bound를 사용하여 위치를 찾을 수 있다. 그 다음, 한..