PS 일지

BOJ 20156 - 기왕 이렇게 된 거 암기왕이 되어라 [C++]

문제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 ..

BOJ 13907 - 세금 [C++]

문제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..

BOJ 25549 - 트리의 MEX [C++]

문제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 ..

BOJ 15683 - 감시 [C++]

문제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월의 문제 풀이 - (3)

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/11 BOJ 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 우선..

너무 오래 쉰 것 같다. 종강을 하고도 PS는 종종 했지만, 글 쓰는게 귀찮아서 방치하다가 4개월치나 밀려버렸다. 한 번에 쓰기에는 문제 수가 너무 많아서 4월부터 다시 시작하려 한다... 4/2 BOJ 4384 - 공평하게 팀 나누기 Gold 1 더보기 #knapsack #dp 모든 사람들의 몸무게 합은 $45\,000$ 이하이고, 사람의 수가 $100$명 이하이다. 따라서, 사람이 한 명씩 추가될 때마다 (몸무게 합, 사람 수)로 가능한 경우를 knapsack dp로 갱신해주면 된다. BOJ 1043 - 거짓말 Gold 4 더보기 #bfs 주어진 $M$개의 파티 정보로 양방향 그래프를 만들고, 진실을 아는 사람들을 시작점으로 한 뒤 bfs를 돌려주자. bfs 수행 중에 만나는 모든 사람들에게는 거짓말..

Round 917에서 내 실력에 허무함을 느끼고 한동안 PS를 하지 않았었다. 그러다 블루 복귀를 위해 간절함을 가지고 다시 시작하게 되었다. A - Square (00:02) 네 개의 점이 사각형을 이루는 것이 보장되므로 네 점에 대한 $x$, $y$좌표의 최소, 최댓값을 구해 놓으면 넓이를 구할 수 있다. B - Arranging Cats (00:08) 두 수열에 대해 같은 인덱스끼리 xor을 해주고 다시 저장하면, 변화를 줘야 하는 박스들만 남는다. 두 수열에서 남은 $1$의 수 중 최댓값 만큼의 작업으로 두 수열을 같게 만들 수 있다. C - Sending Messages (00:16) $m_i$에서 $m_{i+1}$로 갈 때, 폰을 껐다가 다시 키는 경우와 쭉 켜두는 경우 중 더 작은 값에 해당..

이번 라운드가 역대 최저점 퍼포먼스를 찍은 라운드였다... A번을 풀고 B를 보는데 풀이가 바로 생각나는 게 없어서 나머지 문제들을 둘러봤다. E를 풀 수 있을 것 같아서 여기에 시간을 다 쏟아부었는데, 왜 틀리지 하다가 반례가 생각났고 고칠 수 없어서 그냥 포기해버렸다. A - Least Product (00:04) 배열에 $0$이 있거나 음의 원소 개수가 홀수이면, 아무런 작업을 하지 않았을 때 전체 곱이 최소가 된다. 그렇지 않으면, $0$이 아닌 원소들 중 아무 원소에 작업을 1회만 하면 전체 곱이 최소가 된다. B - Erase First or Second Letter ??? C - Watering an Array ??? D - Yet Another Inversions Problem ??? E ..

Codeforces Round 915 (Div. 2) 에 참가했다. 이번 라운드는 내 안일한 판단때문에 아쉬웠던 라운드였다. 무지성 제출을 하면 안 된다는 걸 배워가는 좋은 기회라고 생각해야겠다. A - Constructive Problems (00:04) 문제가 $n\times n$ 정사각형일 때를 생각해보면, 답은 $n$임을 쉽게 알 수 있다. $n\times m$ 격자에서, 우선 $\min(n, m)$ 크기의 정사각형을 모두 build할 수 있다. 남은 직사각형의 크기가 $x \times y$ 라면, $\min(x, y)$ 크기의 정사각형을 또 모두 build할 수 있다. $\vdots$ 이 과정을 반복해서 정답을 구하면 $\max(n, m)$이 된다. B - Beginner's Zelda (00:..