SCPC 2019 1차예선 풀이, 후기

SCPC도 올해로 3년차다. 학기중에 Problem Solving을 못해서 감이 좀 떨어졌을까 걱정했지만 작년보다 결과가 좋았다.

1번-2번-5번-3번-4번 순서로 풀었다.

 

문제 1. 오르락 내리락

설명

함수 \(F(x)\)가 다음과 같이 정의된다고 하자.

$$F(x) = \begin{cases} F(x+1) + 1, & \text{x가 3 이상의 홀수} \\ F(x/2) + 1, & \text{x가 짝수} \\ 0, & x = 1 \end{cases}$$

정수 \(N, M\) (1 ≤ \(N\) ≤ \(M\) ≤ 1,000,000)을 받아서 \(F(N) + F(N+1) + ... + F(M)\)을 계산하는 것이 문제다.

 

제한시간: 10,000개 이하의 테스트 케이스에 대한 실행시간 총합이 1초 이내 (Java 2초 이내)

풀이

\(F(x)\)의 정의를 잘 살펴보면 \(F(x) = O(\lg{x})\)임을 알 수 있다. 따라서 모든 가능한 \(x\)값에 대해 전부 다 미리 계산하더라도 1초 내에 가능하다.

 

이때 Range Query로 \(F(x)\)의 구간합을 구해야 하기 때문에 그냥 For문을 돌면 시간초과가 날 것이다. Prefix Sum을 구한 다음 Psum[M] - Psum[N - 1]로 풀어야 한다.

 

문제 2. 공 굴리기

설명

반지름 \(R\)인 공이 직사각형 모양의 장애물 \(N\)개를 넘어 굴러갈 때 중심의 궤적 길이를 구하는 문제다.

이때, 장애물은 모두 땅에 붙어있으며 두 인접한 장애물의 옆면은 최소 \(2R\) 초과만큼 떨어져 있다.

공이 이동할 때는 중력에 의해 반드시 땅 혹은 장애물에 붙어서 이동한다고 가정한다.

공의 초기 시작위치 \(x\)좌표는 \(S\), 최종위치는 \(E\)이다. \(S\), \(E\) 역시 인접한 장애물과 최소 \(2R\) 초과만큼 떨어져 있다.

 

제한시간: 150개 이하의 테스트 케이스에 대한 실행시간 총합이 1초 이내 (Java 2초 이내)

풀이

장애물이 모두 \(2R\) 이상 떨어져 있기 때문에 각각을 독립적으로 고려할 수 있다.

장애물의 높이를 \(H\)라고 하면, 하나의 코너에서 늘어나는 이동거리는

• \(R \le H\)인 경우:
  • 원래 이동거리는 \(R\)이었다.
  • 장애물이 있을 때 이동거리는,
    • 공이 기어올라가야 하므로 그 거리는 \(H - R\)이고,
    • 코너에서 도는 거리는 항상 90도를 돌아가므로 \(\pi R/2\)다.
• \(R > H\)인 경우: 
  • 원래 이동거리는 \(R \sin{\theta}\)였다. (\(\theta\): 올라가기 직전에 공의 중심과 장애물의 모서리를 이은 직선이 평면에 수직인 직선과 이루는 각도)
  • 장애물이 있을 때 이동거리는, 원호의 길이인 \(R \theta\)다.

 

 

이렇게 각 장애물에 대해 (장애물이 있을 때 이동거리) - (장애물이 없을 때 이동거리)를 계산해서 \(E - S\)에 더해주면 \(O(N)\)에 해결되는 쉬운 문제다. 이때, 장애물의 코너가 두 개이므로 한 번만 더해주지 않도록 주의한다. (실수해서 틀렸었음ㅋㅋ)

 

문제 3. 점프

설명

삼각수 \(T_n\)은 1부터 \(n\)까지 모두 더한 수로, 다음과 같이 주어진다.

$$T_n = \frac{n(n+1)}{2}.$$

함수 \(F(x)\)를 다음과 같이 정의하자. (\(F(0) = 0\)으로 정의함)

