PS 일지

나중에 까먹을 때를 대비한 기록용 포스팅 레퍼런스 : https://justicehui.github.io/hard-algorithm/2019/05/22/Li-Chao-Tree/(설명도 쉽게쉽게 되어있어서 많이 도움되었습니다.)  핵심은 특정 구간에서 Line들의 lower(혹은 upper) hull을 관리할 수 있다는 것이다.CHT 문제를 풀 때 사용할 수 있다. +) 덤으로 Dynamic Segment Tree에 대한 개념도 공부하게 되었다.필요 시에만 노드를 생성하며, 직선이 존재할 수 있는 범위가 $[s,e]$일 때 하나의 쿼리에 $O(log(e-s))$개의 노드만 추가된다.

9/9 ~ 10/11 BOJ 4167 - Tunnelling the EarthGold 3Elapsed Time : --Rating : 1224 -> 1208 (-16) 소수점 문제인 것을 보고 도망쳤다. BOJ 10021 - Watering the FieldsGold 3Elapsed Time : 5m 36sRating : 1208 -> 1233 (+25)#mst 좌표평면에서의 기본 MST 문제이다. BOJ 7639 - Counting PixelsSilver 1Elapsed Time : 13m 16sRating : 1233 -> 1241 (+8)#math #geometry 답은 r값만으로 정해진다. 원의 방정식을 이용해서 구해주었다. BOJ 26650 - 그램팬Silver 1Elapsed Tim..

9/2 ~ 9/4골랜디도 제대로 못하는 실력임을 깨닫고 가는 날이었다. BOJ 2063 - 철사 연결Silver 1Elapsed Time : 39m 36sRating : 1244 -> 1258 (+14)#greedy #sorting 반원 모양인 건 중요하지 않고, 철사의 시작 ~ 끝의 길이가 지름임을 알면 된다.몇 개를 골랐을 때 가장 큰 것의 길이가 나머지의 합보다 작거나 같으면 YES이다.문제를 잘못 읽어서 30분동안 삽질을 했다. BOJ 4895 - Stock ChaseGold 4Elapsed Time : --Rating : 1258 -> 1216 (-42) 너무 어려웠다. pass하고 태그를 깠는데 여전히 풀 수 없었다. BOJ 23506 - CoinsGold 4Elapsed Time : ..

문제 풀이를 재미있게 해주는 랜덤 디펜스 확장 프로그램을 발견했다.매번 직접 하기 귀찮기도 해서 한 번 체험해보았다. BOJ 17827 - 달팽이 리스트Silver 2Elapsed Time : 7m 55s Rating : 1000 -> 1029 (+29)#implementation 사이클의 길이를 구해서 $K$를 적절히 $N$밑으로 내려주면 된다. BOJ 4358 - 생태학Silver 2Elapsed Time : 3m 12sRating : 1029 -> 1055 (+26)#map map으로 나온 횟수 저장 BOJ 15787 - 기차가 어둠을 헤치고 은하수를Silver 2Elapsed Time : 9m 24sRating : 1055 -> 1078 (+23)#bitmask 각각의 기차는 비트마스크를 이..

문제https://www.acmicpc.net/problem/20156 $i$번 정점의 부모가 $p_i$인 포레스트가 주어지고, 아래와 같은 쿼리가 $M$개 주어진다.$x$ : $x$와 $x$의 부모를 잇는 간선이 아직 존재한다면, 끊는다. 이 때, 아래와 같은 질의 $K$개를 처리해야 한다.$a$ $b$ $c$ : $a$번 쿼리까지 수행되었을 때, $b$와 $c$가 연결되어있는가? 풀이쿼리에 의해 끊어지는 간선들은 모두 끊어놓고 질의를 오프라인으로 처리한다.쿼리를 역순으로 수행하면 간선을 잇는 쿼리로 바뀌며, 각 질의는 분리 집합으로 해결할 수 있게 된다. #include using namespace std;using ll = long long;int root[100001]{};int find(int ..

문제https://www.acmicpc.net/problem/13907 간선의 가중치가 시간 $t$에 대한 일차함수의 형태인 무방향 그래프와, 정수 $s, e$가 주어진다.특정 시간 $t$에서, $s$에서 $e$로 가는 최단 거리를 구해야 한다. 풀이최단 경로에는 어떠한 경우에도 같은 간선이 두 번 이상 포함되지 않는다. 즉, 최대 $N-1$개의 간선만을 지난다.따라서 다음과 같은 정의를 쉽게 떠올릴 수 있다.$dist[n][k]$는 $s$번 도시에서 $n$번 도시까지 $k$개의 간선을 지나서 갔을 때의 최단 거리이제 그대로 다익스트라를 돌려주고, 쿼리가 주어질 때마다 $psum += p$ 후에 $\min(dist[e][j] + j \times psum)$을 출력하면 된다. #include using n..

문제https://www.acmicpc.net/problem/25549 $N$개의 정점으로 구성된 루트 있는 트리의 각 정점에 정수가 하나씩 쓰여있다.$mex(i)$를 $i$번 정점을 루트로 하는 서브트리의 정점에 적혀 있지 않은 수 중에서 가장 작은 음이 아닌 정수라고 할 때, $1 \le i \le N$인 모든 $i$에 대해 $mex(i)$를 출력해라. 풀이정점 $i$의 서브트리에 적혀 있는 모든 수의 집합(std::set)을 $S_i$라 하자.dfs를 돌면서 부모 정점 $n$과 그 자식 정점들 $c_1, c_2, \ldots, c_j$에 대해, $S_n$과 $S_{c_1}, S_{c_2}, \ldots, S_{c_j}$를 모두 합쳐서 $mex(n)$을 직접 구하는 풀이가 가능하다.집합을 small ..

문제https://www.acmicpc.net/problem/15683 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 ..

4/21BOJ 27452 - (재밌고 웃기고 센스있고 깔끔한 제목)Platinum 5더보기#recursion $|S_i|$가 $10^{18}$보다 커지는 $i$의 최솟값을 찾아서 주어지는 $n, k$를 그 범위 안으로 끌어내리고 그 때부턴 직접 재귀로 찾아주면 된다. BOJ 12963 - 달리기Platinum 3더보기#greedy #disjoint_set 도로를 역순으로 하나씩 배치하면서 $0$과 $N-1$을 잇게 되면 그 가중치만큼의 사람을 이동시켜주면 된다.$i$번 도로가 배치되어있다고 가정하면, $i-1$번 이하의 모든 도로 사람들을 수용할 수 있다. $3^i > 3^{i-1} + \cdots + 3^0$이기 때문이다. BOJ 27894 - 특별한 숙제 순서 바꾸기Platinum 4더보기연산을 ..

4/11BOJ 24136 - 冊子の配布 (Distribution)Platinum 4더보기#greedy #dfs dfs를 $M$번 돌리며, 돌 때마다 가장 이득이 되는 리프 노드를 찾으면 된다. BOJ 15900 - 나무 탈출Silver 1더보기#dfs 루트에서 모든 리프까지의 거리 합을 구하면 된다. BOJ 13164 - 행복 유치원Gold 5더보기#greedy #sorting 인접한 두 원소의 차 중 큰 값을 $N-K$개 더하면 된다. BOJ 22104 - Три ладьиGold 3더보기#case_work 주어진 판에서 나올 수 있는 서로 다른 경우의 수는 6가지밖에 없다. BOJ 11000 - 강의실 배정Gold 5더보기#sweeping #priority_queue 우선순위를 절댓값이 작..