[14346] Radioactive Islands (Small)

 

14346번: Radioactive Islands (Small)

 

일단 배의 궤적은 함수로 나타낼 수 있다. 말인즉슨, 궤적은 \(x\) 좌표 하나에 한 개의 점만 대응된다는 뜻이다.
만약 \(x\)좌표 하나에 여러개의 점이 대응된다고 해보자. 즉, 배가 한 번 양의 \(x\)의 방향으로 갔다가, 다시 \(-x\) 방향으로 갔다가, 다시 방향을 트는 궤적을 그린다는 것이다. 그러한 궤적이 최선의 이동 궤적이 되는 경우가 있을까?
일단 Small 문제의 경우(\(N = 1\)로 고정)에는 그러한 경우가 없다.
Large (\(N = 2\))의 경우에도 그러할 것인데, 사실 엄밀한 증명은 잘 못 하겠다.

대충 왔다리갔다리하는 궤적은 항상 일부 구간을 살짝 바꿔서 더 효율적인 궤적을 만들 수 있는 것으로 보인다. 그렇게 믿고 문제를 풀기로 했다.

어쨌든 그래서 배의 궤적의 \(y\) 좌표를 \(x\)에 대한 함수로 나타내서 \(y(x)\)라 하자.
그럼 배의 속도가 \(1\)로 고정되어 있으므로 간단히 문제를 다음과 같이 고칠 수 있다.

$\displaystyle\int_{-10}^{10}\left(1+\sum _{i=1}^N\frac{1}{x^2+\left\{y\left(x\right)-c_i\right\}^2}\right)\sqrt{1+\left\{y^{\prime}\left(x\right)\right\}^2}dx$
Small에서는 \(N = 1\)이니까 시그마 떼고
$displaystyle\int _{-10}^{10}\left(1+\frac{1}{x^2+\left\{y\left(x\right)-c\right\}^2}\right)\sqrt{1+\left\{y^{\prime}\left(x\right)\right\}^2}dx$
이제 구해야 하는 것은 저 적분 값을 최소화하는 $x$에 대한 함수 $y$이다. 여기서 난관 봉착. 함수를 어떻게 구한다는 말일까?
학교에서 배운 것은 다항함수, 삼각함수, 지수/로그함수, 유리함수, 무리함수 뿐인데
최적의 궤적이 그런 특수한 꼴을 해 줄까? 그럴 리는 없을 테니까 다른 방법을 찾아보자.

$y, y^{\prime}, x$에 대한 함수를 오일러-라그랑주 방정식에 냅다 넣어서 미분방정식을 풀면 된다.
​$\displaystyle f\left(y,\ y^{\prime};\ x\right)=\left(1+\frac{1}{x^2+\left\{y-c\right\}^2}\right)\sqrt{1+\left\{y^{\prime}\right\}^2}$
$\displaystyle J\left[y\right]=\int _{-10}^{10}f\left(y,\ y^{\prime};\ x\right)dx$
로 범함수 \(J\)를 정의한 뒤에
오일러 라그랑주 방정식
$\displaystyle \frac{\partial f}{\partial y}-\frac{d}{dx}\left(\frac{\partial f}{\partial y^{\prime}}\right)=0$
에 집어넣어서 (미분 노가다...) 만들어 낸 식이 바로!
$\displaystyle y^{\prime\prime}=-\frac{2\left\{\left\{y^{\prime}\right\}^2+1\right\}\left(y-c-y^{\prime}x\right)}{\left(\left(c-y\right)^2+x^2\right)\left(\left(c-y\right)^2+x^2+1\right)}$
이다.

더럽게 생긴 비선형 미방이니까 풀 엄두는 안 나고 룽게쿠타로 풀면 되겠다.
초기의 \(x, y\) 값은 문제에서 주는데, 달라는 \(y^{\prime}\)는 안 주고 끝점을 줘서 좀 난감하다.
처음 순간변화율을 구하기 위해서는 어떻게 해야 할까?

1. 뭔가 수식으로 해결을 본다.
2. 원하는 값을 탐색 한다면?

 적절한 기울기가 있고 시작 위치에서 그 기울기로 궤적을 그리기 시작해서 미분방정식을 따르며 이동하면 문제에서 제시한 끝점에 도달해야 한다.

만약 최적 경로의 경우보다 더 아래로 꺾인 기울기로 시작했다면? 도달 지점은 우리가 원하는 끝점보다 아래일 것이다.
더 위로 꺾인 기울기라면? 끝점보다 더 위의 점에 도달할 것이다. 기울기가 도착 지점의 $y$값에 영향을 준다. 그렇다면?

이분 탐색을 적용하면 된다. 이분 탐색을 쭉 하다가 적당히 \(x=10\)일 때의 \(y\)값 차이가 목표한 값이랑 가까울 때 끊으면 된다.
물론 이대로만 구현하면 TLE 혹은 WA다. 생각해야 할 것은 로컬 최적점인데,

1. 로컬 최적점에 빠져서 일단 시작-끝을 잇긴 하는데 최적 경로가 아닌 경우.

Small 문제의 경우 빠지기 쉬운 로컬 최적점이 하나는 있는 것 같다. 섬 위를 지나가는 경우와 섬 아래를 지나가는 경우 둘 중 하나는 최적해가 아님은 당연하니까...

이 문제는 시작지점과 섬 사이의 직선의 기울기를 기준으로 해서 위/아래로 탐색 구간을 잘라 두번 돌려서 해결했다. 어떻게 이걸로 해결이 되냐면...

A. 처음에 시작지점-섬 잇는 직선을 기준으로 위로 꺾여 올라가다가 섬 아래를 지나게 되는 궤적의 경우 무조건 이보다 더 효율적인, 처음에 아래로 꺾여 내려가는 궤적이 존재할 것이다. 반대의 경우도 마찬가지.

B. 궤적이 최적해를 찾으며 연속적으로 변화하는 과정에서(구현은 당연히 Discrete하긴 한데 상관없고) 가운데에 있는 섬을 도저히 넘어갈 수가 없다. 일단 넘어간다 함은 한번 지나기는 해야 한다는 건데 저 방사능 섬 살아서 뚫어 건널 자신 있음? 방사능 무한대로 발산, 항해는 개같이 멸망...

Large의 경우 섬이 두 개니까 구간을 셋으로 잘라 해결할 수 있을 것으로 기대된다. 아직 안 풀어봄 ㅎㅎ

 

2. 로컬 최적점에 빠져서 극값은 찾았는데 시작과 끝이 안 이어지는 경우.
1번 해결하면서 탐색 구간 위 아래로 나눈 후일 테니까 2번 문제가 뜨면 탐색 종료하면 된다. 다른 쪽에 답이 있겠지...

어쨌든 이거 구현하면 된다. RK4 쓸 때 h값은 대충 적당히 잡아서. 나는 탐색할 때 쓴 RK4의 \(h\)랑 나중에 적분할 때 쓴 RK4의 \(h\)값이 다르게 구현했다. TLE날까봐 무서워서...

Large 풀러 떠남