10월 2주차 PS 기록 ★ (BOJ 19847, 17260, 25323, 18251, 25201)

좋다.

 

여우 신탁

오랫동안 고민한 뒤에야 맞췄다. 다양한 관찰과 접근을 시도했지만 전부 애매했다.

sparse table을 이용하고 싶다는 생각도 했는데, 매번 함수가 다르기 때문에 무용지물이었다.

거꾸로 마지막 나머지들로부터 추적을 해볼까 하는 생각도 했는데, 크게 달라지는 점은 없었다.

기댓값의 선형성을 적극적으로 이용할 수 있는가도 고민해봤는데, 티어 상 그럴 것 같지도 않았고 써먹기 좋은 상황이 없었다.

 

사실 초반에 제수가 감소한다는 관찰을 했었는데, 이를 다시 생각해보니 쓸 만했다. 뭔가 로그 시간으로의 단축을 원했던지라 효과가 없다고 넘겼었는데, 분할 상환적으로 봤을 때 효과적이었다.

결국 풀이는 제수가 감소하는 만큼만 새 나머지로 이동시켜주면 되는 것이었다. 그러면 시간 복잡도가 분할 상환적으로 $O(n+x_1)$이 된다.

 

계곡이 넘쳐흘러

트리 DP임은 쉽게 눈치챌 수 있다. 다만 까다로운 점은 2로 계속 나눠간다는 점이다. 만약 실수 자료형을 사용한다면 실수 오차를 해결하지 못할 것이고, 분수 구조체로 관리한다면 분모 분자에서 산술 오버플로우가 발생할 것이다.

따라서 새로운 관찰이 필요한데, 바로 정수$+\alpha$($0<\alpha<1$)꼴이라는 '사실'만 알면 된다는 것이다. 왜냐하면 주어지는 높이들은 정수 자료형이기 때문이다. 따라서 (int,bool)로 관리하면 쉽게 맞힐 수 있다.

 

수 정렬하기, 근데 이제 제곱수를 곁들인

곱이 제곱수된 것끼리 바꿀 수 있다는 사실을 바탕으로 여러 수를 거쳐서 결국 바꿀 수 있는 쌍들은 어떤 성질을 갖나 생각을 해 보았더니 각 소인수의 지수의 합의 기우성이 같아야 된다라는 결론에 도달했다.
그리고서 원 배열을 정렬한 배열에 대해 같은 위치에 있는 수랑 그 조건을 만족하는지 대조해보면 되겠다는 생각을 했다. 그러기 위해서 map 등을 사용하면 되겠다 생각했는데 문제는 $10^{18}$ 크기의 수를 어떻게 소인수 분해하느냐였다.
내가 알고 있는 소인수 분해 알고리즘은 시간 안에 안 돌아갈 것이고, 골드인데 어려운 소인수 분해 알고리즘이 나올 것 같지 않다고 생각해서 난관에 막혔다.

그래서 '결국 원 배열과 정렬한 배열에 대해 각 위치에서 조건을 만족하는지 확인하는 건데, 거기에 꼭 소인수 분해가 필요하냐'는 힌트를 받았다. 아... 최대 공약수로 두 수를 나눈 뒤에 각각 제곱수인지 확인하면 되는 거였다.

결국 스스로 한 질문 속에 답이 있었던 것이다. 소인수 분해가 안 쓰일 것 같다고 생각했을 때, '다른 방법은 뭐가 있을까?' 하고 더 생각해 보았으면 좋았을텐데 아쉽다. 아무튼 구현은 5분만에 잘 했다.

 

내 생각에 A번인 단순 dfs 문제가 이 대회에서 E번이 되어버린 건에 관하여 (Easy)

높이 조절이 안 된다면 간단하게 풀 수 있다.

너비 조절이 안 되도 간단하게 풀 수 있다.

이 둘의 요소가 합쳐지니 어려워진다.

 

간단하게 어떻게 풀더라? → Maximum subarray

이진 트리로 준 이유가 있겠지? → 높이가 $\log_2 N$!

 

그럼 모든 높이 구간에 대해 Maximum subarray 진행! → $O(n\log n)$에 해결된다.

 

이 글의 첫 번째 문제랑 세 번째 문제보다도 이 문제를 쉽게 풀었다.

입력을 중위순회로 고쳐 받는 과정만 꼼꼼히 생각해서 구현했더니 실수없이 빠르게 맞출 수 있었다.

 

보드 뒤집기 게임

대충 30분 언저리에 아이디어를 찾은 것 같다. 어렵다.

 

일단 격자의 색칠을 논할 때면 제일 먼저 떠오르는 것이 불변량이다.

그럼 색이 변해야 되는 칸들은 홀수번 바뀌고, 안 변해야 하는 칸들은 짝수번 바뀌어야 된다는 것을 알 수 있다.

좀 더 나아가서, 입력의 부분을 크게 신경쓸 필요가 없다는 것도 알 수 있다. 그냥 $N+M$번 xor시키는 것으로 대체하면 되기 때문이다.

 

그 다음에 관찰할 것은 격자의 크기가 매우 커서 기우성이 안 맞는 칸들에 대해 매번 시행을 해줄 수 없다는 것이다.

이를 바탕으로, 전체적인 정보를 바탕으로 어떤 특성을 찾아야 문제가 풀릴 것 같다는 생각을 할 수 있다.

 

이 점에 유의하며 관찰하다 보면, 각 행과 각 열마다 등장하는 색칠된 격자의 개수가 짝수라는 조건만 만족하면 될 것 같다는 관찰을 할 수 있다. 증명할 방법은 모르겠지만 일단 발견하고 나면 강한 확신이 든다.

그렇게 코딩해서 제출하면 맞는다.