2024 IOI 멘토교육 4주차

byunjaewoo 2024. 7. 11. 15:28

JOISC 2018/2019 중 세 문제로 이루어진 셋을 돌았다.

이 날은 기말고사가 끝난 당일 날로, 학교 일정 때문에 부득이하게 셋을 늦게 시작했고, 중간에 한 문제가 이미 풀었던 문제여서 문제를 수정했다. 신체적, 정신적으로 컨디션도 안 좋았을 뿐더러, 시간도 많지 않아서 셋을 제대로 풀지 못했다.

따라서 시간대별 복기는 올리지 않고, 내가 각 문제별로 어느 서브태스크까지 풀었는지만 정리할 것이다.

1. Bitaro, who Leaps through Time

JOISC답게 서브태스크가 거의 나눠져 있지 않았다.

서브태스크 1은 쉽게 풀 수 있었고, 서브태스크 2는 합성함수 세그먼트 트리를 잘 이용하면 풀 수 있을 것 같았다.

x좌표와 현재까지 사용한 가중치를 $(x, w)$라고 했을 때, $x$의 범위에 따라 다음 상태가 나뉜다.

1. $x \le l_i$인 경우 : $(l_i+1, w)$가 된다.

2. $l_i < x < r_i$인 경우 : $(x+1, w)$가 된다.

3. $r_i \le x$인 경우 : $(r_i, w+x-r_i+1)$이 된다.

이는 $(x, w)$를 새로운 $(x', w')$에 대응시키는 함수와 같고, 이를 여러 번 빠르게 합성하기 위해 금광 세그와 같은 합성함수 세그먼트 트리를 잘 사용하면 풀리겠다고 생각했다.

이 문제에서 4점만 긁고 넘어갔는데, 2번 섭태를 구체화시키지 못한 것이 안타깝다.

이 문제는 서브태스크가 꽤나 많이 나누어져 있었다.

서브태스크 1은 간단한 투 포인터로, 서브태스크 2, 3은 $O(NM)$의 간단한 DP로 해결할 수 있었다.

서브태스크 4부터는 $O(NM)$의 시간복잡도가 불가능했고, 그리디한 방법이나 DP를 잘 최적화해야 할 것 같았다.

DP 테이블의 차 배열과 레이지 프로퍼게이션을 잘 이용해 풀어보려고 했지만, 실패했다.

이 서브태스크만 해결한다면 확장이 그렇게 어렵지 않을 것이라 생각했는데, 이 서브태스크가 끝까지 풀리지 않았다.

인터랙티브 문제였다.

서브태스크 1은 답을 직접 비트로 전송하는 방식으로, 서브태스크 2는 모든 간선에 대한 정보를 직접 비트를 전송하는 방식으로 풀 수 있었다.

서브태스크 3부터는 전혀 감도 안 와서 풀지 못했다.

컨디션이 나쁘고, 시간이 부족했다고 상상을 초월하는 점수가 나온 것이 매우 실망스러웠다.

결론적으로 1, 2, 3번 모두 어려운 문제는 맞았지만, 관찰을 통해서 잘 해결했으면 좋았을 것이라는 생각이 들었다.

특히 나는 대회 시간 중에 D3 이상의 문제를 자력으로 푼 적이 없는데, 이 구간을 잘 넘기면 앞으로 더욱 실력을 높일 수 있을 것 같다.

1번 문제를 업솔빙했다.

대회 시간 중에도 생각한 방법이 있었는데, 이를 조금만 더 구체화시켰으면 풀 수 있었을 것 같다.

기본적으로는 합성함수 세그먼트 트리를 이용할 것이다.

각 도로에 대해서 들어온 시간($T_{in}$)에 대한 나가는 시간($T_{out}$)과 비용($C$)의 함수를 관리할 것이다.

도로 1개에 대해서만 함수를 생각해보면, 다음 그림과 같을 것이다.

$T_{out}$의 그래프는 z 모양, $C$의 그래프는 _/ 모양이다.

이 함수를 여러 번 합성한다면, $T_{out}$의 그래프는 여전히 z 모양을 유지한다는 것은 자명하다.

$C$의 그래프 형태가 좀 애매한데, 함수를 몇 가지 경우에 대해 합성해보면 $T_{out}$의 그래프가 꺾이는 두 번째 지점의 x좌표와 같은 x좌표에서 꺾이는 _/ 모양의 그래프라는 것을 알 수 있다.

따라서 $T_{out}$과 $C$의 함수를 변수 4개($l$, $r$, $y$, $v$)로 표현할 수 있고, 이를 합성하는 세그먼트 트리를 짜면 간단하게 풀 수 있다.