ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • codeforces 283 div2 d tennis game
    알고리즘 문제/sort, search 2019. 11. 2. 16:26

    link

    https://codeforces.com/contest/496/problem/D

     

    Problem - D - Codeforces

     

    codeforces.com

     

    흥미로운 문제다

    테니스게임은 set라는 개념이 있다. 하나의 set은 어떤 플레이어가 점수 t를 달성하면 끝나고, 어떤 플레이어가 s개의 set을 이기면 테니스 게임이 끝난다.   

    프로그래밍 문제는 이 부분에 대한 질문이다. 만약 어느 게임의 스코어 정보만 남아있을 때 s와 t를 찾아낼 수 있는지에 대한 문제다.

    다음 예를 보자.

    5
    1 2 1 2 1

    5개의 숫자정보

    아래 숫자 5개는 score를 낸사람의 번호다.

    이 때 s와 t를 추론하는 것이다.

    naive 한 접근법은 모든 s 가능성을 탐색하자. s : from 1 to n.

    만약 5개의 점수가 단 하나의 세트의 승리로만 이루어져있다면 t는 무조건 3이다.

    만약 5개의 점수가 2 개의 세트 승리로 이루어져있다면 t는 존재할 수 없다. t가 1이면 수열이 시작하는 앞 세자리 1 2 1 일때 게임이 이미 끝났다. t가 2라면 수열 시작 앞 세자리 "1 2 1" 일때 1세트이고 그다음 세트 "2 1" 인데 숫자가 부족하다. 

    만약 5개의 점수가 3개의 세트 승리로 이루어져 있다면, "1", "2", "1", "2", "1" 이므로 가능하다.

    만약 5개의 점수가 4개의 세트 승리로 이루어져 있다면, t가 존재하지 않는다.

    만약 5개의 점수가 5개의 세트 승리로 이루어져 있다면, t가 존재하지 않는다.

    naive한 방법도 코드로 구현하기가 까다로울 것이다.

    반드시 점수의 마지막 녀석이 승리 한 것이므로 ( 애초에 마지막 녀석의 점수가 찍힌 것이라면 그전에 게임이 결정되지 않았음을 의미 ) 그녀석을 기준으로 거꾸로 세면 되지 않을까? 

    내 생각엔 n^3 일 것 같은데...n^2 일수도 있겠다. 여차저차 n 제한이 10만이니까 택도 안된다.

     

    그러나 2변수 문제이기 때문에 t를 고정하여 s를 찾는 방법도 있다. 

    t를 1 ~ n 까지 순회하면서, 각 셋트당 t를 먼저 가지는 녀석을 찾아서 세트 승리를 가져가는 것이다. 그래서 가장 많은 세트 승리를 가진 사람과 마지막 점수를 낸 사람 번호가 같은지 체크하여 정당한 변수 s, t 인지 체크한다.

    세트 승리를 가져가는 걸 체크하는데에는 이분탐색( lower_bound) 을 활용하면 n log^2 n 에 구현할 수 있다.

    https://codeforces.com/contest/496/submission/64067361

    '알고리즘 문제 > sort, search' 카테고리의 다른 글

    codeforces 283 div2 d tennis game  (0) 2019.11.02
    CF 1041D Glider  (0) 2018.09.20
    888E : Maximum Subsequence  (0) 2017.11.12
    Codeforces : Ordering Pizza  (0) 2017.10.02

    댓글 0

Designed by Tistory.