ICPC I번 에 대해서..

  • dgsquare
    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는 잘 통과하는데, 실재 매치의 결과를 보면 시도는 많은데 성공이 별로 없다는 것이 마음에 걸리네여..
    혹시 제 방식이 틀렸거나, 아니면 고려되지 않은 예외가 있는지 알고 싶습니다.
    아니면 다른 풀이가 있는걸까요? ^^;

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    12년 전
5개의 댓글이 있습니다.
  • soyoja
    soyoja

    대회 후에 저희 팀원이 제안한 방법이 있는데, 누적된 수식에서 중복항들을 제거해서 간단하게 계산하는 방법이었습니다.
    맞는지 아직 코딩으로 검증을 못해봤는데.. 이게 맞는지 내용을 정리해서 조만간 다른분들에게 여쭤보고 싶네요 -_-;;


    12년 전 link
  • wookayin
    wookayin

    실제 대회때 많은 팀들이 precision error 로 말렸습니다[....]


    12년 전 link
  • dgsquare
    dgsquare

    저는 그냥 for루프를 100번정도 돌렸는데, (예전에 오차범위로 하다가 고생한적이있어서.. ) 이러면 WA가 뜰까여?


    12년 전 link
  • wookayin
    wookayin

    (네타방지) 저렇게 하면 될듯[..] 대회때도 저희팀이 I번풀때 종료조건을 상대오차가 아닌 iteration 으로 해서 안 말릴 수 있었어요.ㅇ_ㅇ


    12년 전 link
  • dgsquare
    dgsquare

    감사합니다 :D 좋은 참고 되었어여~!


    12년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.