SRM628
SRM[200π]
Easy:DivisorsPower
問題概要:
2以上1e18以下の整数xが与えられるので、nの(nの正の約数の個数)乗=xになるnを返せ ない場合は-1
解法:
i乗根とってやるだけ…と思っていたら落ちた
原因はdoubleがlong long intを表現しきれないことで、doubleは64bit中,符号1,指数11,仮数52bitが割り当てられていて、まあ2^52<2^63なので、ダメでした。
Sampleに入れておいて欲しかったなあ(でもint,long longの上限と同じくらいの知識だから流石に知らないとやばい)
コード:
#include <iostream> #include <vector> #include <cmath> #define rep(i,n) for(int i=0;i<n;i++) #define rep1(i,n) for(int i=1;i<=n;i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second typedef long long ll; using namespace std; const ll ccc=1000000; bool prime[ccc+1]; vector<ll> pr; void makeprime(){ ll iii,jjj; for(iii=0;iii<=ccc;iii++){ prime[iii]=true; } prime[0]=false; prime[1]=false; for(iii=2;iii*iii<=ccc;iii++){ if(prime[iii]){ for(jjj=2*iii;jjj<=ccc;jjj+=iii){ prime[jjj]=false; } } } for(iii=2;iii<=ccc;iii++) if(prime[iii]) pr.push_back(iii); } double eps=1e-9; int kosu(ll x){ int ret=1; rep(i,pr.size()){ int cnt=1; while(x%pr[i]==0){ x/=pr[i]; cnt++; } ret*=cnt; } if(x>1) ret*=2; return ret; } class DivisorsPower{ public: long long findArgument(long long n){ makeprime(); for(int d=2;d<=61;d++){ ll x=(eps+pow(n,1.0/d)); ll pow=1; rep(i,d) pow*=x; //ここをpow=(long long)(eps+pow(x,d))とすると死 if(pow==n){ if(kosu(x)==d) return x; } } return -1; } };
Med:CircuitsConstruction
問題概要:
サーキットというものが定義されている。
1.'X'はサーキットである
2.string Y,Zがサーキットの時、'A'+Y+Zと'B'+Y+Zはサーキット
3.以上のもののみがサーキット
サーキットYの'X'たちにそれぞれ値を代入した時のサーキットの値fは、
f('X')=このXに代入された値
f('A'+Y+Z)=f(Y)+f(Z)
f('B'+Y+Z)=max(f(Y),f(Z))
で定義される。
あるサーキットcircuit(validで、含まれるXの個数nは2000以下)が与えられる。また、1以上100000以下の整数n個からなる集合conductorsが与えられるので、代入する値を好きに割り当てて値を最大化せよ
ex.circuit="AXBXX",conductors={8,2,3}の時、8+max(2+3)や2+max(3,8)などの6通りが考えられる。最大は11
解法:
でかい値を足したいが,maxとるなら片方はどうでもいい→
サーキットの値はconductors[i]のΣなので、結局足す数の個数を最大化して、そいつらにconductorsのでかい値から突っ込めば良い.最大何個足せるかgは再帰的にわかる(g('X')=1,g('A'+Y+Z)=g(Y)+g(Z),g('B'+Y+Z)=max(g(Y),g(Z)))
あとは軽い構文解析をかけば良い
コード:
#include <iostream> #include <vector> #include <algorithm> #define rep(i,n) for(int i=0;i<n;i++) #define rep1(i,n) for(int i=1;i<=n;i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second using namespace std; typedef string::const_iterator State; int circuit(State& be){ if(*be=='A'){ be++; int x=circuit(be); int y=circuit(be); return x+y; }else if(*be=='B'){ be++; int x=circuit(be); int y=circuit(be); return max(x,y); }else{ be++; return 1; } } class CircuitsConstruction{ public: int maximizeResistance(string s, vector <int> c){ int ans=0; sort(all(c)); State be=s.begin(); int n=circuit(be); rep(i,n) ans+=c[c.size()-1-i]; return ans; } };