Good Bye 2022 짧은 후기

A

단순 구현 문제. 물어보는게 복잡해서 약간의 전처리를 했다. 모든 자연수의 진약수의 합을 전처리하면 짧게 할 수 있었다.

B

물어보는 게 모든 가방의 평균 중 몇 번째의 어쩌구 같은 아주 복잡한 무언가였다.
특히 가방의 개수가 많으면 사실상 관리가 불가능한 수치이다. 그런데 가방의 개수가 많으면 첫 번째 / 두 번째로 큰 가방만 남겨두고 나머지는 그냥 다 합쳐주면 된다.
그러니까 최적해에서 가방이 많지 않을 거라고 짐작할 수 있고 그 원리에 입각해서 생각하면 된다. 그런 식이었다. 더 정확하게는 기억이 나지 않는다 (...)
$(K+1)/2$ 를 올림하고 내림하는 걸 헷갈려서 한번 틀렸다.

C

애드혹 문제도 기출 패턴이 있고 웰노운이 있다. 이 문제 와 비슷하게 해결할 수 있다.

D

재밌게 풀었다.
시작은 $X$ 가 $a_{i, j}$ 의 최댓값 이상이라는 걸 관찰 (...) 하는 것일 것 같다.
답에 대한 이분 탐색을 하면 인접한 원소의 차가 큰 "나쁜" 원소들이 있다.
나쁜 원소 중 큰 것과 작은 것이 있을 텐데, 이 중 작은 걸 $X$ 로 바꿔주는 게 무조건 이득이다.
이 과정을 반복하면서 나쁜 원소들이 계속 생긴다. 이러한 것들을 큐에 관리하면서 돌려주면 된다.

E

아주 더럽게 생겼고, G가 그냥 짜면 되는 문제라, G를 먼저 보고 내려왔다. 다행이도 그렇게 더럽지는 않았다.
아이디어는, $k$ 명에게 $T$ 점 이상을 배정할 수 있는 scheme의 존재성을 찾을 수 있다면 전체 문제가 풀린다는 것이다.
최대화는, 위 scheme이 존재하는 최대 $T$를 찾아주면 된다.
최소화는, $n - k + 1$ 명으로 바꾸고, $(-a, -b, -c)$ 에 대해서 $-T$ 점 이상 배정할 수 있는지를 물어보는 것과 동일하다.
"$k$ 명한테 $T$ 점 이상을 배정하면 다른 $n-k$ 명에게 $T$ 점 이상이 배정되더라도 상관없다" 라는 원리 때문에 위와 같은 것이 성립한다.

이제 저 scheme을 찾아야 한다. 이렇게 하면 된다.

• 기본적으로 무승부라고 가정하자. $T := T - (n - 1) b$ 로 두면 된다. 이제 게임은 해도 되고 안 해도 된다. 그리고 $a \geq c$ 라고 가정하자. (승패 자체가 중요하지 않다. 그냥 누구한테 $a$ 를 주고 누구한테 $c$ 를 주는 게임이다.)
• 이미 $T \leq 0$ 이면 게임 없이 끝낸다. $a \leq 0$ 이어도 의미 없다.
• 편의상 $k$ 명을 승자, $n-k$ 명을 패자라 부르자.
• 패자와 패자간 게임은 안 봐도 된다. 승자와 패자간 게임은 승자가 $a$ 를 먹으면 된다.
• 승자와 승자간 게임은 두 가지 경우가 있다. 기본 원칙은, 모든 사람의 결과가 공평할수록 성공 확률이 높다는 것이다. (합은 고정되어 있고 모든 사람이 다 $T$ 점 이상을 받아야 하니까)
  • 승자가 홀수명일 경우 모든 사람이 반은 이기고 반은 지게 할 수 있다. construction은 오일러 투어를 생각하면 좋다.
  • 승자가 짝수명일 경우 누군가는 한번 더 져야 한다. 그리고 딱 한번만 더 지게 construction할 수 있다.
  • 승자가 짝수명인데 져서 이득이 아닌 경우도 있다. $c \le 0$ 이면 그럴 것이다. 사실 $k/2-1$ 번 지고 $k/2-1$ 번 이기게만 할 수도 있다. $(2i-1, 2i)$ 번 사람이 부전승을 하게 짝짓고, 나머지 관계들은 모두 반은 이기고 반은 지게 하면 된다.

이를 구현하면 된다.

F

재밌게 풀었다. 일단 문제 풀이가 knapsack일 것이라고 생각했는데, 도달 시간이 실수로 나오기 때문에 $dp[state] = $ (무언가를 하면서 도착 시간 최소화) 라는 식으로 정의를 시도해봤다. 그런데 생각보다 상태가 복잡해지고 식도 복잡해졌다. 일단 무언가 정리가 필요해 보여서, 내가 모든 물건을 먹었을 때 드는 시간을 식으로 정리해 보았다. $\frac{1}{속도}$ 의 합 꼴로 나왔는데, 약간 고등학교 시절 생각이 나면서 "그럼 질량 나누기 운동량인가?" 라는 식으로 생각 정리가 되었다. 그런 식으로 정리하니까 도달 조건이 아주 단순하게 나왔고, 상태를 $\sum c$ 로 두는 단순한 Knapsack을 유도했다.

G

아는 문제라서 아는 대로 구현했다. 여담으로 내 determinant 라이브러리가 $O(NM)$ 이라 내 풀이도 $O(NM)$ 이다.

H

재밌게 풀었다. Monge array의 대표적인 특성은 row maxima를 빠른 시간에 계산할 수 있다는 것이다. 그래서 "row maxima" 를 계산하고 여기에 나머지 디테일을 끼워맞추려고 했다. row maxima를 계산하면 "어떠한 점" 들을 답의 후보에서 제거해 줄 수 있는데, 대충 계산했을 때 그렇게 깔끔하게 떨어지지 않아서 어려웠다. 분할 정복을 하듯이 Monge array를 $n$ 개의 직사각형으로 분할해야겠다는 생각이 불현듯 떠올랐는데, 직사각형으로 분할하니까 필요한 점이 각 문제당 $O(n)$ 개밖에 생기지 않았고, 쉽게 해결할 수 있었다.

row / column maxima는 CHT를 짜면 되는데 int128이 필요한 게 머리아파서 SMAWK를 복붙했다. 그 과정에서 사용법 실수가 있어 한번 틀렸다. 복붙한 김에 나중에 한번 배워봐야겠다.