SRM459,460,461 Div1Medium

SRM459 Div1Med(500)
解法：DP
数え上げのDP典型なのにすっかり忘れていた。

public class NumberPyramids{
	public int count(int a,int b){
		int MOD=1000000009;
		if(a>=21)return 0;
		int C[]=new int[a];
		int now=1;
		for(int i=0;i<a;i++){
			if(i>0)now/=i;
			C[i]=now;
			now*=a-i-1;
		}
		int dp[][]=new int[2][b+1];
		dp[0][0]=1;
		for(int i=0;i<a;i++){
			for(int j=0;j<=b;j++)dp[1-(i&1)][j]=0;
			for(int j=0;j<=b;j++){
				if(j+C[i]<=b){
					dp[1-(i&1)][j+C[i]]=(dp[1-(i&1)][j+C[i]]+dp[i&1][j])%MOD;
					dp[1-(i&1)][j+C[i]]=(dp[1-(i&1)][j+C[i]]+dp[1-(i&1)][j])%MOD;
				}
			}
		}
		return dp[a&1][b];
	}
}

SRM460 Div1Med(500)
解法：DP
確率のDPは何を掛けるか結構迷う。e/nではなく(e-i)/(n-j)を掛ける。

public class TheFansAndMeetingsDivOne{
	public double find(int []a,int[]b,int[]c,int []d,int e){
		int n=a.length;
		double J[][][]=new double[n+1][e+1][e*40+1];
		double B[][][]=new double[n+1][e+1][e*40+1];
		J[0][0][0]=B[0][0][0]=1;
		for(int i=0;i<n;i++){
			for(int j=0;j<=Math.min(e,i);j++){
				for(int k=0;k<=j*40;k++){
					//System.out.print(J[i][j][k]+" ");
					J[i+1][j][k]+=J[i][j][k]*(n-i-e+j)/(n-i);
					B[i+1][j][k]+=B[i][j][k]*(n-i-e+j)/(n-i);
					if(j<e){

						for(int l=a[i];l<=b[i];l++)J[i+1][j+1][k+l]+=J[i][j][k]/(b[i]-a[i]+1)*(e-j)/(n-i);
						for(int l=c[i];l<=d[i];l++)B[i+1][j+1][k+l]+=B[i][j][k]/(d[i]-c[i]+1)*(e-j)/(n-i);
					}

				}
				//System.out.println();
			}
		}
		double ret=0;
		double JJ=0;
		double BB=0;
		for(int i=0;i<=e*40;i++){
		//	System.out.println(J[n][e][i]+" "+B[n][e][i]);
			ret+=J[n][e][i]*B[n][e][i];
			JJ+=J[n][e][i];
			BB+=B[n][e][i];
		}
		//System.out.println(JJ+" "+BB);
		return ret;
	}
}

SRM461 Div1Med(500)
解法：(何個町を作ったか,今いる場所)でDijkstra。遅いDijkstraだと通らないらしいけど、そんなの書く人いるのか(?)
このくらいの問題は解いていて気楽。

#include<algorithm>
#include<queue>
#include<vector>
#include<math.h>
using namespace std;
class BuildingCities{
	public:
	double ijk[2000][50];
	int v[2000][50];
	int findMinimumCities(int a,int b,vector<int>c,vector<int>d){
		int n=c.size();
		if((c[n-1]-c[0])*(c[n-1]-c[0])+(d[n-1]-d[0])*(d[n-1]-d[0])>b*b)return -1;
		priority_queue<pair<double,pair<int,int> > >Q;
		Q.push(make_pair(0,make_pair(0,0)));
		for(int i=0;i<2000;i++)for(int j=0;j<50;j++)ijk[i][j]=99999999;
		ijk[0][0]=0;
		while(Q.size()){
			double cost=-Q.top().first;
			int use=Q.top().second.first;
			int at=Q.top().second.second;
			Q.pop();
			if(v[use][at])continue;
			v[use][at]=1;
			for(int i=0;i<n;i++){
				if(at!=i){
					double dist=sqrt((c[at]-c[i])*(c[at]-c[i])+(d[at]-d[i])*(d[at]-d[i]));
					int P=(int)((dist-0.000001)/a);
					if(dist+ijk[use][at]<b+0.000001&&!v[use+P][i]&&ijk[use+P][i]>ijk[use][at]+dist){
						ijk[use+P][i]=ijk[use][at]+dist;
						Q.push(make_pair(-ijk[use+P][i],make_pair(use+P,i)));
					}
				}
			}
		}
		for(int i=0;i<2000;i++)if(ijk[i][n-1]<b+0.000001)return i;
		return -1;
	}
};