gubshig

https://www.acmicpc.net/problem/32766 이런 형태의 문제는 우선 트리를 만들고 생각하고 싶다. 각 직사각형의 외부 중 가장 가까운 직사각형을 그 직사각형의 부모라 하자. 모든 직사각형을 포함하는 직사각형을 추가해주면, 이 직사각형을 루트로 하는 하나의 트리가 생긴다. 그럼 쿼리에서 물어보는 것이 무엇일까? 트리에서 쿼리로 주어진 점을 포함하는 직사각형 중 깊이가 가장 작은 정점을 잡아보자. 그럼 트리에서 경로 쿼리가 된다. 트리의 어떤 정점에서 부모로 가는 간선은 그 정점에 해당되는 직사각형이 가지고 있는 색 중 적어도 하나를 지나야 한다는 관찰도 할 수 있다. 이때 색은 $6$가지기 때문에, 트리의 경로 중 임의의 색 조합만 지나는 경로가 존재하는지에 대한 문제를 $2^6$..

https://www.acmicpc.net/problem/27877 27877번: 제곱수 덱 2 $x$의 최솟값을 $998\,244\,353$로 나눈 나머지를 출력한다. 만약 $N$장의 카드를 하나의 덱으로 합칠 수 없다면 -1을 출력한다. www.acmicpc.net 문제가 상당히 간단하다. 관점을 조금 바꿔보자. 각 카드를 정점으로, 덱을 컴포넌트로 보면, 이 문제는 MST 문제로 환원될 수 있다. 가중치 간선의 곱에 대한 MST인데, 결과에 log를 씌운다 하면, 결국 곱셈이 덧셈으로 바뀌기에, 일반적인 MST 문제와 같다. 크루스칼 알고리즘을 생각해보자. 가중치가 적은 간선부터 선택하며 만약 그 가중치를 선택할 때 사이클이 생긴다면 선택하지 않는 식으로 작동하는 알고리즘이다. 예제어서 주어진 14..

https://www.acmicpc.net/problem/26973 26973번: Circular BarnFor the first test case, Farmer John can remove $1$, $2$, or $3$ cows from the first room. Whichever number he removes, Nhoj can remove the remaining cow(s), forcing FJ to lose when they circle back to the first room. For the second test case, FJ can removwww.acmicpc.net  일단 N = 1인 경우를 생각해보자. 편의상 Farmer John을 FJ라 하고, Farmer Nhoj를 FN이라 부르..

어제 다른 분들이 쓴 USACO 후기를 조금 찾아봤는데, USACO 2020 December Contest 후기글을 찾았습니다. 일단 문제를 풀고 글을 읽고 싶었어서, 틈틈히 풀었습니다. 문제가 상당히 재밌었던 것 같습니다. 실제 풀이에 쓴 시간은1번 10분2번 30분3번 1시간정도 된 것 같습니다. https://www.acmicpc.net/problem/20647 20647번: CowntagionOne possible sequence of events corresponding to this example is the following: the number of sick cows in farm 1 doubles and then doubles again, so that after two days, the..

유사코가 끝난지 꽤 되었는데, 귀찮아서 풀이를 올리지 않다 이제야 올린다. 당시 대회에서 2, 3번을 1시간 30분정도에 걸쳐 풀고, 1번 문제를 계속 봤는데, 결국 섭테를 하나도 못긁었다. 이상한 관찰을 자꾸 하고 증명도 없이 살면서 풀어본적도 없는 기하적 해석을 했는데, 결국 그냥 뻘짓이었다. 다음부터는 문제가 어려워보이면 섭테 긁을 생각부터 해야겠다. https://www.acmicpc.net/problem/27847 27847번: Cow-libi Somebody has been grazing in Farmer John's $(1 \le G \le 10^5)$ private gardens! Using his expert forensic knowledge, FJ has been able to dete..

https://www.acmicpc.net/problem/15587 15587번: Cow at Large (Gold) Cornered at last, Bessie has gone to ground in a remote farm. The farm consists of $N$ barns ($2 \leq N \leq 10^5$) and $N-1$ bidirectional tunnels between barns, so that there is a unique path between every pair of barns. Every barn which has only one tun www.acmicpc.net 요즘 유사코 실~골 div를 돌고 있는데, 여기는 문제 난이도가 적당하고 굉장히 맛있는 것 같다. 다양한 ..

어제는 애니메이트를 다녀오느라 문제를 거의 못풀었다.. 오늘은 4문제를 풀었다. 다 꽤 재밌는 문제였다고 생각한다. https://www.acmicpc.net/problem/10166 10166번: 관중석 KOI 공연장의 관중석에는 가운데에 있는 무대를 중심으로 반지름이 자연수인 동심원(중심이 같은 여러 원들) 위에 다음과 같이 좌석들이 배치되어 있다. 반지름이 1인 원 위에는 좌석이 1개, 반지 www.acmicpc.net 이 문제는 여러가지 풀이법이 존재한다. 유클리드 호제법을 사용한 O(d2 ^2 log d2) 정도의 풀이가 정해인것 같다. 나는 dp로 O(d2 log d2)에 풀었다. 기본적인 관찰: 반지름이 r인 동심원에 대하여, 반지름이 r의 배수인 동심원들과 정확히 r개의 좌석이 겹친다. d..

https://www.acmicpc.net/problem/1750 1750번: 서로소의 개수 예제 1의 경우 가능한 경우의 수는 (2, 3), (4, 3), (2, 4, 3)이다. www.acmicpc.net 배낭 문제로 풀리는걸 깨달으면 쉬운 문제이다. 수열의 원소를 선택해서 어떤 연산을 해서 나오는 경우의 수를 구할때, 배낭 문제를 사용하면 쉽게 풀 수 있다는걸 잊지 말자. 단, 연산의 교환법칙이 성립해야한다. import sys import math mod = 10000003 input = sys.stdin.readline n = int(input()) a = [int(input()) for _ in range(n)] ans = 0 SZ = max(a) + 1 dp = [0] * SZ for i i..

생각보다 문제의 풀이를 작성하는것이 재밌어서 앞으로 자주 할 것 같다. https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 간단한 배낭 dp 문제이다. dp(i, j)를 i번까지 추를 사용해서 무게 j를 만들 수 있는가? 로 정의하자. 구슬의 무게를 확인할 수 있다는 것이 무슨 뜻일까? 구슬을 왼쪽 저울에 고정한다 할 때, 오른쪽에 추를 올리는것은 추의 무게를 더한다고 할 수 있고, 왼쪽에 추를 올리는 것은 추의 무게를 뺀다 할 수 있다. dp(0,..

이 문제는 서브테스크를 긁고 최적화를 할 방법을 모르겠어서 풀이를 봤다. 풀이가 신기하고 좋은 문제라고 생각해서 풀이를 올려본다. https://www.acmicpc.net/problem/25402 25402번: 트리와 쿼리 첫 번째 줄부터 $Q$개의 줄에 걸쳐, 각 질의에 대한 답을 출력한다. 이 중 $i$ ($1 ≤ i ≤ Q$)번째 줄에는 $i$번째 질의에서 주어진 $S$에 대하여, $S$의 연결 강도를 출력한다. www.acmicpc.net 이 문제를 요악하자면 트리를 S라는 집합의 정점들로만 한정지었을때, 생기는 각 컴포넌트들의 연결 되어있는 노드의 개수를 구하면 된다. 연결 개수는 컴포넌트의 노드 개수를 n이라 했을때, nC2가 된다. 나이브하게 매 쿼리마다 dfs를 돌리며 컴포넌트의 개수를 ..