7월의 첫 번째 PS일지 (7/15~7/27)

7월의 첫 번째 PS일지 (7/15~7/27)

728x90

방학이 되어서 PS를 더 많이 할 수 있게 되었고, 방학 시작(7월 15일)부터 지금까지 푼 문제를 정리하는 글이다.

요약

1. AC레이팅 변화 2277->2350 (D5->D4)

2. 푼 문제

17168/18845/18847/17274/13925/12858/17690/16783/3382/16217/6171/12928

일부만 풀었거나(서브테스크), 풀다가 틀린 문제는 적지 않았다. 또한 풀이가 같은 서로 다른 문제는 그 중 하나만 적었다.

1. Water Knows The Answer

링크: https://www.acmicpc.net/problem/17168

그리디하게 접근할 수 있다. 일단, 높이가 너비보다 같거나 크게 되도록 잘 값을 변환해 주고, 두 개를 골라서 양 쪽의 벽으로 세우고, 나머지는 바닥에 깔자. 그러면 여기서 채울 수 있는 물의 양은 바닥의 길이와 양쪽 높이의 최솟값의 곱에 바닥으로 쓴 만큼의 블록의 넓이의 합을 뺀 것이다. 이를 CHT로 쉽게 최적화해 줄 수 있다.

2. Constellation 3

https://flappybird.tistory.com/39

여기에 문제 설명과 풀이를 모두 작성하였다.

3. Stray Cat

꽤 어려운 문제로, 문제 설명과 풀이를 나중에 블로그에 작성할 예정이다.

4. 카드 공장(Small/Large)

http://boj.kr/17274

Small은 브론즈 난이도로 그냥 일일히 구하면 되고, Large는 하나의 관찰이 필요하다. 카드에 써진 두 숫자가 $a$와 $b$라 하고 $a

5. 수열과 쿼리 13

http://boj.kr/13925

그냥 Lazy Propagation을 지원하는 세그트리를 구현하면 된다. Lazy Propagation을 구현해본지 꽤 오래되었어서 오랜만에 구현해 보았다.

6. Range GCD

http://boj.kr/12858

유클리드 호제법에 의해, $gcd(a_1, a_2, ..., a_k)=gcd(a_1, a_2-a_1, ..., a_k-a_{k-1})$이 된다. 이를 구현해 주면 된다. 구현은 쉬운데 수학적인 아이디어가 어려운듯 하다.

7. Library

http://boj.kr/17690

쿼리 하나를 통해 추론할 수 있는 것은 쿼리로 날린 책중에서 연속한 쌍이 몇개 있는지다. 일단 $N$제한을 보면 $NlgN$정도의 해법을 찾아야 하는데, 그러면 양쪽 끝에 있는 것을 하나씩 $lgN$정도의 쿼리로 알아낼 생각을 해야 한다. 이게 약간 어려운데, 전체 배열을 적절히 반으로 나눠서 각각 쿼리를 날려준다. 그러면 첫 묶음의 책들 중 연속한 것, 두 묶음의 책들 중 연속한 것들의 갯수를 알 수 있으니 연속한 첫 번째 묶음의 책과 두 번째 묶음의 책의 쌍의 수를 알 수가 있는데, 이를 통해 전체 배열에서 양 끝의 책이 두 묶음에 각각 한 권씩 있는지, 아니면 한 묶음에 두 책이 다 있는지를 판단할 수 있다. 일단 각각 한권 있다 하고, 첫 번째 묶음을 반으로 나눠서 두 번째 묶음에 넣고 다시 쿼리를 날려서 반으로 나눠진 첫 묶음 중 어디에 끝에 위치한 책이 있는지 판단한다. 이처럼 이진탐색을 계속 한다면 $lgN$만에 끝에 있는 책 하나를 찾을 수 있다. 그러면 그 책을 제외한 나머지의 책에서 이 작업을 반복하면 된다. 만약, 맨 처음에 두 묶음으로 나눴을때 한 묶음에 두 책이 있다 판정되었다면, 랜덤을 돌려서 끝에 위치한 책이 각각 다른 묶음으로 갈 때까지 계속 반복해주면 된다.

8. Bulldozer

정올에 기하가 나올 것을 대비하려고 어려운 기하 문제를 하나 풀었는데, 나오지 않았다.

꽤 어려운 문제이므로 추후에 블로그에 따로 포스팅하겠다.

9. Gems

http://boj.kr/3382

트리의 각 노드에 배정된 자연수는, 아무리 커봐야 $lgN$ 정도이다. 이는 수학적으로 증명할 수 있다. 이를 트리DP하면 바로 끝난다.

10. 옥토끼나라

http://boj.kr/16217

라이언이 곰이 아니라 사자라는 것을 알게 해준 문제이다. DFS 트리를 만들어서 단절점을 구하는 방식과 비슷하게 진행한다. 한 정점에 대해서 답을 구할 때, 그 정점보다 위로 뻗어나가는 백에지가 있는 자식(을 루트로 하는 서브트리)은 모두 한번에 모아서, 그렇지 않은 것은 따로 처리하면 된다. 이게 왜 산만한 고양이보다 어려운 문제인지 모르겠다.

11. 땅따먹기

http://boj.kr/6171

일단 다른 사각형에 완전히 포함되는, 즉 H와 W가 모두 다른 사각형보다 작은 것은 그냥 같이 처리할 수 있으므로 일단 없에 준다. 그런 다음, W나 H를 기준으로 정렬하면 DP식을 세울 수 있고, CHT를 쓰면 풀린다.

12. 트리와 경로의 길이

http://boj.kr/12928

각 정점의 차수를 $d_i$라 하면 $S=\sum_{i=1}^{N}{_{d_i}\mathrm{C}_{2}}$인 트리가 가능한지 구하면 된다. 이는 아주 여러 방법이 있는데, $d_i$들의 합과 제곱의 합이 주어졌을 때 가능한지 판정하는 문제로 바꿔 dp로 하는게 가장 간단하다.

728x90

from http://flappybird.tistory.com/40 by ccl(A) rewrite - 2021-07-28 03:00:35