HYEA cup H - Too Many Traps 풀이

문제 링크

공식 에디토리얼

1년 가까이 틀려 있었던 문제다. 에디토리얼을 읽고도 이해를 못해서... 내가 이해한 대로 다시 써보려고 한다.

문제 요약

수직선상에 $M$개의 이불이 있고, 혜아는 원점 $0$에 서 있다.

혜아는 $N$개의 신발을 가지고 있는데, $i$번째 신발을 사용하면 $A_{i}$만큼 +방향으로 갈 수 있다.

$M < N$이 성립할 때, 모든 신발을 한 번씩만 사용하여 이불에 닿지 않고 $A_{1} + A_{2} + \cdots A_{N}$으로 갈 수 있겠는가? 있다면 순열을 construct하고, 아니면 -1.

제한 :

$1 \le M < N \le 10^{5}$, $1 \le A_{i} \le 10^{9}$, 이불의 위치 $X_{j} \le 10^{14}$.

$A_{i}$는 서로 다른 수이다.

---

This section is intentionally left blank.

---

Induction - $O(N^2)$ solution

이 문제의 원본은 IMO 2009 p6(스포주의, 기만주의)이다.

결론부터 말하자면, $A_{1} + A_{2} + \cdots + A_{N}$에 이불이 있는 경우만 아니라면 항상 이불을 밟지 않고 갈 수 있다.

Claim. $A_{1} + \cdots + A_{N}$에 이불이 존재하지 않고 $M < N$이라면 항상 이불을 밟지 않고 가는 방법이 존재한다.

$M < N$이 성립한다는 데 주목하자. $N = 0,1$이라면 이불이 존재하지 않기 때문에 항상 가능하다.

$N = 1$ 이야기를 꺼내는 거 보니 뭔가 induction을 잘 때리면 될 것 같다는 생각이 든다. 이 문제에서 핵심적인 아이디어 2개는 가장 긴 점프(신발) $A_{N}$과 가장 가까이 있는 이불이다.

매끄러운 설명을 위해, 다음의 정의 및 가정을 도입한다 :

- $A_{1} < A_{2} < \cdots < A_{N}$

- "$A_{i}$에 이불이 있다" = "현재 위치에서 $A_{i}$만큼 점프했을 때 이불이 있다."

핵심 아이디어 2개를 가지고 Case study를 하자.

Case 0. 남은 이불이 0개인 경우 (base case)

남은 점프를 모두 사용하면 된다. 끝. 이 경우는 $N = 0,1$을 포함하므로, 나머지 경우에서는 $N \ge 2$를 가정한다.

Case 1. $A_{N}$에 이불이 있는 경우

Case 1-1. $A_{N}$보다 가까이 있는 이불이 없는 경우

$A_{N}$만큼 점프한 뒤에 신발 $N-1$개, 이불 $M-1$개짜리 부분문제를 푼다. 부분문제에서도 이불<신발임에 주목하자.

그 뒤에 $A_{N}$과 부분문제에서의 첫번째 점프를 swap하면 $A_{N}$에 있는 이불과 그 뒤의 이불을 모두 밟지 않을 수 있다.

Case 1-2. $A_{N}$보다 가까운 이불이 있는 경우

$N-1$개의 pair $(A_{i}, A_{i} + A_{N})$를 고려하자. $A_{N}$을 제외한 이불의 개수는 $M-1 < N-1$이므로, 비둘기집의 원리에 의해 어떤 $j$가 존재해서, $A_{j},A_{j} + A_{N}$ 모두 이불이 없다.

따라서 $A_{j},A_{N}$으로 2번 점프하고, 신발 $N-2$개와 이불 $M-k$개짜리 부분문제를 풀면된다.

여기서 $k := A_{j} + A_{N}$보다 가까운 이불의 개수. (가장 가까운 이불), ($A_{N}$의 이불)이 모두 스킵되므로 $k \ge 2$이다.

Case 2. $A_{N}$에 이불이 없는 경우

Case 2-1. $A_{N}$보다 가까운 이불이 없는 경우

일단 $A_{N}$으로 점프를 하고, 가장 가까운 이불을 고려하지 않은 신발 $N-1$개, 이불 $M-1$개짜리 부분문제를 푼다.

만약 부분문제의 $t$번째 점프가 가장 가까운 이불에 착지한다고 하면, $t+1$번째 점프와 $A_{N}$을 swap하면 된다. (Remark - $t$번째 점프는 마지막 점프가 아님이 보장된다)

Case 2-2. $A_{N}$보다 가까운 이불이 있는 경우

그냥 $A_{N}$으로 점프하면 이불의 개수는 하나 이상 줄어든다. 끝.

이를 Naive하게 구현하면 $O(N^2)$ 내지는 $O(N^2\lg N)$에 문제를 해결할 수 있다.

---

Optimization - $O(NlgN)$ solution

케이스별로 시간복잡도를 적어보자.

현재 상황이 어떤 Case에 속하는지는 신발, 이불을 관리하는 set 등을 사용해 $O(\lg N)$에 알 수 있다.

Case 1-1 : $O(1)$. 

비고 : swap이 필요하다.

Case 1-2 : 모든 $A_{i}$를 돌면서 $A_{j}, A_{j}+A_{N}$이 모두 이불의 set에 속하지 않는 $j$를 찾으면 break해주면 된다. $O(k\lg N)$.

비고 : Case 1-2의 모든 $k$를 합한 값은 $M$이하이므로, Case 1-2의 모든 호출을 다 합한 복잡도는 amortized $O(N\lg N)$이다.

Case 2-1 : 부분문제에 대해 이동거리의 누적합을 저장하는 배열이 필요해 보인다. 누적합 $O(N)$. swap 때문에 계속 갱신이 일어나서 $O(1)$이 안된다.

Case 2-2 : $O(1)$.

결국 Case 2-1의 갱신(swap)을 잘 버틸 수 있는 자료구조가 있으면 되는데, 이는 BIT를 사용하면 충분하다.

즉, BIT에 $i$번째 점프를 BIT의 $i$번째 entry에 저장하되, $BIT.sum(j) = x$인 $j$를 (존재한다면) report하는 쿼리 함수를 적절히 $O(\lg N)$으로 구현하면 모든 Case가 $O(\lg N)$이 되어서 문제를 해결할 수 있다. 그냥 BIT 이진 탐색으로 $O(\lg^{2} N)$짜리 쿼리를 짜도 되고, 이 방법도 시간 내에 돌아간다고 한다.

---

Details

- $i$와 $A_{i}$가 일대일대응되기 때문에, 인덱스를 일일이 들고 다니지 않고 마지막에 출력할 때만 map으로 찍으면 된다.

- BIT에서 query(x)를 구현하는 코드는 다음과 같다. f[i]는 BIT의 i번째 entry를 나타낸다.

int bs(ll q){
    int ans = 0;
    ll csum = 0;
    for(int b = 16; b >= 0; b--){
        if(csum + f[ans | 1 << b] == q) return ans | 1 << b;
        else if(csum + f[ans | 1 << b] < q) ans |= 1 << b, csum += f[ans | 1 << b];
    }
    return 0;
}
- set::rbegin() (또는 --set::end()), set::begin() 등의 iterator가 도움이 된다.