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가 도움이 된다.