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; } };