[일반] 백준 17318번 질문

몇시간째 때려박고 있는데 이렇게 접근하는 게 맞나 싶어서 질문 올림

문제를 요약하면,

1 ≤ i ≤ N ≤ 10000에 대해 s_i, k_i, v_i가 주어지고

Σ(s_i*k_i(x_i − v_i')^2) = E로 주어지면

x_i를 변수로 Σ(s_i/x_i)의 최소값이 얼마냐는 문제거든.

그래서 N차원 공간에서 고정된 (찌그러진 N차원구... 처럼 생긴) 입체도형 Σ(s_i*k_i(x_i − v_i')^2) = E가

모든 x_i가 양수인 한 점에서 곡면 Σ(s_i/x_i) = t랑 접할 때를 찾는 게 목표임.

그래서 임의의 한 점에서 시작해서 곡면의 그래디언트를 구하고 경사하강법으로 지지고 볶고...

할 수 있으면 좋을 텐데 엄두가 안 나더라고

그래서 시도한 게 뭐냐면 여러 축 중에서 두 축씩 골라 짝을 짓고 얘네를 한 축으로 차원축소 시켜보는 거임

실제로 2차원에서 고정된 타원이랑 상수항이 고정되지 않은 쌍곡선을 놓고 보면 이분탐색으로 금방 최적점을 찾을 수 있는데

문제는 그 타원의 상수항이 정해지지 않은 상태에서 그걸 일반화시키기가 어려워 보인다는 거임.

그게 무슨 말이냐면

x_1 x_2 좌표평면상에서, 일단 아직 모르는 E'에 대해 s_1*k_1*(x_1 - v_1)^2 + s_2*k_2*(x_2 - v_2)^2 = E'라고 해보자.

쌍곡선 s_1/x_1 + s_2/x_2 = t의 t를 양수의 범위에서 조절하다 보면, (1사분면상의 곡선만 생각하면 됨)

직교하는 점근선의 교점이 직선 x_2 = (s_2/s_1)*x_1 위에서 왔다갔다하고 곡선이 점근선에 얼마나 떨어져있는지도 변함.

계산해보면 또 알 수 있는 사실이 있는데,

쌍곡선이 타원과 접할 때 그 x_1값에서 쌍곡선의 미분계수를 c라고 해보자.

그러면 t값과 관계없이, 미분계수의 값이 c인 곡선 위의 점 역시 원점을 지나는 직선 위에서 왔다갔다함.

(정확히는 x_2 = (s_2 + sqrt(s_1*s_2*(-c)))/(s_1 + sqrt(s_1*s_2/(-c)))*x_1임)

그래서 이 직선과 곡선의 방정식, 그리고 c를 x_1에 대한 함수로 나타낸 방정식을 풀면 되거든

그래서 그 x_1값을 정확히 구하던지 아니면 이분탐색으로 찾아주면 되는데,,, 계산이 너무 더러워져서 값을 정확히 구하는 건 포기함

자 문제는 여기부터인데, 아직 E'의 값이 정해지지 않았다는 거임.

E' == 0이라고 해보자. 그러면 타원은 그냥 점 (v_1, v_2)랑 같으니까 두 "곡선"의 접점이 바로 그 (v_1, v_2)인데,

E' > 0이면 타원이랑 쌍곡선이 접하는 점이 또 다르겠지?

여기에는 선형성이 있나 해서 여러 E'값에 대해 (접점을 (p, q)라고 하자) q/p랑 (q - v_2)/(p - v_1)을 구해봤는데 일정하지 않음.

그러니까 접점의 위치가 E'의 값과 가지는 관계가 명확하다면,

어느 두 개의 축을 차원축소시켰을 때 얘네가 어떻게 작용하게 되는지를 함수의 형태로라도 남겨둘 수 있을 텐데

그러질 못한다면 이걸 N차원까지 일반화시킬 수가 없다는 거임

만약 일반화시키지 못한다면 2차원이 아니라 깡으로 N차원 기하학 노가다를 해야 하거나,

완전히 다른 접근 방식을 택해야 한다는 결론을 얻었음.

피붕이라면 여기서 어떻게 할 것 같음? 전달이 잘 됐는지 모르겠는데

그러니까 나는 여기서 2차원에서 두 곡선의 접점이 가지는 패턴을 수식으로 정확히 구하거나,

아니면 2차원 관점을 버리던지 선택해야 하는 거지.

댓글 0