상위 99.99%의 PS

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

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$에 대..

업솔빙을 다 할 때까지 후기를 쓰지 않으려 했고, 그렇게 업솔빙을 끝낸 지금 후기를 쓴다. 대회 결과는 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를 사용하여 위치를 찾을 수 있다. 그 다음, 한..