TALKJAIL 정말 헷갈리네요..ㅠㅠ

  • restart
    restart

    2회 전국 대학생 프로그래밍 연합 대회 문제를 하나 남기고ㅠㅠ

    TALKJAIL을 풀고 있는데요..

    처음 description을 읽었을 때는 쉬운 구현문제라 생각하고 접근했는데, 8번 WA세례를 맞았네요ㅠㅠ 몇 번씩 제 가정들을 검토하고 검토해도 답이 안나와서.. 질문하게 되었습니다. ㅠㅠ

    제 해법은 다음과 같습니다.

    (가정) 각 메시지에 해당하는 답은 C_i 또는 0이다.

    왜? 답이 C_i보다 클 순 없다는 건 당연하다.
    답이 C_i보다 작으려면 특정 사람에 대한 정보가 주어져야하는데
    이 정보는 이후 메시지에 등장하는 P_j로만 얻어진다
    그런데 이후에 P_j가 있다면, P_j는 이전 메시지를 모두 읽은 사람이다.
    즉 특정된 사람이 있다면 C_i에 포함되지 않는다.
    결국 C_i보다 답이 작아지는 경우는 없다.
    즉, 답은 C_i 혹은 추측이 불가능할 때 0이 된다.

    (해법)

    1) T_i를 기준으로 소트한다.
    2) 시간 역순으로 순회하면서 1~N을 추가해둔 set을 유지한다.
    이 set은 메시지를 읽지 않았다고 확정할 수 있는 사람들의 집합이다.
    2-1) P_i를 set에서 제거한다.
    2-2) C_i가 set의 크기와 같다면, 해당 메시지의 답은 C_i이다
    2-3) 이외의 경우 답은 0이다.
    3) 각 메시지에 해당하는 답을 출력한다.

    처음엔 답안도 T_i에 소트된 순서대로 출력해서 WA를 받았는데
    이 오류를 고치고 나서도 WA가 나오자 시무룩해졌습니다
    ...

    무엇이 문제일까요ㅠㅠ?


    5년 전
2개의 댓글이 있습니다.
  • iddaga
    iddaga

    헉 ㅋㅋ 오랜만에 접속해보니 제가 낸 문제에 대한 질문이 있었네요..

    꽤 전에 낸 문제라 잘 기억은 안나지만 아마 spoiler 에 적혀있는 가정이 잘못되었을겁니다.

    문제 낼때 예제 설명 조금만 하려고 엄청 간단한 예제를 넣었는데,
    좀 더 큰 예제를 갖고 가정을 검토해보시면 어디서 틀렸는지 아실거에요.


    5년 전 link
  • restart
    restart

    헉 ㅋㅋ출제자의 답변이 올라오다니 영광이에요! 현재 메시지의 문제를 해결할 때, 이전 메시지에 대해서는 얻을 게 없다고 당연하게 여겨버렸는데-_-;; 이전메시지를 안읽은 사람에게 얻을 게 있었군요! 좀 더 신중하게 고민했어야 했습니다ㅠ_ㅠ 답변 감사드립니다, 덕분에 해결했습니다


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