A:
おおっとりあえずメモ化探索しよ
#include<stdio.h> #include<algorithm> #include<map> #include<vector> using namespace std; map<long long,int> dp; vector<long long>hb; long long calc(long long a){ if(dp.count(a))return dp[a]; long long best=a; for(int i=0;i<hb.size();i++){ if(hb[i]>a)continue; long long cost=a%hb[i]; if(cost>=best)continue; best=min(best,cost+calc(a/hb[i])); } return dp[a]=best; } int main(){ long long a;scanf("%lld",&a); long long cur=0; for(int i=0;i<18;i++){ cur*=10; if(i%2)cur+=2; else cur+=5; hb.push_back(cur); } cur=0; for(int i=0;i<18;i++){ cur*=10; if(i%2)cur+=5; else cur+=2; hb.push_back(cur); } std::sort(hb.begin(),hb.end()); printf("%lld\n",calc(a)); }
B:
壊れたドアと同じなのに変なこと考えてて駄目
#include<stdio.h> #include<algorithm> #include<vector> using namespace std; int b[1100]; int ABS(int a){ return max(a,-a); } long long dp[1100][1100][2]; long long mod=1000000007; long long inf=mod*mod; long long calc(int a,int b,int c){ if(dp[a][b][c]>=0)return dp[a][b][c]; if(a==b)return inf; } int main(){ int a;scanf("%d",&a); for(int i=0;i<a;i++)scanf("%d",b+i); int pp=0; for(int i=0;i<a;i++)if(b[i]>0){pp=i;break;} if(pp==0){ printf("1.00000000000\n");return 0; } double left=1; double right=2000000000.0; for(int i=0;i<100;i++){ double M=(left+right)/2; for(int j=0;j<a;j++)for(int k=0;k<a;k++)for(int l=0;l<2;l++)dp[j][k][l]=inf; dp[pp][pp][0]=dp[pp][pp][1]=b[pp]; dp[pp-1][pp-1][0]=dp[pp-1][pp-1][1]=-b[pp-1]; for(int j=0;j<a-1;j++){ for(int k=0;j+k<a;k++){ for(int l=0;l<2;l++){ int r=j+k; if(dp[k][r][l]==inf)continue; if(r<a-1){ long long toc=dp[k][r][l]; if(l==0)toc+=b[r+1]-b[k]; else toc+=b[r+1]-b[r]; if((double)toc/M<(double)ABS(b[r+1])){ dp[k][r+1][1]=min(dp[k][r+1][1],toc); } } if(k){ long long toc=dp[k][r][l]; if(l==0)toc+=b[k]-b[k-1]; else toc+=b[r]-b[k-1]; if((double)toc/M<(double)ABS(b[k-1])){ dp[k-1][r][0]=min(dp[k-1][r][0],toc); } } } } } long long ret=min(dp[0][a-1][0],dp[0][a-1][1]); if(ret<inf){ right=M; }else left=M; } printf("%.12f\n",left); }
C:
実 家 の よ う な 安 心 感
#include<stdio.h> #include<algorithm> #include<vector> using namespace std; int p[300000]; int q[300000]; int segtree[524288]; int query(int a,int b,int c,int d,int e){ if(d<a||b<c)return 0; if(c<=a&&b<=d)return segtree[e]; return max(query(a,(a+b)/2,c,d,e*2),query((a+b)/2+1,b,c,d,e*2+1)); } void update(int a,int b){ a+=262144; while(a){ segtree[a]=max(segtree[a],b); a/=2; } } pair<pair<int,int> ,int> d[300000]; int z[300000]; int cnt[300000]; vector<int>lc[300000]; vector<pair<pair<int,int> ,int> >ev; int y[300000]; int lq[300000]; int main(){ int a,b,c; scanf("%d%d%d",&a,&b,&c); for(int i=0;i<a;i++){ scanf("%d%d",p+i,q+i); d[i]=make_pair(make_pair(q[i],-p[i]),i); z[i]=p[i]; } z[a]=0; z[a+1]=b; d[a]=make_pair(make_pair(0,0),a); d[a+1]=make_pair(make_pair(c,-b),a+1); p[a+1]=b; q[a+1]=c; a+=2; std::sort(d,d+a); std::sort(z,z+a); for(int i=0;i<a;i++){ int at=lower_bound(z,z+a,-d[i].first.second)-z; // printf("%d\n",at); int val=0; if(at)val=query(0,262143,0,at-1,1); cnt[d[i].second]=val+1; // printf("%d %d\n",d[i].second,val+1); update(at,val+1); } int lca=cnt[a-1]; for(int i=0;i<524288;i++)segtree[i]=0; for(int i=a-1;i>=0;i--){ int at=lower_bound(z,z+a,-d[i].first.second)-z; int val=0; val=query(0,262143,at+1,262142,1); if(cnt[d[i].second]+val==lca)lc[cnt[d[i].second]].push_back(d[i].second); update(at,val+1); } for(int i=0;i<=lca;i++){ // printf("%d: ",i); // for(int j=0;j<lc[i].size();j++)printf("%d ",lc[i][j]); // printf("\n"); } long long ret=0; for(int i=0;i<295000;i++){ if(lc[i].size()==0||lc[i+1].size()==0)continue; ev.clear(); int sz=0; for(int j=0;j<lc[i].size();j++){ ev.push_back(make_pair(make_pair(p[lc[i][j]],q[lc[i][j]]),0)); } for(int j=0;j<lc[i+1].size();j++){ ev.push_back(make_pair(make_pair(p[lc[i+1][j]],q[lc[i+1][j]]),1)); y[sz++]=q[lc[i+1][j]]; } std::sort(ev.begin(),ev.end()); //for(int j=0;j<ev.size();j++)printf("%d %d %d %d %d\n",i,j,ev[j].first.first,ev[j].first.second,ev[j].second); std::sort(y,y+sz); int r=999999999; int ind=sz-1; int on=0; for(int j=0;j<ev.size();j++){ if(ev[j].second==0){ r=min(r,ev[j].first.second); on++; }else {ind--;on--;} // printf("%d %d %d %d %d\n",i,j,r,ind,y[ind]); if(ind>=0&&j<ev.size()-1&&ev[j].first.first!=ev[j+1].first.first&&r<y[ind]){ ret+=(long long)(ev[j+1].first.first-ev[j].first.first)/2*((y[ind]-r)/2); } } //printf("%lld\n",ret); } printf("%lld\n",ret); }
D:
不可能
Dの部分点すら取れなかったけど2位でした。
