SRM Div1 medium 埋め
Div1medをひたすら埋めるゲーム
昨日と今日やった分を列挙します
208 235.27pt
書かれている通りに面倒なシミュレーションするだけ。悪問
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; typedef long long ll; ll nowrand=1; class QueenInterference { public: int getrand(int mod) { ll ret=nowrand; nowrand*=16807; nowrand%=2147483647; return ret%mod; } bool iscross(int a,int b,int c,int d) { return ((a==c)||(b==d)||(a+b==c+d)||(a-b==c-d)); } int numSteps(int num) { int ret=0; int now[100]; for(int i=0;i<num;i++) { now[i]=getrand(num); } for(;;) { vector<int>vec; for(int i=0;i<num;i++) { for(int j=0;j<num;j++) { if(i!=j) { if(iscross(i,now[i],j,now[j])) { vec.push_back(i); break; } } } } if(vec.empty()) { return ret; } int col=vec[getrand(int(vec.size()))]; int dat[100]; fill(dat,dat+100,0); for(int i=0;i<num;i++) { for(int j=0;j<num;j++) { if(j!=col) { if(iscross(col,i,j,now[j])) { dat[i]++; } } } } vector<int>pos; int mini=100000; for(int i=0;i<num;i++) { if(mini==dat[i]) { pos.push_back(i); } if(mini>dat[i]) { pos.clear(); pos.push_back(i); mini=dat[i]; } } if(pos.size()==1) { now[col]=pos[0]; } else { now[col]=pos[getrand(int(pos.size()))]; } ret++; } } };
339 297.56pt
勝った時にはお金が1増えてるのでそれでDPする
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; class TestBettingStrategy { public: double dp[51][1001]; double winProbability(int st,int go,int kai,int pr) { double pro=double(pr)/100.0; for(int i=0;i<51;i++) { for(int j=0;j<1001;j++) { dp[i][j]=0; } } dp[0][st]=1.0; for(int i=1;i<=kai;i++) { for(int j=max(0,i-15);j<i;j++) { for(int k=0;k<1000;k++) { if(k>=(1<<(i-j))-1) { double tim=dp[j][k]; for(int l=0;l<i-j-1;l++) { tim*=(1.0-pro); } tim*=pro; dp[i][k+1]+=tim; } } } } double ans=0; for(int i=1;i<=kai;i++) { ans+=dp[i][go]; } return ans; } };
459 257.88pt
良問。1000000マス以下とか書いてあるけど21マス以上の時はどう頑張ってもtopが小さすぎるので枝狩り。あとは個数制限なしナップザックやっておしまい
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; typedef long long ll; ll mod=1000000009; class NumberPyramids { public: ll com[30][30]; ll dp[1000001]; ll newdp[1000001]; void calccom() { com[0][0]=1; for(int i=1;i<=27;i++) { com[i][0]=1; for(int j=1;j<=i;j++) { com[i][j]=com[i-1][j-1]+com[i-1][j]; com[i][j]%=mod; } } } int count(int num,int gen) { if(num>=30) { return 0; } gen-=(1<<(num-1)); if(gen<0) { return 0; } calccom(); vector<int>vec; for(int i=0;i<=num-1;i++) { vec.push_back(com[num-1][i]); } fill(dp,dp+gen+1,0); fill(newdp,newdp+gen+1,0); dp[0]=1; for(int i=0;i<num;i++) { for(int j=0;j<=gen;j++) { if(j-vec[i]>=0) { newdp[j]+=newdp[j-vec[i]]; } newdp[j]+=dp[j]; newdp[j]%=mod; } for(int j=0;j<=gen;j++) { dp[j]=newdp[j]; newdp[j]=0; } } return int(dp[gen]); } };
460 150.00pt
ごく普通のn^5の確率DPするだけ。ちょっと自明な枝狩りをしないとTLEするのつらいので制約ゆるくしてくだされ〜
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; double dpa[41][42][1601]; double dpb[41][42][1601]; class TheFansAndMeetingsDivOne { public: double find(vector<int>mina,vector<int>maxa,vector<int>minb,vector<int>maxb,int kai) { dpa[0][0][0]=dpb[0][0][0]=1; for(int i=0;i<mina.size();i++) { for(int j=0;j<=kai;j++) { for(int k=0;k<=1600;k++) { dpa[i+1][j][k]+=dpa[i][j][k]; dpb[i+1][j][k]+=dpb[i][j][k]; for(int l=mina[i];l<=maxa[i];l++) { if(k+l<=1600) { dpa[i+1][j+1][k+l]+=dpa[i][j][k]*(1.0/double(maxa[i]-mina[i]+1)); } else { break; } } for(int l=minb[i];l<=maxb[i];l++) { if(k+l<=1600) { dpb[i+1][j+1][k+l]+=dpb[i][j][k]*(1.0/double(maxb[i]-minb[i]+1)); } else { break; } } } } } double ans=0; for(int i=0;i<=1600;i++) { ans+=dpa[int(mina.size())][kai][i]*dpb[int(mina.size())][kai][i]; } for(int i=1;i<=kai;i++) { ans*=i*i; ans/=(mina.size()-i+1)*(mina.size()-i+1); } return ans; } };
461 150.00pt
普通にdijkstra.定数倍が厳しくて枝刈りまくって19回提出したらやっと通った。制約ゆるくしてくだされ〜
#include<stdio.h> #include<vector> #include<algorithm> #include<queue> #include<math.h> using namespace std; typedef pair<double,pair<int,int> >pdii; class BuildingCities { public: double dist[50][50]; int cost[50][50]; double flag[50][8001]; bool used[50][8001]; int findMinimumCities(int gen,int mok,vector<int>vx,vector<int>vy) { for(int i=0;i<vx.size();i++) { for(int j=0;j<vy.size();j++) { dist[i][j]=sqrt((vx[i]-vx[j])*(vx[i]-vx[j])+(vy[i]-vy[j])*(vy[i]-vy[j])); cost[i][j]=int(floor(dist[i][j]/double(gen)-0.00000001)); if(i==j) { cost[i][j]=0; } printf("%d ",cost[i][j]); } printf("\n"); } if(dist[0][vx.size()-1]>mok) { return -1; } priority_queue<pdii>que; que.push(make_pair(0.0,make_pair(0,0))); for(int i=0;i<vx.size();i++) { for(int j=0;j<2001;j++) { flag[i][j]=1000000000; used[i][j]=false; } for(int j=2001;j<8001;j++) { flag[i][j]=0; used[i][j]=true; } } int ans=1000000000; for(;;) { if(que.empty()) { break; } pdii zan=que.top(); que.pop(); if(flag[zan.second.first][zan.second.second]<(-zan.first)) { continue; } if(used[zan.second.first][zan.second.second]) { continue; } used[zan.second.first][zan.second.second]=true; if(-zan.first>mok) { break; } if(ans<=zan.second.second) { continue; } if(vx.size()-1==zan.second.first) { if(ans>zan.second.second&&mok>=(-zan.first)) { ans=zan.second.second; } } for(int i=0;i<vx.size();i++) { int a=zan.second.second+cost[zan.second.first][i]; if(i!=zan.second.first&&(flag[i][a]>(-zan.first+dist[zan.second.first][i]))&&ans>a&&mok>=a) { que.push(make_pair(zan.first-dist[zan.second.first][i],make_pair(i,a))); flag[i][a]=-zan.first+dist[zan.second.first][i]; } } } return ans; } };
462 135.00pt
確率の問題ってなにをやってよくてなにをしていけないかわからない...
それをしていいことに気付けばやるだけ
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; class CandyBox { public: vector<double>expectedScore(int ko,vector<int>vec,int kai) { vector<double>ret; double sum=0; if(vec.size()==1) { ret.push_back(vec[0]); return ret; } for(int i=0;i<vec.size();i++) { sum+=vec[i]; } for(int i=0;i<vec.size();i++) { double exp=(vec[i]); double oth=(sum-vec[i]); for(int j=0;j<kai;j++) { double kak=1.0-double(ko*(ko-1)+(ko*(vec.size()-1))*(ko*(vec.size()-1)-1))/double(ko*vec.size()*(ko*vec.size()-1)); exp=exp*(1.0-kak)+((oth/(vec.size()-1)+exp*(ko-1))/ko*kak); oth=sum-exp; } ret.push_back(exp); } return ret; } };
463 294.50pt
mathmathした良問。1.5<=pなので2p*q>=2p+qで、3つ以上足し合わせるのは意味がない。
よって2つくみあわせるのとそのままのをかけまくるのが答え。
2つ組み合わせるのの組の個数を決めると上下から貪欲にとっていくのが最適なので全部動かして調べる。
JOI本選4と同じにおいを感じた。
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; class Nisoku { public: double theMax(vector<double>vec) { sort(vec.begin(),vec.end()); double maxi=1; for(int i=0;i<=vec.size()/2;i++) { double nowans=1; for(int j=0;j<i;j++) { nowans*=(vec[j]+vec[i*2-1-j]); } for(int j=i*2;j<vec.size();j++) { nowans*=vec[j]; } maxi=max(maxi,nowans); } return maxi; } };
464 255.48pt
良問。でもちょっと実装量が多い。まあライブラリ持っている設定なのかも。
答えで二分探索して2-SATを解く。
#include<stdio.h> #include<vector> #include<algorithm> #include<math.h> #include<stdlib.h> using namespace std; class ColorfulDecoration { public: bool flag[100]; vector<int>topo; int ban[100]; vector<int>pat[100]; vector<int>rpat[100]; void dfs(int node) { if(flag[node]) { return; } flag[node]=true; for(int i=0;i<pat[node].size();i++) { dfs(pat[node][i]); } topo.push_back(node); } void rdfs(int node,int b) { if(flag[node]) { return; } flag[node]=true; ban[node]=b; for(int i=0;i<rpat[node].size();i++) { rdfs(rpat[node][i],b); } } void scc(int num) { topo.clear(); fill(flag,flag+100,false); for(int i=0;i<num;i++) { if(!flag[i]) { dfs(i); } } fill(flag,flag+100,false); int now=0; for(int j=topo.size()-1;j>=0;j--) { if(!flag[topo[j]]) { rdfs(topo[j],now); now++; } } } int getMaximum(vector<int>vx1,vector<int>vy1,vector<int>vx2,vector<int>vy2) { int beg=0,end=1000000000; for(;;) { int med=(beg+end)/2+1; for(int i=0;i<100;i++) { ban[i]=-1; pat[i].clear(); rpat[i].clear(); } for(int i=0;i<vx1.size();i++) { for(int j=0;j<vx1.size();j++) { if(i==j) { continue; } if(max(abs(vx1[i]-vx1[j]),abs(vy1[i]-vy1[j]))<med) { pat[i*2].push_back(j*2+1); pat[j*2].push_back(i*2+1); rpat[j*2+1].push_back(i*2); rpat[i*2+1].push_back(j*2); printf("%d %d\n",i*2,j*2+1); printf("%d %d\n",j*2,i*2+1); } if(max(abs(vx1[i]-vx2[j]),abs(vy1[i]-vy2[j]))<med) { pat[i*2].push_back(j*2); pat[j*2+1].push_back(i*2+1); rpat[j*2].push_back(i*2); rpat[i*2+1].push_back(j*2+1); printf("%d %d\n",i*2,j*2); printf("%d %d\n",j*2+1,i*2+1); } if(max(abs(vx2[i]-vx1[j]),abs(vy2[i]-vy1[j]))<med) { pat[i*2+1].push_back(j*2+1); pat[j*2].push_back(i*2); rpat[j*2+1].push_back(i*2+1); rpat[i*2].push_back(j*2); printf("%d %d\n",i*2+1,j*2+1); printf("%d %d\n",j*2,i*2); } if(max(abs(vx2[i]-vx2[j]),abs(vy2[i]-vy2[j]))<med) { pat[i*2+1].push_back(j*2); pat[j*2+1].push_back(i*2); rpat[j*2].push_back(i*2+1); rpat[i*2].push_back(j*2+1); printf("%d %d\n",i*2+1,j*2); printf("%d %d\n",j*2+1,i*2); } } } scc(int(vx1.size())*2); bool flag=true; for(int i=0;i<vx1.size();i++) { printf(" %d %d\n",ban[i*2],ban[i*2+1]); if(ban[i*2]==ban[i*2+1]) { flag=false; } } if(flag) { beg=med; } else { end=med-1; } if(beg==end) { return beg; } } } };
466 399.32pt
さすがにやるだけ
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; typedef long long ll; ll dp[101][6]; class LotteryPyaterochka { public: double chanceToWin(int num) { ll ans=1; for(int i=0;i<5;i++) { ans*=(num*5-i); } ans/=120; dp[0][0]=1; for(int i=0;i<num;i++) { for(int j=0;j<=5;j++) { dp[i+1][j]+=dp[i][j]; } for(int j=1;j<=5;j++) { dp[i+1][j]+=dp[i][j-1]*5; } for(int j=2;j<=5;j++) { dp[i+1][j]+=dp[i][j-2]*10; } for(int j=0;j<=5;j++) { printf("%lld ",dp[i+1][j]); } printf("\n"); } return 1.0-double(dp[num][5])/double(ans); } };
467 442.68pt
なんでこんなやるだけがmedに出るんだ(憤怒)
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; typedef long long ll; ll mod=1000000007; class SuperSum { public: ll po(ll a,ll b) { vector<int>vec; for(;;) { if(b==0) { break; } vec.push_back(b%2); b/=2; } reverse(vec.begin(),vec.end()); ll ret=1; for(int i=0;i<vec.size();i++) { ret*=ret; ret%=mod; if(vec[i]) { ret*=a; ret%=mod; } } return ret; } ll inv(ll a) { return po(a,mod-2); } int calculate(int a,int b) { b=a+b; a++; ll now=1; printf("%d %d\n",a,b); for(ll i=b;i>b-a;i--) { now*=i; now%=mod; } for(ll i=1;i<=a;i++) { now*=inv(i); now%=mod; } return int(now); } };
468 264.43pt
DPやるだけ
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; typedef long long ll; ll dp[41][2]; ll newdp[41][2]; class RoadOrFlightHard { public: vector<ll>getarray(ll beg,ll tim,ll add,ll mod,int num) { vector<ll>ret; ll now=beg; for(int i=0;i<num;i++) { now%=mod; ret.push_back(now); now=(now*tim+add)%mod; } return ret; } ll minTime(int num,int bega,int tima,int adda,int moda,int begb,int timb,int addb,int modb,int gen) { vector<ll>road=getarray(bega,tima,adda,moda,num); vector<ll>flit=getarray(begb,timb,addb,modb,num); for(int i=0;i<=gen;i++) { dp[i][0]=dp[i][1]=newdp[i][0]=newdp[i][1]=1000000000000000000LL; } dp[0][0]=0; for(int i=0;i<num;i++) { for(int j=0;j<=gen;j++) { newdp[j][0]=min(dp[j][0]+road[i],dp[j][1]+road[i]); newdp[j][1]=dp[j][1]+flit[i]; } for(int j=1;j<=gen;j++) { newdp[j][1]=min(newdp[j][1],dp[j-1][0]+flit[i]); } for(int j=0;j<=gen;j++) { dp[j][0]=newdp[j][0]; dp[j][1]=newdp[j][1]; newdp[j][0]=newdp[j][1]=1000000000000000000LL; } } ll mini=1000000000000000000LL; for(int i=0;i<=gen;i++) { mini=min(mini,dp[i][0]); mini=min(mini,dp[i][1]); } return mini; } };
475
n<=50だと50回半分にしても平気なのか...
2べきでのmodを持っておいて適当に割る
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; typedef long long ll; ll mod=1000000009; ll gm=1LL<<52LL; class RabbitIncreasing { public: int getNumber(vector<int>a,int b) { sort(a.begin(),a.end()); int pt=0; ll nowb=0,nows=1; ll gb=0,gs=1; if(a[0]==1) { return 0; } for(int i=2;i<=b;i++) { ll t=nowb; nowb=(nowb+nows)%mod; nows=t; t=gb; gb=(gb+gs)%gm; gs=t; if(pt==a.size()) { continue; } if(a[pt]==i) { if((gb%2)^(gs%2)) { gb=(gb+gm-1)%gm; nowb=(nowb+mod-1)%mod; } gb=(gb+gm-(gb+gs)/2)%gm; if((nowb+nows)%2) { nowb=(nowb+mod-((nowb+nows+mod)/2)%mod)%mod; } else { nowb=(nowb+mod-((nowb+nows)/2)%mod)%mod; } pt++; } } return (nowb+nows)%mod; } };
解法が分かったけどフローだったのであきらめたものが数問、わからなかったのは2~3問くらいなのでmed実は簡単に安定するのではと思い始めた