$$F(x) = \min_{T_{n_1} + T_{n_2} + \cdots = x}{n_1 + n_2 + \cdots}$$

즉, \(F(x)\)는 \(x\)를 삼각수의 합으로 표현했을 때 각 삼각수의 원래 \(n\)값의 합의 최솟값이다.

 

자연수 \(1 \le M \le N \le 10^{11}\)에 대해, \(F(x)\)의 구간 최댓값

$$\max_{M \le x \le N}{F(x)}$$

를 구하는 프로그램을 작성하시오.

 

제한시간: 40개 이내의 테스트 케이스에 대한 실행시간 총합이 2초 이내 (Java 4초 이내)

 

풀이 업데이트 (2019/6/22 19:00)

충분히 큰 \(x\), 즉 \(x \ge 1173\)에 대해서는 \(x\)보다 작거나 같은 최대의 삼각수 \(T_n\)을 포함하는 최적해가 반드시 존재한다고 한다. 증명은 (아마) \(x\)값에 대해 루즈한 바운드를 찾은 다음(한 10,000쯤?) 그 미만의 모든 \(x\)값을 컴퓨터로 확인하면 될 것이다. 직관적으로 생각해보자면 아마 \(T_n\)이 \(n\)에 대해 아래로 볼록이기 때문에, 나눠 가지는 것보다는 몰아주는 쪽이 유리해서 그런 것 같다.

 

따라서 \(x\)가 1173보다 작아질 때까지 \(x\)보다 작거나 같은 최대의 삼각수를 빼 준 다음, 그렇게 해서 남은 값에 대한 \(F(x)\) 함수값은 아래의 \(O(N\sqrt{N})\) 점화식을 써서 미리 구한 테이블을 참조하면 될 것이다. \(x \le 10^{11}\)에 대해서, 두 번만 이렇게 삼각수를 빼 주면 반드시 1173보다 작아진다. 따라서 한 점에서의 함수값을 계산하는 과정은 사실상 \(O(1)\)이라고 할 수 있다.

 

이렇게 하면 부분문제 2까지 해결되고, 부분문제 3을 해결하기 위해서는 아래의 풀이에 있는 \(G(n)\)에 관한 내용을 그대로 적용하면 된다.

 

* 그리고 사실 아래에 있는 내용은 하나도 증명하지는 못했다. 대강 점근분석으로 찍은 다음에 컴퓨터를 돌려서 그럴듯한 알고리즘을 만들었을 뿐...

풀이

정수론 문제를 풀어본 적이 잘 없어서 고생했다(ㅜㅜ). 일단, 기초적인 관찰을 통해 다음 점화식을 얻을 수 있다.

$$ F(x) = \begin{cases} n, & x = \frac{n(n+1)}{2} \\ \min_{k < x}{F(k) + F(x-k)}, & \text{otherwise} \end{cases} $$

하지만 이는 불필요하게 많은 \(k\)값을 고려한다. 삼각수 하나씩만 잘라내도록 하면 다음과 같이 바꿀 수 있다.

$$ F(x) = \begin{cases} n, & x = \frac{n(n+1)}{2} \\ \min_{T_{k} < x}{F(T_k) + F(x-T_k)}, & \text{otherwise} \end{cases} $$

이 점화식을 쓰면 \(1 \le x \le N\)인 모든 \(x\)에 대해 계산하는 데 \(O(N \sqrt{N})\)의 시간이 소요된다. 따라서 \(N \le 10,000\)인 부분문제 1은 해결된다.

 

하지만 전체문제는 해결되지 않는다. 어떻게 해야 할까? 그래서 수학적인 성질을 조금 더 파 보았다.

그러면 다음을 알 수 있었다.

• \(x = \frac{n(n+1)}{2} + k\) (단, \(0 \le k \le n\))이라면, \(n \le F(x) \le n + F(k)\).

즉, \(F(x) \sim \sqrt{2x}\). 이를 이용해 조금 더 생각하면 모든 최적해가 다음 성질을 만족함을 알 수 있다. 왜냐면 \(F(2T_{n}) \sim \sqrt{2}\,n < 2n = 2F(T_{n})\)이기 때문이다.

