UVa Online Judge 10385 - Duathlon

문제 링크입니다:

https://uva.onlinejudge.org/index.phpoption=com_onlinejudge&Itemid=8&page=show_problem&problem=1326

'프로그래밍 대회에서 배우는 알고리즘 문제해결전략' 책에서 삼분법을 소개할 때 예시로 든 문제였습니다.

algospot과 BOJ가 상당히 친절한 알고리즘 사이트라는 것을 깨달았습니다.

매수를 한 사람을 함수로 표현하면 (달린 거리/달리는 평균 속도) + (자전거 탄 거리/자전거 평균 속도) 이므로 달린 거리에 대한 선형함수입니다.

또한, 2등을 한 사람도 똑같이 선형함수이므로 결과인 (매수를 한 사람이 걸린 시간) - (2등을 한 사람이 걸린 시간) 또한 위로 볼록한 함수임을 알 수 있습니다.

삼분 검색은 미분할 수 없는 함수에 사용할 때 유용하므로 해당 문제는 삼분 검색으로 풀었을 때 쉽게 풀 수 있는 문제였습니다.

/*

달리기와 자전거로 총 t 킬로미터를 달리는 철인 2종 경기를 개최한다.

0 ~ (n-1)번까지 모두 n명의 참가자가 등록했으며, 각 참가자의 달리기 속도와 자전거 속도가 주어졌다.

그런데 (n-1)번 참가자가 주최측에 뇌물을 건네며 자신이 승리할 수 있도록 달리기와 자전거 경주의 길이를 조정해달라고 요청했다.

이 참가자가 2등과 가장 큰 차이로 우승하려면 달리기 경주의 길이와 자전거 경주의 길이를 어떻게 정해야할까?

*/

#include <iostream>

#include <vector>

#include <algorithm>

#include <iomanip>

using namespace std;

 

const int MAX = 20;

 

int N; //number of contestors

int track; //트랙길이

double runSpeed[MAX], cycleSpeed[MAX]; //뛰는 속도, 자전거 타는 속도

 

//달리기 구간의 길이가 run일 때, i번 선수가 걸린 시간

double time(int i, double run)

{

        double cycle = track - run;

        return run / runSpeed[i] + cycle / cycleSpeed[i];

}

 

//달리기 구간 길이가 run일 때, others(run)-cheater(run) 반환

//이 때, others(run)은 cheater를 제외한 선수들 중 제일 빠른 사람

double difference(double run)

{

        double cheater = time(N - 1, run);

        double others = time(0, run);

        for (int i = 1; i < (N - 1);i++)

               others = min(others, time(i, run));

        return others - cheater;

}

 

//difference() 함수의 최대치의 위치를 삼분 검색으로 계산

double maxDifference(void)

{

        double low = 0, high = track;

        for (int iter = 0; iter < 100; iter++)

        {

               double a = (2 * low + high) / 3; // 1/3 지점

               double b = (low + 2 * high) / 3; // 2/3 지점

               //오목함수에서 최대점 왼쪽에서는 순증가, 최대점 오른쪽에서는 순감소

               if (difference(a) > difference(b))

                       high = b;

               else

                       low = a;

        }

        return (low + high) / 2;

}

 

int main(void)

{

        while(cin >> track)

        {

               cin >> N;

 

               //속도 입력.

               for (int i = 0; i < N; i++)

                       cin >> runSpeed[i] >> cycleSpeed[i];

 

               double run = maxDifference(); //달린 길이

               double cycle = track - run; //자전거 길이

               double timeDiff = difference(run);

               if (timeDiff >= 0.0)

               {

                       cout << fixed << setprecision(0);

                       cout << "The cheater can win by " << (timeDiff * 3600);

                       cout << fixed << setprecision(2);

                       cout << " seconds with r = " << run << "km and k = " << cycle << "km." << endl;

               }

               else

                       cout << "The cheater cannot win." << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략