SRM585 Div1 Easy(250) TrafficCongestion
class TrafficCongestion: def theMinCars(self, treeHeight): T = [1,1] while len(T)<=treeHeight: T += [(T[-1]+2*T[-2])%1000000007] return T[treeHeight]
SRM582 Div2 Easy(250) SemiPerfectSquare
SemiPerfectSquare
#include <string> using namespace std; class SemiPerfectSquare{public: string check( int N ) { for ( int a=1; a<=N; a++ ) for ( int b=a+1; b<=N; b++ ) if ( a*b*b==N ) return "Yes"; return "No"; }};
SRM582 Div1 Easy(250) SpaceWarDiv1
SpaceWarDiv1
疲労度で二分探索。最大の疲労度が与えられたとき、魔法少女が敵を倒せるかどうかは、弱い魔法少女をなるべく弱い敵に貪欲に割り当てて行けば分かる。
#include <vector> #include <algorithm> #include <utility> using namespace std; bool check( vector<int> girl, vector<int> enemy, vector<long long> count, long long f ) { for ( int i=0; i<(int)girl.size(); i++ ) { long long t = f; for ( int j=0; j<(int)enemy.size(); j++ ) if ( girl[i]>=enemy[j] ) { long long n = min(t,count[j]); t -= n; count[j] -= n; } } for ( int i=0; i<(int)enemy.size(); i++ ) if ( count[i]>0 ) return false; return true; } class SpaceWarDiv1{public: long long minimalFatigue( vector <int> magicalGirlStrength, vector <int> enemyStrength, vector<long long> enemyCount ) { sort( magicalGirlStrength.begin(), magicalGirlStrength.end() ); vector<pair<int,long long> > T; for ( int i=0; i<(int)enemyStrength.size(); i++ ) T.push_back(make_pair(enemyStrength[i],enemyCount[i])); sort(T.begin(),T.end()); for ( int i=0; i<(int)enemyStrength.size(); i++ ) enemyStrength[i] = T[i].first, enemyCount[i] = T[i].second; if ( !check(magicalGirlStrength,enemyStrength,enemyCount,1LL<<62) ) return -1; long long ans = (1LL<<62)-1; for ( long long b=1LL<<61; b>0; b>>=1 ) if ( check(magicalGirlStrength,enemyStrength,enemyCount,ans-b) ) ans -= b; return ans<(1LL<<62)-1 ? ans : -1; }};