• 각 \(T_{n}\)는 4개의 예외를 제외하면 기껏해야 한 번 등장할 수 있다.
• 4개의 예외는 \(T_1, T_3, T_4, T_9\)로, 이들은 기껏해야 두 번 등장할 수 있다.

즉, 같은 삼각수가 두 번 등장할 일은 거의 없다. 그런데 조금만 더 생각해보면, \(m\)과 \(n\)이 충분히 가까울 경우에도 비슷한 논리가 성립함을 알 수 있다. \(n = \alpha m\) \((\alpha > 1)\)이라고 하면,

• \(F(T_n + T_m) \sim \sqrt{n(n+1) + m(m+1)} \sim \sqrt{1 + \alpha^2}m < (1+\alpha)m = F(T_n) + F(T_m)\).

즉, 근사가 성립하는 범위라면 (i.e. \(m\)과 \(n\)이 모두 충분히 크고 두 수가 일정 범위 이내로 가까운 경우), 둘은 최적해에 동시에 등장할 수 없다.

 

따라서 \(K = \lceil \sqrt{2\times10^{11}} \rceil \)에 대해 \(1 \le x \le K\) 범위의 함수값은 점화식을 써서 \(O(K \sqrt{K})\) 내에 구하고, \(x > K\) 범위의 함수값은 다음 점화식을 고려하면 된다.

$$F(x) = \min_{x - T_Q \le K} Q + F(x - T_Q)$$

이렇게 하면 \(N - M \le 10^4\)인 부분문제 2까지 해결되지만 부분문제 3은 힘들다. 이를 해결하기 위한 마지막 관찰은 다음과 같다.

• \(G(n)\)을 다음과 같이 정의하자. $$G(n) = \max_{T_n \le x < T_{n+1}} F(x)$$
• 그러면 \(G(n)\)은 단조증가함수이다.

따라서, \(M\)과 \(N\)이 세 개 이상의 삼각수 구간에 걸쳐있는 경우 상위 2개의 구간만 남겨도 최댓값이 올바르게 구해진다. 그러면 고려할 총 가짓수가 \(O(\sqrt{N})\)으로 줄어들어 부분문제 3까지 해결된다.

문제 4. 파이프

설명

반지름이 고정된 파이프 \(N\)개가 주어진다. 이들을 모두 같은 방향으로 놓는 상황만 생각하면 2차원 문제가 된다.

그림은 두 가지의 가능한 배치를 예로 든 것인데, 왼쪽보다는 오른쪽의 배치가 원 양끝 거리가 짧다는 것을 알 수 있다. 단, 모든 원은 반드시 바닥에 닿아있어야 한다.

파이프의 반지름이 주어졌을 때, 양끝 길이를 최소화하는 배치의 각 파이프 중심 \(x\)좌표를 출력하시오.

테스트 케이스 \(n\)에 대해 주최측이 가지고 있는 답을 \(B_n\)이라고 했을 때, 양끝 길이를 \(2B_n\) 이하로 줄여야만 해당 테스트 케이스에 대해 점수를 받을 수 있다.

 

제한시간: 30개 이하의 테스트 케이스에 대한 실행시간 총합이 2초 이내 (Java 4초 이내)

풀이

원들이 반드시 바닥에 붙어있어야 하므로 각각의 배치는 N!개의 순열 중 하나로 표현할 수 있다.

이제, 주어진 그림을 보고 떠올린 휴리스틱은 다음과 같다.

• 주어진 반지름을 오름차순으로 정렬한다. R[0], R[1], ..., R[N-1]이라고 하자.
• 이제, R[N-1], R[0], R[N-2], R[1], ...으로 배치한 다음 최대한 바싹 붙인다.

이렇게 했더니 200점 만점에 186점이 나왔다. 나머지 점수를 받으려면 최적화를 해야 한다. 가장 간단하게 생각할 수 있는 다음 scheme을 고려해보자.

• 임의의 두 원 \(i, j\) \((i \neq j)\)을 뽑아 자리를 바꾸는 상황을 고려한다.
• 이 자리바꿈에 의해 양끝 길이가 줄어들면 바꾸고, 그렇지 않으면 바꾸지 말고 그대로 둔다.

