TopCoder 2013 Open Round 1 C

250

なんかこう、バランスよく上に上げていけばいいかなって思った。

class TheArray {
    public:
        int find(int n, int d, int first, int last) {
            n -= 2;
            if(first > last) swap(first,last);
            int retval = last;
            int due = 0;
            if(first < last){
                for(due=1;due<=n;due++){
                    first += d;
                    if(first >= last){
                        break;
                    }
                }
            }
            for(int i=0;i<(n-due);i++){
                if(i % 2 == 0){
                    last += d;
                }else{
                    first += d;
                }
            }
            retval = max(retval,max(first,last));
            return retval;
        }
};

500

だいぶ悩んだけれど、よく考えたら二分探索だった。なんかintのままだとあぶなかったらしい。

class TheOlympiadInInformatics {
    public:
        int find(vector <int> sumsi, int ki) {
            ll k = ki;
            vector<ll> sums;
            for(int i=0;i<sumsi.size();i++){
                sums.push_back(sumsi[i]);
            }

            ll lower = 0;
            ll upper = 1000000010;

            for(int i=0;i<200;i++){
                ll med = (lower+upper)/2;
                ll s = 0;
                for(int j=0;j<sums.size();j++){
                    s += sums[j] / (med+1);
                }
                if(s <= k){
                    upper = med;
                }else{
                    lower = med;
                }
            }
            return upper;
        }
};