BOJ 10760

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

 

코드

http://boj.kr/2d99b1fb4d394b3a810946241c8a2e1e

업솔빙

http://boj.kr/34a429ec34da451bba1b598137e5fca8

 

USACO Open Contest 2015 Gold 3

 

난이도 : P1

 

Elapse time : 100min

 

처음에 이 문제를 봤을 때는 시뮬레이션을 하지 않고 어떻게 풀 수 있을까? 였다. 이때 든 생각이 $i$번째 건초더미와 $j$번째 건초더미 사이에 있을 때 각각의 크기가 $p_j-p_i$이상이면 두 건초더미 사이를 절대 나갈 수 없다는 것이었다. 그렇다면 이 조건을 만족하는 모든  구간 길이의 합을 구하면 된다. 이 아이디어를 떠올리기까지 30분이 걸렸는데, 이를 구현하는 것도 만만치 않았다. 우선 대칭적이라는 사실을 활용하여 한 건초더미를 기준으로 오른쪽만 보기로 했다. 위치가 $p_i$ 이고 $s_i$인 건초더미를 기준으로 위치가 $p_i+s_i$이하인 건초더미만 보면 된다. 이는 이분탐색을 활용하여 몇 번째 $idx$까지 보면 되는지 $nxt$에 저장해 놓았다. 위치가 $p_j$인 건초더미는 $s_j\geq p_j-p_i$를 만족해야 한다. 이 식을 변형하여 $p_i\geq p_j-s_j$로 만들었다. $i\leq j<nxt[i]$를 만족하는 $j$ 중 $p_i\geq p_j-s_j$를 만족하는 가장 큰 $j$를 구하면 된다. 이를 값 압축과 세그먼트 트리를 활용하여 구하였는데 첫 WA를 받았다. $i$를 증가시킬 때 $j$를 $nxt[i]$까지 증가시키면서 범위를 구해나갔는데 $nxt[i]>nxt[j] (i<j)$인 경우 때문에 반례가 나왔다. $ord$ 배열을 만들어 $nxt$가 증가하는 순서대로 $i$별로 조건을 만족하는 가장 큰 $j$를 구하고 이 범위를 $set$에 넣는 형식으로 두 번째 답안을 작성하였는데, $set$ 안에서 겹치는 구간이 나오게 되면서 두 번째 WA를 받았다. 이를 해결하기 위해 $range$ 배열을 만들어서 각 $i$별로 조건을 만족하는 가장 큰 $j$를 $range[i]$에 넣어두고 투 포인터처럼 범위들을 훑는 방식으로 풀어 맞게 되었다.

 

다른 사람들의 풀이를 보다가 나의 풀이보다 훨씬 쉬운 풀이가 존재한다는 것을 깨달았다. jhwest2님의 풀이이다.

$i$번째 건초더미와 $j$번째 건초더미 사이에 있을 때 각각의 크기가 $p_j-p_i$이상이면 두 건초더미 사이를 절대 나갈 수 없는데, 두 건초더미 중 작은 것의 크기만 $p_j-p_i$이상이면 된다. 위치가 $p$이고 크기가 $s$인 건초더미가 있다고 할 때 위치가 $p-s$, $p+s$ 사이인 건초더미 중 크기가 $s$ 이상인 건초더미가 있으면 두 건초더미 사이는 절대 빠져나갈 수 없다. 건초더미를 크기 내림차순으로 정렬한 뒤 각 큰 건초더미부터 건초더미의 위치와 인덱스를 $set$에 저장해 놓고 건초더미를 하나씩 보면서 위치가 $p-s$, $p+s$ 사이에 있는 건초더미들의 최소 인덱스와 최대 인덱스에 표시를 해둔 뒤 이를 스위핑 하면서 각 범위가 탈출할 수 없는 범위 내에 있는지 판단할 수 있다.