SRM 552 DIV1 Easy - FoxPaintingBalls

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12146&rd=15174

解き方

法則を導き出しても解けるが、少し複雑なことに気づけば
2分探索するのが確実。
N=1のときは必要なボールの数の計算が例外値となるので別に判定するのに注意。

コード

class FoxPaintingBalls {

public: long long theMax(long long R, long long G, long long B, int N) {
if(N==1)return R+G+B;
long long sum=(long long)N*(N+1)/2LL;
long long one=(long long)N*(N+1)/6LL;

if((N%3)!=1){
return min(R,min(G,B))/one;
}

long long low=0,high=max(R,max(G,B));
while(high-low>1){
long long mid=(low+high)/2LL;
if( min(R,min(G,B))/one>=mid && (R+G+B)/sum>=mid)low=mid;
else high=mid;
}
return low;

/*if(N==1)return R+G+B;
long long num=(long long)N*(N+1)/6;

if(N%3==1)return min(min(R,min(G,B))/num,(R+G+B)/((long long)N*(N+1)/2) );
return min(R,min(G,B))/num ;*/
}

};

SRM 548 DIV1 Easy - KingdomAndTrees

問題

http://community.topcoder.com/stat?c=problem_statement&pm=11967&rd=15170

解き方

二分探索を用いればよい。
０が答えのときを含ませるには、lowを-1以下に設定する必要があることに注意。

コード

class KingdomAndTrees {

public:

bool ispossible(vector<int> h,int m){
int n=h.size();

h[0]=max(1,h[0]-m);
FORE(i,1,n){
if(h[i]+m<=h[i-1])return false;
h[i]=max(h[i-1]+1,h[i]-m);
}

return true;
}

int minLevel(vector<int> heights) {

long long low=-1,high=INT_MAX;
while(high-low>1){
int mid=(low+high)/2;
if(ispossible(heights,mid))high=mid;
else low=mid;
}

return high;
}

};

SRM 513 DIV1 Easy - YetAnotherIncredibleMachine

問題

http://community.topcoder.com/stat?c=problem_statement&pm=11502&rd=14538

解き方

各プラットフォームについて有効な場所の総数を、それぞれかけていけばよい。
あるプラットフォームについて有効な場所かどうかの判定は、
一番左側の点と右側の点の間にボールがなければよい。
この判定には二分探索を使うことができる。

コード

class YetAnotherIncredibleMachine {

public: int countWays(vector<int> platformMount, vector<int> platformLength, vector<int> balls) {
int n=platformMount.size();
int MOD=1000000009;

int m=balls.size();
sort(all(balls));

int ret=1;
FORE(i,0,n){
int cur=0;
for(int l=platformMount[i]-platformLength[i];l<=platformMount[i];l++){
int r=l+platformLength[i];
int s=lower_bound(balls.begin(),balls.end(),l)-balls.begin();
if( !(0<=s && s<m) || balls[s]>r )cur++;
}
ret=(1LL*ret*cur)%MOD;
}

return ret;
}

};

SRM 657 DIV1 Easy - ProblemSets x

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13771&rd=16417

・問題Easy,EM,Middle,MH,Hardの数が与えられる。
・ここから問題のセットをできるだけ多く作りたい。
・各問題セットは、Easy,Middle,Hardの問題を各一つ含む必要がある。
・問題EMはEasyもしくはMiddleの代わり、MHはMiddleもしくはHardの代わりに使える。
・このとき、作ることのできる最大の問題セット数を求める。

解き方

まずは法則がないか考えてしまうが、かなり複雑になりそう。

ここで作ることの問題セットがわかっていれば、それを作ることができるかどうかは
すぐに判定することができる。

よって二分探索を用いればよい。

コード

class ProblemSets {

public:

bool ispossible(long long x,long long E, long long EM, long long M, long long MH, long long H){
if(EM<x-E)return false;
if(MH<x-H)return false;

if(E<x)EM-=(x-E);
if(H<x)MH-=(x-H);

return M+EM+MH>=x;
}

long long maxSets(long long E, long long EM, long long M, long long MH, long long H) {
long long low=0,high=LONG_MAX;

while(high-low>1){
long long mid=(low+high)/2;
if(ispossible(mid,E,EM,M,MH,H))low=mid;
else high=mid;
}

return low;
}

};

SRM 230 DIV1 Easy - SortEstimate

問題

http://community.topcoder.com/stat?c=problem_statement&pm=3561&rd=6519

ソートアルゴリズムの計算量を計算したい。
計算量はc*n*log2(n)で表わされ、これをtime以下でかつ最大となるときのｎを求めたい。
cとtimeはあらかじめ与えられる。

解き方

nが一意に決まれば計算量は算出できるので、二分探索が適用できる。

コード

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class SortEstimate {

public: double howMany(int c, int time) {
double low=0.0,high=1e+18;

FORE(i,0,100){
double mid=(low+high)/2.0;
if(c*mid*log(mid)/log(2)<=time)low=mid;
else high=mid;
}

return low;
}

};