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