[뇌풀이 일지] 20250801

앞으로 뇌풀이 일지를 작성해보기로 하였다. 분명히 문제를 구현해야 푼것이긴 하지만, 일단 풀이를 내지 못하면 당연히 구현할 수도 없기 때문에 결국 중요한 것은 풀이를 내는 능력이 아닌가 싶어 이러한 일지를 작성하게 되었다. 오늘의 일지는 그냥 다이아 이상의 문제를 많이풀린 순으로 정렬한 뒤, 필자가 풀지 않은 문제들을 차례대로 작성하였다. 해당 뇌풀이들을 구현할 가능성은 꽤나 요원하긴 하지만, 그래도 언젠간 짜게 되지 않을까?

 

1. https://www.acmicpc.net/problem/18621

중앙을 관통하는 세로선을 전부 알아내자. 이 세로선중에서, 제일 큰 원소를 잡고, 그 주변에 있는 원소도 전부 알아내자.

 

이제 이 원소의 주변원소중 제일 큰 원소가 있는 방향이, 최대원소가 존재하는 방향이다. 임의의 원소에 대해서 자신보다 큰 원소를 따라가면 언젠간 최대원소를 만나야 하기 때문이다.

 

쿼리 횟수는 처음에 세로선을 긋는데에 n, 가로선을 긋는데에 n/2, 다시 세로선을 긋는데에 n/2, 가로선 n/4,..하여 3n+a정도가 소모된다.

 

2. https://www.acmicpc.net/problem/19556

N/3에서 시작해서 오른쪽, 왼쪽, 오른쪽, 왼쪽을 반복하면 된다.

 

3. https://www.acmicpc.net/problem/10319

주어진 그래프를 s개의 층으로 복사한다. 이제 복사된 정점 ns개의 그래프에서, 유량을 g만큼 흘리는 문제가 되어 전체 시복 O(nsg)에 해결된다.

 

4. https://www.acmicpc.net/problem/13545

누적합 배열을 생각하자. 이제, 문제는 주어진 구간에서 가장 멀리 떨어진 동일한 값의 거리를 찾는 문제로 환원된다.

이러한 문제는 모스를 돌려서 풀 수 있다. 총 n개의 값들에 대해서, 가장 오른쪽 위치-가장 왼쪽 위치를 관리해야 하므로, 아마 셋질이 유효하지 않을까 싶다. nlognsqrt(n)이긴 하지만, 10만, 2.5초에 힐베르트 모스등을 박으면 아마 괜찮게 돌 것으로 생각된다.

 

5. https://www.acmicpc.net/problem/8464

이분탐색을 돌린다. 어떤 수 k에 대해서, k 이하의, d^2으로 나누어떨어지지 않는 수의 개수를 구하면 된다.

 

전체 수에서, 2^2으로 나누어지는 수의 개수를 빼고, 3^2으로 나누어지는 수의 개수를 빼고, 4^2으로 나누어지는 수는 무시하고, 비슷하게 간다.

 

구체적으로 d에 대해서 mu(d)X(n/d^2)만큼을 전체 카운트에서 빼주면 될텐데, d가 sqrt(n)보다 커지면 어차피 전부 0이 됨을 알 수 있어서 O(sqrt(n)logn)에 풀 수 있다.

 

6. https://www.acmicpc.net/problem/2927

6-1. 링컷을 박는다.

6-2. 앞으로 주어질 bridge들을 미리 전부 받고, 그걸로 트리를 만든다. 이 과정은 유파를 통해 실제로 트리를 구성하는 다리를 알아낼 수 있다.

이제 이렇게 얻은 트리에서 두 정점 사이의 모든 간선이 활성화되었는지의 여부를 체크하고, 그렇다면 그 경로상의 모든 수의 합을 구하는 문제로 환원된다.

 

전자와 후자 둘 다 특정 path의 원소 합을 구하는 문제이므로, 그냥 오일러 투어 테크닉을 적용해서 해주면 된다.

 

7. https://www.acmicpc.net/problem/13324

슬로프 트릭의 유명한 연습문제인 것으로 알고 있다. 

dp(i,x)를, 수열의 i번째 값까지 고려하였고, 특히 B_i<=x라는 제약을 만족하는 경우의 최솟값이라고 하자. 이때, dp값은 x에 대한 일차함수들의 결합으로 관리한다. 당연하지만, 특정 시점부터는 기울기가 0이 될 것이고, 그 이전까지는 기울기가 음수일 것이다. 이제 i를 1 늘리는 행위는, V자 함수와 이전의 dp배열을 합치는 연산으로 생각할 수 있다. 이때, 합친다는 것은 말 그대로 그냥 동일 인덱스의 두 값을 더하는 것이다. 뒤에 만약 양수의 기울기가 있다면, 이를 0으로 바꿔준다. 역추적을 위해 합치면서 롤백할 연산들을 전부 보관해준다. 

 

