안녕하세요. ICPC가 끝난지 10여일이 지났지만, 혼자 문제풀면서 놀고있는 1인입니다. ^^;
어케어케 H번까지는 지나서 I번을 보고 있는데요. ICPC에 대한 예기가 거의없어 뜬금없이 질문을 올립니다.
나름 한참을 생각하다 풀이를 생각했는데, 이 풀이가 맞는지 몰라서여 ㅠ.ㅠ 제 풀이는 다음과 같습니다.
(아직 안푸신분들을 위해 가립니다. )
1. 각 좌표와 이동 벡터를 S0에 대하여 정리한후,
2. 이것들의 거리(D)를 시간 t에 대하여 2차 방정식으로 구성한뒤,
3. 시간 t에 대하여 binary search를 돌립니다.
4. binary search를 돌리면서 각 탐색시간마다 가장 거리가 먼 방정식(Di)을 찾아서, 이것을 미분값을 구한뒤
5. 미분값이 0.0보다 작으면 우측을 탐색, 크거나 같으면 왼쪽을 탐색하는 식으로 구성하였습니다.(여러시간이나오면 가장 빠른시간을 구해야하므로..)
최장 거리 역시 2차방정식들의 교집합이기 때문에 binary search로 탐색 가능하다는 생각을 해서 이런식으로 짯구요.
Test는 잘 통과하는데, 실재 매치의 결과를 보면 시도는 많은데 성공이 별로 없다는 것이 마음에 걸리네여..
혹시 제 방식이 틀렸거나, 아니면 고려되지 않은 예외가 있는지 알고 싶습니다.
아니면 다른 풀이가 있는걸까요? ^^;
dgsquare
안녕하세요. ICPC가 끝난지 10여일이 지났지만, 혼자 문제풀면서 놀고있는 1인입니다. ^^;
어케어케 H번까지는 지나서 I번을 보고 있는데요. ICPC에 대한 예기가 거의없어 뜬금없이 질문을 올립니다.
나름 한참을 생각하다 풀이를 생각했는데, 이 풀이가 맞는지 몰라서여 ㅠ.ㅠ 제 풀이는 다음과 같습니다.
(아직 안푸신분들을 위해 가립니다. )
1. 각 좌표와 이동 벡터를 S0에 대하여 정리한후,
2. 이것들의 거리(D)를 시간 t에 대하여 2차 방정식으로 구성한뒤,
3. 시간 t에 대하여 binary search를 돌립니다.
4. binary search를 돌리면서 각 탐색시간마다 가장 거리가 먼 방정식(Di)을 찾아서, 이것을 미분값을 구한뒤
5. 미분값이 0.0보다 작으면 우측을 탐색, 크거나 같으면 왼쪽을 탐색하는 식으로 구성하였습니다.(여러시간이나오면 가장 빠른시간을 구해야하므로..)
최장 거리 역시 2차방정식들의 교집합이기 때문에 binary search로 탐색 가능하다는 생각을 해서 이런식으로 짯구요.
Test는 잘 통과하는데, 실재 매치의 결과를 보면 시도는 많은데 성공이 별로 없다는 것이 마음에 걸리네여..
혹시 제 방식이 틀렸거나, 아니면 고려되지 않은 예외가 있는지 알고 싶습니다.
아니면 다른 풀이가 있는걸까요? ^^;
15년 전