問題
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;
}
};
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;
}
};
Share this
Related Posts
SRM 230 DIV1 Easy - SortEstimate
問題
http://community.topcoder.com/stat?c=problem_statement&pm=3561&rd=6519
ソートアルゴリズムの計算量を計算したい。
計算量はc*n*log- SRM 657 DIV1 Easy - ProblemSets x
問題
http://community.topcoder.com/stat?c=problem_statement&pm=13771&rd=16417
・問題Easy,EM,Middle,MH,Hardの数が与え
- SRM 258 DIV1 Easy - AutoLoan
問題
http://community.topcoder.com/stat?c=problem_statement&pm=3970&rd=7993
・車をローンで購入する。
・車の費用はあらかじめわかっており、デ
- SRM 548 DIV1 Easy - KingdomAndTrees
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11967&rd=15170
解き方
二分探索を用いればよい。
０が答えのときを含