오늘의 PS (29) - 240423~24

23일에는 지난 글에 IBory님이 남겨 주신 숙제 2개를 풀었고 24일에는 북마크에서 1개, 밀린 숙제에서 1개를 골라 풀었다.

 

30789 초콜릿 케이크

 

월향 본 대회에서 레이지 세그 쓴 이상한 풀이로 비비다가 패배했던 기억이 있는 문제이다. 저런 식으로 푸는 게 아니라는 정보 정도만 가지고 다시 풀어보기로 했다.

 

생각의 흐름

 

어떤 문제든 간에 엄청난 직관의 소유자가 아닌 이상 식을 좀 써 봐야 실마리가 잡히는 것 같다.

 

\(D_i\) = \(i\)번 조각을 시작으로 피자를 잘랐을 때 두 부분의 맛의 차이(절댓값)으로 정의하자.

 

이를 가지고 뭔가 해보려 했으나 잘 되지 않았고, 절댓값을 뗀 후 각 조각에 초콜릿을 놓았을 때 \(D\)값의 변화량을 관찰하였다. 그러면 아래와 같은 두 가지의 연산을 쓸 수 있다는 사실을 알 수 있다.

 

1. \(1 \le i \le N\)에 대해 \(D_1, \cdots, D_i += M, D_{i+1}, \cdots, D_n -= M\)

2. \(1 \le i \le N\)에 대해 \(D_1, \cdots, D_i -= M, D_{i+1}, \cdots, D_n += M\)

 

두 연산을 잘 조합하면 하나의 \(D\)값을 \(2M\)만큼 변화시킬 수 있다. 따라서 모든 \(D\)값을 \([-M, M]\) 구간 사이에 들어오도록 하는 풀이를 짰는데, 틀렸다.

 

반례를 열심히 만들어 본 결과 \(M = 1\)인 답에서 0이 나오지 않는다는 놀라운 사실을 발견하였다. 이유를 고민하다, 뭔가 모든 \(D\)를 \(M\)만큼 이동시키는 경우를 고려하면 잘 처리될 것 같아 바꿨더니 맞았다. Proof by AC 느낌이 좀 있긴 한데 재미있는 애드혹 문제라고 생각한다.

 

31622 Highway Tolls

 

백준에서 한/영이 아닌 다른 문제는 잘 풀지 않는 편인데 숙제로 받아서 풀게 되었다. GPT가 번역을 잘 한다는 사실을 알게 되었다.

 

생각의 흐름

 

이상한 다익스트라 사풀으로 시간을 좀 낭비했다. 정신 차리고 식을 공책에 다시 써 본 결과 실마리를 잡을 수 있었다.

 

일단 식을 보면, 절댓값 함수의 합 꼴이다. 정확히는 누적합과의 차이를 더한 꼴이라, \(x\)개의 간선을 사용했다면 가운데 간선을 시간 \(0\)에 사용하는 것이 최적임을 알 수 있다.

 

이를 염두한 후 식을 다시 써보면 각 간선의 \(l\)값에 붙는 계수가 \(1, 2, 3, ... 3, 2, 1, 0\) 꼴이라는 사실을 알 수 있다.

 

여기까지 관찰한 후 한 단계를 더 못가서 시간을 상당히 허비했다. 일단 제한을 보니 \(O(NM)\) DP인데, 저 식을 어떻게 잘 계산할 지 고민이 좀 길었던 것 같다.

 

결론적으로, 경로를 반으로 쪼개면 \(1, 2, 3, ... \)과 \(0, 1, 2, 3, ...\)이라는 DP를 하기 아주 좋은 형태가 나온다. 그 뒤는 그냥 Simple DP를 돌린 후 답을 계산하면 된다.

 

 

11691 LCM(i,j)

 

수학 문제는 내 담당이 아니지만 정수론 수업을 듣던 중 북마크에 있던 이 문제가 떠올라서 풀기로 했다.

 

생각의 흐름

 

식 정리를 열심히 하면 mobius 함수를 잘 계산한 후 Harmonic Lemma로 풀 수 있는 형태가 된다.

수식을 쓰기 귀찮을 뿐더러 인터넷에 좋은 풀이가 많기 때문에 생략하겠다.

 

 

21792 Meetings 2

 

2주 전에 잠깐 잡았다가 틀린 채로 방치되었던 것이 생각나서 풀기로 했다.

 

생각의 흐름

 

2주 전에 생각한 사풀: 일단 자명하게 홀수면 1이다. 그리고 2일 때는 지름이 답이다. 이에 착안해 지름 위에 항상 답이 있을 것이라고 추측한 후 풀었더니 틀렸다. 생각해 보니 반례가 어렵지 않게 보여서 일단 여기서 멈춰두었다.

 

결국 해야 하는 것은, 양 끝에 정점이 \(i\)개 이상 달린 정점 쌍 중 가장 먼 것의 거리를 구하면 된다.

 

트리의 모든 경로에 대해 무언가 구한다 -> 대부분 스투라 아니면 센트로이드다.

 

스투라로 열심히 비벼봤는데 잘 모르겠어서 센트로이드 쪽으로 넘어갔다.

너무 오랜만에 봐서 센트랑 스투라의 차이가 뭔지 모르는 사고가 있었지만, 다행히 센트 쪽으로 생각하니 갈피가 좀 잘 잡혔다.

 

(같은 거리 중 제일 큰 subtree)나 (같은 크기 중 제일 먼 subtree)를 저장하면 될 것 같았다.

 

전자로 조금 해보다 잘 안 되어서 후자로 갈아타니 다행히 잘 되는 것 같았다.

 

다만 구현에 테크니컬한 부분이 좀 필요해서 + 센트 너무 오랜만에 짜서 좀 많이 걸리고 맞았다.

 

방에서 그냥 편하게 풀다보니 뭔가 근육만 써서 풀게 되는 것 같다. 제출도 대충 해서 항상 좀 많이 틀리고 맞는다. 열심히 하자.

룸메이트라는 사람이 옆에서 루비5 3시간만에 풀기를 하고 있는데 나는 코딩만 열심히 하면 되는게 아닐까?

 

문제 추천 받습니다. 감사합니다.