이제 역추적은, x=inf로 초기화한 다음 맨 뒤쪽 dp배열마다 x 이하중 최초로 등장하는 최솟값을 선택해주면 될 것이다.

 

8. https://www.acmicpc.net/problem/13550

누적합 배열을 생각하면 된다. 4.과 같다.

 

9. https://www.acmicpc.net/problem/17429

lazy 값을 ax+b와 같은 일차함수 꼴로 관리하는 것이 유효하다. 서브트리 쿼리와 경로 쿼리는 적어도 내 생각엔 각각을 다른 세그로 관리할 필요가 있어보였는데, 서브트리는 그냥 in, out을 전부 +의 가중치를 주고, 경로 쿼리는 in에 +, out에 -를 붙여야 하는걸로 생각되는데 한꺼번에 관리 가능한지는 잘 모르겠다.

 

10. https://www.acmicpc.net/problem/2626

이런걸 휴리스틱하게 뭔가 한다고 듣긴 했는데, 필자는 어떻게 하는지 잘 모른다. 여기에서는 n^2logn인 다른 풀이를 설명한다.

 

거리에 대한 이분탐색을 진행한다. 고정된 거리에 대해, optimal한 원은 어떤 점 하나를 지난다고 가정할 수 있다. 따라서, 가능한 모든 점에 대해 해당 점을 중심으로 원을 돌리면서, 어떤 점이 어떤 각도에서 원에 들어오고 빠져나가는지 체크하여, 모든 점이 원에 들어오는 경우가 있는지 체크하면 된다.

 

11. https://www.acmicpc.net/problem/13557

만약 두 구간이 겹치지 않는다면, 그냥 각 구간에서 누적합의 최소, 최대를 골라서 빼준 값이 답이다.

 

두 구간이 겹친다면, 제약에 따라 반드시 부분적 포함관계라고 가정할 수 있다. 즉, 전체 구간이

[l][l,r][r]과 같이 분할될 수 있다는 것이다. 이제, 답을 구하기 위해선 i가 [l]에 속한 경우와 j가 [l,r]U[r]에 속한 경우, i가 [l]U[l,r]에 속한 경우와 j가 [r]에 속한 경우, 그리고 i,j가 둘다 [l,r]에 속한 경우로 분할할 수 있다.

 

첫 2개는 그냥 누적합에 대한 최소/최대 쿼리이고, 둘다 [l,r]에 속한 케이스는 구조체세그를 통해 해결될 수 있음이 잘 알려져 있다.

 

12. https://www.acmicpc.net/problem/13538

로그제곱은 하면 되고, 추가연산이 로그를 키울때까지 시간이 꽤 걸리니까 어떻게 가능하지 않을까?싶긴 하다. 로그로 푸는법은 잘 모르겠다. 

 

조금 더 생각해봤는데, PST와 섹분탐색을 쓰면 1,3,4,5번 쿼리는 처리가 되는것으로 생각된다. 2번 쿼리도 따지고보면 PST를 트라이 취급하여 쿼리를 날릴 수 있으니까 풀리는듯하다.

 

13. https://www.acmicpc.net/problem/14898

각 수들에 대해서, 자신과 같은 값을 가졌으면서 자신의 왼쪽에서 가장 마지막으로 등장한 원소의 위치를 생각하자.

 

이러한 것을 prv[i]이라고 표기하고 2차원의 점 (i,prv[i])를 생각하면, 주어진 쿼리는 결국 [l,r]X[1,l-1] 내부에 있는 점의 개수를 세는 문제로 환원할 수 있다. 이는 PST로 풀린다.

 

14. https://www.acmicpc.net/problem/10070

Candies?라는 문제가 이 문제랑 비슷했던 것 같은데, 잘 기억나진 않는다.

 

열 기준으로 스위핑을 하면서 각 쿼리를 포함시키고, 제거하는 방식으로 관리하자. 중요한 관찰은, 값을 위로 제한하거나 아래로 제한하는 과정은 클램프 함수의 꼴로 나타난다는 것이다. 클램프 함수는 합성해도 클램프이기 때문에, 세그로 관리해줄 수 있다.

 

15. https://www.acmicpc.net/problem/17975

금광과 동일한 formulation인것으로 확인된다.

 

16. https://www.acmicpc.net/problem/18439

비트셋 LCS 기본문제인 것으로 알고 있다.

 

17. https://www.acmicpc.net/problem/18438

히르쉬버그 기본문제인 것으로 알고 있다.

 

18. https://www.acmicpc.net/problem/13514

센트로이드 트리를 쓰면 로그제곱에 가능한 것으로 생각된다. 활성화된 정점에 대해서, 해당 정점의 모든 부모 노드들에 대해서 자신과 부모노드까지의 거리를 가능성으로 관리해주면 된다.