BOJ 23176

 

 

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

 

 

코드

http://boj.kr/7d3b2e772d524996bab2a9994f076fe5

 

2021 KAIST 11th ICPC Mock Competition G

 

난이도 : D5

 

Elapse Time : 80min

 

체력의 상한이 존재하지 않는다면 $i$번째 과정이 끝난 뒤 남은 체력은 $x+a_1+\cdots+a_i$이다. 남은 체력이 누적합과 연관되어 있긴 한데 상한이 존재한다는 것이 문제였다. 체력이 변하는 과정에서 언제 체력이 최솟값이 될지를 생각해 보니 구간합이 최소인 구간의 끝일 것 같다는 느낌이 왔다. 구간합이 최소인 구간을 $[s, e]$라고 하면 $s\leq i\leq e$인 $i$에 대해 $a_s+\cdots+a_i\leq 0$이고 $a_1+\cdots+\a_{s-1}\geq 0$이기 때문에 $s-1$번 과정이 끝난 직후에는 체력이 $x$이고 $e$번 과정이 끝난 뒤 체력은 $x-(a_s+\cdots+a_e)$가 된다. 스킬을 사용하는 구간이 주어지기 때문에 이를 구간별로 관리할 필요가 있고 이를 세그먼트 트리로 관리하기로 했다. 처음에는 누적합의 최댓값과 최솟값을 저장해 놓고 그 차이를 활용해 구간합의 최솟값을 구하려고 했는데 쿼리당 시간복잡도가 $logn$보다 커져 실패했다. 다른 방법을 생각하다가 금광세그를 사용하면 쉽게 구할 수 있겠다는 생각이 들어 구간 내 연속합의 최솟값을 구할 수 있는 금광세그를 만들었다. 이제 스킬을 쓰는 구간인 $[l, r]$이 주어졌을 때 죽는지 여부와 안 죽었을 때 남은 체력을 구해야 한다. $[1, l-1]$에서 연속합의 최솟값이 $x$이하라면 스킬 전에 죽는다. $[1, l-1]$에서 죽지 않았다면 $[l,r]$ 사이에 체력이 $(x+9)/10$이하로 떨어지는 경우가 있는지를 확인해야 한다. 체력이 $(x+9)/10$이하로 떨어지는 경우가 있다면 구간 $[r+1,n]$에서 $(x+9)/10$만큼의 체력을 가지고 시작했을 때 죽는지를 확인해 주고 없다면 구간 $[1,n]$에서 죽는 경우가 있는지를 확인해 주면 되겠다는 생각을 했다. 남은 체력은 금광세그에 요청한 쿼리의 결과의 $r$값을 $x$에 더하면 구할 수 있다. 여기서 $[l,r]$ 사이에 체력이 $(x+9)/10$이하로 떨어지는 경우가 있는지를 확인해야 하는데 $[1,r]$ 사이에 체력이 $(x+9)/10$이하로 떨어지는 경우가 있는지를 확인하는 코드를 작성하여 WA를 한 번 받았고 스킬의 효과가 발동되어 $(x+9)/10$의 체력을 가지고 $r+1$번째 과정을 시작해도 체력의 상한은 $x$가 되는데 상한을 $(x+9)/10$으로 설정하여 계산했다가 WA를 한 번 더 받았다. 체력의 상한이 $x$인데 $(x+9)/10$의 체력을 가지고 시작할 때에는 $node(x- (x+9)/10)$에 $[r+1,n]$ 쿼리의 결과 노드를 붙여주면 된다.