tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

SRM 628

TopCoder

大負け直後のSRM。また負け。

250:
やるだけ。4位。
http://i.gyazo.com/99affafec2972d5621a5be892401fae8.png

// I like wolves!!
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <string.h>
#include <complex>
using namespace std;

class DivisorsPower {
	public:
	long long findArgument(long long n) {
		double EPS=1e-9;
		long long ret=-1;
		for(int i=2;i<63;i++){
			long long val=(long long)(pow(n,1.0/i)+EPS);
			long long now=1;
			for(int j=0;j<i;j++){
				now*=val;
			}
			if(n==now){
				int tmp=0;
				for(int j=1;(long long)j*j<=val;j++){
					if((long long)j*j==val)tmp++;
					else if(val%j==0)tmp+=2;
				}
				if(i==tmp){
					ret=val;
				}
			}
		}
		return ret;
	}
};

//Powered by [KawigiEdit] 2.0!

500:
skyさんが爆速で提出していたのでDPだと思って嵌った
かなり時間が経ってStandings見たらみんな高得点だったのでどうせGreedyだとおもったらGreedyだった。
Greedyは最も(puke) (handshake)
スピードがﾄﾞﾎﾞﾎﾞｯ

// I like wolves!!
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <string.h>
#include <complex>
using namespace std;

class CircuitsConstruction {
	public:
	int n;
	int m;
	string str;
	int c[2100];
	int dp[5100][2100];
	int L[5100];
	int R[5100];
	void dfs(int a){
		if(str[a]=='X'){
			L[a]=a;
			R[a]=a;
		//	printf("%d: %d %d\n",a,L[a],R[a]);
			return;
		}
		dfs(a+1);
		L[a]=R[a+1];
		dfs(L[a]+1);
		R[a]=R[L[a]+1];
	//	printf("%d: %d %d\n",a,L[a],R[a]);
	}/*
	int solve(int a,int l,int r){
		if(~dp[a][l])return dp[a][l];
		if(l==r)return dp[a][l]=c[l];
		printf("%d %d %d %d %d\n",a,l,r,L[a],R[a]);
		int sz=r-l+1;
		int lsz=(L[a]-a+1)/2;
		int rsz=sz-lsz;
		int ret=999999999;
		if(str[a]=='A')ret=max(solve(a+1,l,l+lsz-1)+solve(L[a]+1,l+lsz,r),solve(a+1,l+rsz,r)+solve(L[a]+1,l,l+rsz-1));
		else ret=max(max(solve(a+1,l,l+lsz-1),solve(L[a]+1,l+lsz,r)),max(solve(a+1,l+rsz,r),solve(L[a]+1,l,l+rsz-1)));
		return dp[a][l]=ret;
	}*/
	int solve(int a){
		if(str[a]=='X')return 1;
		if(str[a]=='A')return solve(a+1)+solve(L[a]+1);
		return max(solve(a+1),solve(L[a]+1));
	}
	int maximizeResistance(string a, vector <int> b) {
		str=a;
		n=b.size();
		m=a.size();
		for(int i=0;i<=m;i++){
			for(int j=0;j<=n;j++){
				dp[i][j]=-1;
			}
		}
		dfs(0);
		//for(int i=0;i<m;i++)printf("%d %d\n",L[i],R[i]);
		for(int i=0;i<n;i++)c[i]=b[i];
		std::sort(c,c+n);
		int num=solve(0);
		int ret=0;
		for(int i=0;i<num;i++)ret+=c[n-1-i];
		return ret;
	}
};

//Powered by [KawigiEdit] 2.0!

1000:
終了後に解いた。
まず、Yが小さい順にソートする。
dp[i][j]: i番目までみて余分にもらえた★の数がj個となる確率
とちょっと変形して、もらえすぎをm-nまでにしたり、途中で足りなくなるのを無視するべく、「もう残りは全部使わないと足りない」状態からは遷移しないようにする。

各地点に対して、「ここからはもう全部★2つもらっていかないと足りない確率」を上の表から求めて、期待値は1/(x[1]+y[1])+...+1/(y[i])+...+1/(y[n])のようになる。(途中までは1個以上もらえれば先にすすみ、途中からは2個もらえたら先にすすんだときの期待値)
掛け算して足して終わり。

// I like wolves!!
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <string.h>
#include <complex>
using namespace std;

class DoraemonPuzzleGame {
	public:
	pair<int,int> z[3000];
	double dp[3000][3000];
	
	double solve(vector <int> X, vector <int> Y, int m) {
		int n=X.size();
		for(int i=0;i<n;i++)z[i]=make_pair(Y[i],X[i]);
		std::sort(z,z+n);
		for(int i=0;i<3000;i++)for(int j=0;j<3000;j++)dp[i][j]=0;
		dp[0][0]=1;
		for(int i=0;i<n;i++){
			for(int j=0;j<=i;j++){
		//		printf("%d %d: %f\n",i,j,dp[i][j]);
				if(j+n-i<=m-n)continue;
				dp[i+1][min(j+1,m-n)]+=dp[i][j]*z[i].first/(z[i].first+z[i].second);
				dp[i+1][j]+=dp[i][j]*z[i].second/(z[i].first+z[i].second);
			}
		}
		double ret=0;
		
		for(int i=0;i<=m-n;i++){
			int t=n-(m-n-i);
			double prob=0;
			double ex=0;
			for(int j=0;j<n;j++){
				if(j<t)ex+=1000.0/(z[j].first+z[j].second);
				else ex+=1000.0/(z[j].first);
			}
			if(t==0)prob=1;
			else if(t==n){
				prob=dp[n][m-n];
			}else prob=dp[t][i];
		//	printf("%d: %f %f\n",i,ex,prob);
			ret+=ex*prob;
		}
		return ret;
	}
};

//Powered by [KawigiEdit] 2.0!

Score:
ほぼ0

Rating:
0

Div1Hardがそれなりの時間で解けたので、Div1Hardをやったほうが良かったのかもしれない。というか練習効果は出ていてただ苦手なだけだったと思いたいですね。