読者です 読者をやめる 読者になる 読者になる

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