TCO13 Round1 (Qual Round) 3차까지 가는 졸전끝에 겨우 통과.. 2라운드 진출했다..
아.. 오랜만에 하니깐 잘 안된다.. 요즘 애들 너무 잘해.. ㅠ_ㅠ;;
2라운드는 탈락이 거의 확실시되니.. 블챌이나 신나게 해봐야겠다~~

레이팅은.. 블루로 떨어진지 오래됐음;;






근데 신기하게 이번에 250, 500 둘다 같은 솔루션으로 풀었다..
이거 뭔가.. 출제자 의도가 아닌거같은데;;


Level1 - TheArray

더보기



딱히 좋은 방법이 생각나지 않아서.. 무식하게 binary search

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
#define min(x, y) ((x) > (y) ? (y) : (x))
#define max(x, y) ((x) > (y) ? (x) : (y))
//#define INF 999999999
//#define EPS 1e-14

class TheArray {
public:

int find(int n, int d, int first, int last)
{
    int sol;
    int cnt, cnt2;
    int l, r, m;
    int dif;
    if (n == 2)
        return max(first, last);
    sol = max(first, last);
    l = -1000;
    r = 1000000000;
    while (l <= r) {
        m = (l+r) / 2;
        if (m <= first || m <= last) {
            l = m+1;
            sol = m;
            continue;
        }
        if (m > first + (d * (n-2))) {
            r = m-1;
            continue;
        }

        dif = m - first;
        if (dif % d == 0) {
            cnt = dif / d;
        }
        else {
            cnt = dif / d + 1;
        }
        cnt2 = n-1-cnt;

        if (cnt2 <= 0) {
            r = m-1;
            continue;
        }
        if (abs(m-last) <= d * cnt2) {
            l = m+1;
            sol = m;
            continue;
        }
        else {
            r = m-1;
        }
    }
    return max(first, max(last, sol));
}





Level2 - TheOlympiadInInformatics

더보기


문제 이해를 돕기 위해..
sum = 10 일 경우 내가 10을 먹으면 내가 무조건 1등이지만,
내가 4 일 경우, 다른 방에는 5, 5 가 되서 내가 3등이 될 수 있다..
내가 2 일 경우 ,다른 방에는 3, 3, 3 이 되어 내가 4등이 될 수 있다..

어쨋든 이것도 간단히 binary search


#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
#define min(x, y) ((x) > (y) ? (y) : (x))
#define max(x, y) ((x) > (y) ? (x) : (y))
//#define INF 999999999
//#define EPS 1e-14

class TheOlympiadInInformatics {
public:

int find(vector <int> sums, int k)
{
    int n;
    int l, r, m;
    int cnt, sol;
    int i;
    n = sums.size();
    sol = 1000000000;
    l = 0;
    r = 1000000000;
    while (l <= r) {
        m = (l+r)/2;
        cnt = 0;
        for (i = 0; i < n; i++) {
            cnt += sums[i] / (m+1);
            if (cnt > k)
                break;
        }
        if (i == n && cnt <= k) {
            sol = m;
            r = m-1; 
        }
        else {
            l = m+1;
        }
    }
    return sol;
}

};




'Problem Solving > TopCoder logs' 카테고리의 다른 글

TCO13 Round 1C 생명연장 매치  (0) 2013.03.10
TCO12 R1A - 606등 -_-;;  (0) 2012.04.01
SRM 529  (0) 2012.01.15
SRM 521  (0) 2011.10.24
SRM 511  (0) 2011.07.04
TCO11 R1 - 탈락  (0) 2011.06.23
SRM 509 !!  (0) 2011.06.09
SRM 507 - 나이스!  (0) 2011.05.30
TCO11 Qual2  (0) 2011.05.20
TCO11 Qual1  (2) 2011.05.15
SRM 504 - unrated event  (0) 2011.04.27

Leave a Comment


to Top