신나는 추석 기념 oi 돌기 1편 (NOI singapore 2023)

추석이고 나가도 할 건 없고.. 그럼 뭐를 해야할까? ps와 아니메 시청 말곤 없을듯..

전희절창 심포기어가 좀 재밌어 보이던데 볼 예정이다. 매일 oi셋 돌고 업솔빙하기 라는 장대한 계획을 세웠는데.. 5시간 풀집중은 너무 힘들다. 이걸 다들 어떻게 하는걸까? 내가 늙어서 그런듯...

 

다이 바나나가 아니라 다이 급식 이었다..

 

셋을 거하게 말아먹었다! B에서 말린게 좀 큰 것 같음... 현재 a, b, c는 풀이를 알고 a, b는 구현까지 했고 c는 구현을 해야하고 d, e는 읽어보지 않은 상태이다. 업솔빙 다 하고 자려햇는데 1시부터 모니터만 보고 있다보니 정신이 나갈 것 같아.. 나머진 내일 일어나서 하는걸로... 회복도 공부의 한 파트 아닐까? 암튼 내일은 반드시 정리해서 올리는걸로... 내일은 유사코를 돌 예정인데 그래도 이런 무서운 셋보단 정신적으로 괜찮지 않을까 싶다.

 

https://www.acmicpc.net/problem/28495

28495번: Topical

처음에 문제를 잘못 읽어서 접근을 못하다 읽어보니 할만해서 구현했다. nypc 2023 2-b 3번 문제랑 유사한 것 같은데, 사실 이 유형 자체가 좀 웰노운 같다.

 

요악하자면 $K$개의 공부능력?이 있고 N개의 강좌가 있다. 어떠한 강좌를 들으려면 K개의 공부 레벨 "모두" 요구치 이상이어야 하고, 강좌를 듣고 난 후엔 각 공부 능력이 어떠한 값 만큼 는다. 이때 들을 수 있는 최대의 강좌 개수를 구하는 문제이다.

 

각 과목별 요구치를 정렬해주자. 수강 가능한 강좌를 큐에 넣어주자. 그리고 강좌를 수강할 때 마다 공부능력이 증가할텐데, 정렬이 되어있기에 배열을 차례차례 훑으면서 어떠한 강좌에 어떠한 공부능력 요구치가 충족되었다를 관리해줄 수 있다. 모든 요구치가 충족된 강좌는 큐에 담으면 된다. 위상정렬 비슷한 느낌이다. 모든 연산은 amortized하게 처리되고, 시복은 정렬에 의해 $O(NM \log NM)$ 이 된다.

 

https://www.acmicpc.net/problem/28496

28496번: Inspections

구현을 제외한 모든 것이 재밌는 문제이다. 구현도 이쁘게 할 수 있는 것 같은데, 난 아직 잘 모르겠다. 구현을 잘 하는 연습을 할 필요가 있어보인다. 정해에 가까운 풀이는 빠르게 떠올랐지만, 자구에 약한지 구현법을 잘 떠올리지 못하였다. 

 

문제를 요약하자면, $N$개의 기계가 있고, 수행할 명령이 $M$개 있다. 각 명령은 닫힌 구간 $[L, R]$ 으로 표현되는데, 기계 $L$부터 $R$까지 순차적으로 실행시킨다는 뜻이다. 예를 들어 명령 $[1, 5]$, $[3, 6]$이 있으면 명령이 수행되는 기계는 차례대로 1, 2, 3, 4, 5, 3, 4, 5, 6 이 된다. 단위시간당 하나의 기계만 작동된다. 이때 어떠한 정수 $S$가 쿼리로 들어오는데, 어떠한 기계가 다시 작동될 때 전에 작동된 시간과 차이가 $S$ 초과로 나는 그러한 작동?의 횟수를 구해야 한다. 위의 경우에선 $S = 2$ 일 때 답은 $3$이 된다. 기계 3, 4, 5가 다시 작동될 동안 3초가 지나기 때문이다. 

 

우선, 오프라인 쿼리가 가능함을 생각해보자. 어떠한 기계가 다시 수행될 때 $S$초가 지났다 하면, $S$ 초과의 쿼리에 대해서는 답이 다 더해져야 하기에, 쿼리를 오름차순 정렬 후, 누적합 등으로 관리해주면 된다.

 

subtask 1, 2)

$N$개의 각 기계마다 가장 최근에 실행된 시각을 저장해주자. 그리고 각 기계마다 다시 실행될 때 그 차이 이상인 쿼리들에 대해 1을 더해주어야 하는데, 이는 위에서 설명한 오프쿼리를 고려하면 이분탐색 등으로 초과인 쿼리를 찾아줄 수 있다. 시간복잡도 $O(NM + Q \log Q)$

 

fulltask)

어떠한 구간에 수행하는 시간은 연산은 연속적이다. 그 후, 그 구간의 임의의 연속된 부분집합에 연산이 다시 수행되면, 연속적인 기계마다 단위시간의 차이는 동일하다. $[3, 6]$ 이라는 연산이 먼저 수행되고, $[4, 5]$ 라는 연산이 수행되었다 생각해보자. 4가 이전에 실행된 시간과의 차이와 5가 이전에 실행된 시간과의 차이는 동일하다. disjoint한 구간들과 그 구간에 해당하는 단위시간들을 관리해주자. 이제 우리가 해야할 것은 새로운 구간과 단위시간이 들어올 때, 그 구간과 교집합이 생기는 구간들에 대해 쿼리 값을 업데이트 해주는 것이다. 나이브하게 하면 업데이트 부분만$O(NM)$이 될 것 같지만... bbst 등으로 딱 그 구간의 교집합들만 봐주고 완전히 포함되는 구간은 삭제시켜주는 방식으로 구현하면, 놀랍게도 amortized하게 전체 문제가 풀린다.

대충 $O((N + M) \log N \log Q + Q \log Q)$이 나오는 것 같다. 이는 disjoint한 구간은 최대 $O(N)$개 존재할 수 있고, 어떠한 구간과 교집합이 생기는 구간이 한번의 연산 이후 사라지기 때문이다. 엄밀하게 증명하기는 어렵지만 직관적으로 받아들이기는 쉽다고 생각한다.

 

C, D, E 는 내일.. 너무 피곤함

 

셋 후기?

문제는 재밌었는데.. 음.. 아무래도 멘탈 관리를 해야할 필요가 있다. B, C 전부 문제에 필요한 관찰은 전부 하였지만, 멘탈 파괴와 뇌절을 거듭하며 못 푼 것이 너무...