이 과정을 1,000번 반복하도록 했더니 만점이 나왔다.

 

문제 5. 세포 키우기

설명

좌표평면 위에 선분 \(S: (L, 0) - (R, 0)\) 이 있다. 이 선분 \(S\) 위의 임의의 한 점 \(P(p,0)\)를 잡아, \(P\)를 중심으로 하고 각 변이 좌표축에 평행한 정사각형 

$$\max{\lbrace|x - p|, |y|\rbrace} = r$$

를 고려하자. 평면 위에는 장애물 점이 \(N\)개 있기 때문에, 정사각형 한 변 길이의 절반인 \(r\)는 무한정 커질 수 없다. (단, 경계에는 닿을 수 있다.)

 

선분의 양 끝점을 지정하는 \(L, R\) 및 \(N\)개의 장애물 점의 좌표가 주어졌을 때, 가능한 모든 \(P\)점에 대해 정사각형 한 변 길이 \(2r\)값의 최댓값을 구하시오.

 

제한시간: 40개 이내의 테스트 케이스에 대한 실행시간 총합이 2초 이내 (Java 4초 이내)

풀이

일단, 각 장애물 점의 \(y\)좌표는 부호가 상관이 없으므로 모두 양수 혹은 0으로 바꿔줄 수 있다.

이제, 하나의 장애물 점 \(P_n(a_n, b_n)\)은 선분 위의 각 점에 대해 \(r\)값에 다음과 같은 제한조건을 부과한다.

$$r \le R_n(x) = \begin{cases} a_n - x, & x < a_n - b_n \\ b_n, & a_n - b_n \le x \le a_n + b_n \\ x - a_n, & x > a_n + b_n \end{cases}$$

 

위 제한조건은 필요충분조건이므로, 어떤 위치 \(x\)에서 \(r\)값이 가능할지 여부는 다음 식으로 주어진다.

$$r \le \min_{1\le n\le N}{R_n(x)}.$$

 

그러면 위 식의 최댓값(in [L, R])을 효율적으로 구하는 일만 남았다. 분할정복 알고리즘을 사용하면 \(O(N \lg{N})\) 내에 풀 수 있다. 왜 그런지 살펴보기 위해, 다음 함수를 정의하자.

$$ F_{i,j}(x) \equiv \min_{i\le n\le j} {R_n(x)}. $$

그러면 \(F_{i,j}(x)\)는 최대 \(4(j-i+1) + 1\)개의 선분 조각으로 구성된다. 그 이유는 다음과 같다.

• \(F_{i,j}(x)\)의 모든 선분 조각은 어떤 \(R_n(x)\) 그래프에서 와야 한다.
• \(R_n(x)\)의 선분 조각은 내려오는 구간(기울기 -1), 평탄한 구간(기울기 0), 올라가는 구간(기울기 +1)으로 구성된다.
  • 기울기 -1인 조각은 기껏해야 하나밖에 존재할 수 없다. 다른 어떤 조각이 아래부분을 잘라먹었다면 아래부분은 통째로 사라지지, 일부만 잘리고 저 밑에는 남고 이럴 수 없다. 따라서 최대 \((j-i+1)\)개.
  • 기울기 +1인 조각도 마찬가지로 기껏해야 하나다. 따라서 최대 \((j-i+1)\)개.
  • 기울기 0인 조각은 기울기가 \(\pm 1\)인 조각 사이나 끝에만 존재할 수 있으므로, 그 개수는 최대 (기울기가 \(\pm 1\)인 조각의 개수) \(\times\) 2 + 1개뿐이다.

이제 분할정복을 이용해 \(F_{i,k}(x)\) 및 \(F_{k+1,j}(x)\)를 합치는 것은 선형시간 내에 가능하므로 전체 시간복잡도는 \(O(N \lg{N})\)이 된다.

 

5번 문제의 구현은 https://paido.tistory.com/15에 올려두었다. 

 

처음으로 만점을 맞은 거라 기분이 좋다.^^ 이번 대회에선 상 받으면 좋겠다~