JJaewon의 PS하는 블로그

4.2 ~ 4.11 동안 푼 문제 정리 산만한 고양이 https://www.acmicpc.net/problem/14866 DFS 스패닝 트리를 만들고 Tree DP 느낌으로 서브트리 내부의 Back Edge들을 잘 카운트하고 케이스 분류하면 각 정점의 자식들을 확인하면서 사이클을 제거할 수 있는지 판단 가능하다. The Bridege on the River Kawaii https://www.acmicpc.net/problem/16695 처음 보면 좀 무서운데, $V

Link https://www.acmicpc.net/problem/10129 POI 2013/2014 Stage 2 3번 Tag dp Time Complexity $O(QN)$ $N$개 나무의 높이가 주어지고, $Q$마리의 새가 1번 나무에서 N번 나무까지 날아간다. 각 새는 한번에 $k_i$ 그루의 나무만큼 날아갈 수 있고, 현재 위치한 나무보다 높이가 같거나 높은 나무로 날아갈때 피로감을 느낀다. 각 새의 피로감 느끼는 횟수를 최소화해야한다. 쿼리가 있긴 한데 $Q\le 25$이라 그냥 따로따로 풀어도 상관없다. dp 점화식은 쉽게 나온다. $dp[i]=min(dp[j]+C)$ $(i-k\le j<i)$ ($C$는 $h[j]\le h[i]$일때 1, 아니면 0) 모든 j에 대해 고려하면 ..

Link http://codeforces.com/contest/1332/problem/E Codeforces Round #630 (Div. 2) E번 Tag 수학 Time Complexity $O(lg(NM))$ 인접한 두칸을 골라 1씩 증가시키거나 한칸을 골라 2씩 증가시키는 연산을 할 수 있을 때, 모든 칸의 숫자를 같게 만들 수 있는, 각각의 수는 $L$ 이상 $R$ 이하이고 $N\times M$ 크기 격자의 갯수를 구해야 한다. 몇가지 관찰을 통해 해결할 수 있다. 먼저, 한칸을 골라 2씩 증가시키는 연산이 존재하기 때문에 각 칸의 홀짝성만이 중요하다. 두번째, 임의의 두 칸의 홀짝성을 바꿀 수 있다. 두 칸 사이의 경로에다가 인접한 두칸을 골라 1씩 증가시키면 경로상에서 두 칸의 홀짝성은 반전..

Link https://atcoder.jp/contest/abc159/tasks/abc159_f AtCoder Beginner Contest 159 F Tag dp Time Complexity $O(NS)$ 길이 N인 수열과 정수 S가 주어진다. $f(L,R)$ 은 수열에서 L이상 R이하 인덱스로 만들수 있는 합이 S인 부분집합의 갯수로 정의된다. 이때 모든 $(L,R)$ 쌍에 대해 $f(L,R)$의 합을 구해야 한다. 일단 $L=1$로 고정했다고 생각해보자. $dp[i][j]$ := (1 ~ i)까지 선택해서 합이 j가 되는 경우의 수 로 정의하면, 냅색처럼 $O(NS)$에 dp 배열을 채울 수 있다. 이때 초기값으로 $dp[i][0]=1$로 했을 것이다. $L = 2, 3, ... , R..

Link https://www.acmicpc.net/problem/14164 USACO 2016 December Platinum 1번 Tag 기하 Time Complexity $O(N^3)$ 점 N개가 있고, 이 중 3개를 택해 삼각형을 만들때 내부에 점이 i개 (0≤i≤N-3) 있는 삼각형의 갯수를 구해야 한다. $O(N^2)$ 개의 선분에 대해 왼쪽에 있는 점의 갯수를 ccw를 이용해 각각 $O(N)$, 총 $O(N^3)$에 전처리한다. cnt[i][j] = 선분 ij 왼쪽에 있는 점의 갯수 라고 하면, 삼각형 ABC 내부의 점의 갯수는 cnt[A][B], cnt[B][C], cnt[A][C]로 나타 낼 수 있다. 따라서 $O(N^3)$ 개의 삼각형에 대해 내부의 점 갯수를 $O(1)$..

Link https://www.acmicpc.net/problem/2452 KOI 2011 전국본선 중/고등부 4번 Tag bfs Time Complexity $O(N^2{M}^2)$ 흰색/검은색 돌로 구성된 $N\ast M$ 격자가 주어진다. 어떤 돌을 선택해 뒤집으면 같은 색으로 연결된 컴포넌트들이 전부 뒤집힌다. 전체 격자를 같은 색으로 바꾸기 위해 필요한 최소한의 뒤집기 횟수를 구해야 한다. 가장 중요한 관찰은, '처음 뒤집은 돌을 계속 뒤집어도 된다'는 것이다. 따라서 $N\ast M$개의 돌을 모두 시도해 보면서, 그 돌만 눌렀을때 총 몇번 뒤집어야 하는지 계산하면 된다. 인접한 돌들끼리 간선을 연결하고, 같은 색끼리는 0, 색이 다르면 1의 가중치를 가지는 그래프를 생각해 보자. 이때 $(sx, sy)..

Link https://www.acmicpc.net/problem/18798 2020 SciOI #1 A번 Tag 세그먼트 트리 Time Complexity $O(NlgX+QlgN)$ 길이 $N$ 인 수열 $A$ 가 주어지고, 음이 아닌 정수가 $K$ 가 주어진다. 구간 bitwise OR 쿼리와 구간 내 $K$ 와 같은 수의 개수를 묻는 쿼리에 응답해야한다. 2번 쿼리는 구간 합 세그먼트 트리를 만들어 쿼리를 날리면 되므로, 1번 쿼리를 처리하는 방법을 알아보자. 풀이의 핵심은 bitwise OR의 성질에 있다. 어떤 비트가 1이 되고 나면, 다시 0이 되는 일이 없다. 위 성질을 이용해 적절한 가지치기를 해 주자. 레이지 느낌으로, 구간 내 업데이트를 기록해주는 세그먼트 트리를 구성하자. 2번 쿼리가..

Link https://www.acmicpc.net/problem/4002 APIO 2010 1번 Tag 트리 오일러 투어 테크닉 세그먼트 트리 Time Complexity $O(NlgN)$ 트리 형태로 닌자 조직이 주어진다. 각각의 닌자는 받아야 하는 월급, 리더십 레벨 속성을 가지고 있다. 우리는 '매니저' 닌자를 선택해, 매니저를 루트로 하는 서브트리에서 닌자들을 선택할 수 있다. 선택된 닌자들의 월급의 합은 $M$ 이하가 되어야 한다. 이때 (매니저의 리더십 레벨) * (선택된 닌자들의 수) 를 최대화 해야 한다. 임의의 매니저를 정했으면, 그리디하게 월급이 적은 닌자들부터 선택하는게 최적이다. 나이브하게 모든 닌자들을 매니저로 시도해보면서, 서브트리의 닌자들 중 월급이 작은 순서대로 정렬 후 $..