単純に2時間コンテストとは思えないほど難しい。
| A | B | C | D | E | Place |
|---|---|---|---|---|---|
| 00:08 | 00:44 | - | - | - | 56th |
A:
(i+1)^2(i+2)^2にしてからsqrtを使う。(i+1)^2(i+2)^2はlong longに入らないが、あらかじめ(i+1)で割っておけば対処可能。
#include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<string.h> #include<vector> #include<set> #include<stdlib.h> using namespace std; const long long mod=1000000007; const long long inf=mod*mod; long long pv[110000]; long long ret[110000]; int main(){ int a;scanf("%d",&a); pv[0]=2; for(int i=1;i<a;i++){ pv[i]=(long long)i*(i+1); } for(int i=0;i<a;i++){ long long t=(long long)(i+1)*(i+2); long long s=t*(i+2); ret[i]=s-pv[i]/(i+1); } for(int i=0;i<a;i++)printf("%I64d\n",ret[i]); }
B:
ふだんCに置いてあるような難度のB。逆からコストの決まった辺だけで最短距離を求めておいて、L未満にならないような最小のコストをつけてたどっていく。
#include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<string.h> #include<vector> #include<set> #include<map> #include<stdlib.h> using namespace std; const long long mod=1000000007; const long long inf=mod*mod; vector<pair<int,int> > g[1100]; long long ijk[2][1100]; int v[2][1100]; int main(){ int a,b,c,d,e; scanf("%d%d%d%d%d",&a,&b,&c,&d,&e); for(int i=0;i<b;i++){ int p,q,r;scanf("%d%d%d",&p,&q,&r); g[p].push_back(make_pair(q,r)); g[q].push_back(make_pair(p,r)); } for(int i=0;i<2;i++)for(int j=0;j<a;j++)ijk[i][j]=inf; priority_queue<pair<long long,int> > Q; Q.push(make_pair(0,d)); ijk[0][d]=0; while(Q.size()){ long long cost=-Q.top().first; int at=Q.top().second;Q.pop(); if(v[0][at])continue; v[0][at]=1; for(int i=0;i<g[at].size();i++){ int to=g[at][i].first; if(g[at][i].second==0)continue; long long toc=cost+g[at][i].second; if(v[0][to]||ijk[0][to]<=toc)continue; ijk[0][to]=toc; Q.push(make_pair(-toc,to)); } } if(ijk[0][e]<c){ printf("NO\n");return 0; } Q.push(make_pair(0,e)); ijk[1][e]=0; map<pair<int,int>,long long>M; while(Q.size()){ long long cost=-Q.top().first; int at=Q.top().second;Q.pop(); if(v[1][at])continue; v[1][at]=1; for(int i=0;i<g[at].size();i++){ int to=g[at][i].first; long long toc=cost+g[at][i].second; if(g[at][i].second==0){ if(M.count(make_pair(min(at,to),max(at,to))))toc=cost+M[make_pair(min(at,to),max(at,to))]; else{ if(cost+1+ijk[0][to]>=c){ toc=cost+1; M[make_pair(min(at,to),max(at,to))]=1; }else{ toc=(c-ijk[0][to]); M[make_pair(min(at,to),max(at,to))]=c-cost-ijk[0][to]; } } } if(v[1][to]||ijk[1][to]<=toc)continue; ijk[1][to]=toc; Q.push(make_pair(-toc,to)); } } if(ijk[1][d]>c){ printf("NO\n");return 0; } printf("YES\n"); for(int i=0;i<a;i++)for(int j=0;j<g[i].size();j++){ if(i>g[i][j].first)continue; if(g[i][j].second)printf("%d %d %d\n",i,g[i][j].first,g[i][j].second); else printf("%d %d %I64d\n",i,g[i][j].first,M[make_pair(i,g[i][j].first)]); } }
C:
あからさまな重心分解に加え重心分解の中身を線形並みの速度にするのも難しそうなのでスルーした。また今度。
D:
田^^^8888_______________
田^^^8888____________|
田^^^8888__________|
田^^^8888________|
田^^^8888______|
みたいなのをつなげる。それぞれの田で6倍に増えて、隣の8をうまく使うと0~5倍にできるので、6進数で表記するのに対応する。
6^24>10^18なのでぎりぎり収まる。ただし右下の8を置くスペースだけは足りなくなるので、強引に押し込む。
こういう問題はそもそもサンプルがあってるのかすらわからない上デバッグしようにもどこから手をつけたらいいのかわからないので、大変困ります。良い解決方法はあるのでしょうか。
#include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<string.h> #include<vector> #include<set> #include<map> #include<stdlib.h> using namespace std; const long long mod=1000000007; const long long inf=mod*mod; int y[60][60]; int t[60][60]; int main(){ long long a; scanf("%I64d",&a); for(int i=0;i<23;i++){ t[i*2+2][i*2]=t[i*2+2][i*2+1]=1; y[i*2+1][i*2+2]=1; int f=a%6; // printf("%d",f); y[i*2][i*2+2+f]=1; // if(i==22)break; for(int j=0;j<7;j++){ if(i*2+3+j<49)t[i*2+1][i*2+3+j]=1; } if(i==22){ if(f==4){ y[i*2][i*2+2+2]=1; t[i*2+1][48]=0; }else if(f==5){ t[i*2+1][48]=0; } } y[i*2+1][i*2+10]=1; y[i*2+2][i*2+10]=1; a/=6; } //printf("%d\n",(int)a); if(!a)y[46][46]=1; //printf("\n"); printf("47 50\n"); vector<pair<pair<int,int>,pair<int,int> > >ans; for(int i=0;i<60;i++)for(int j=0;j<60;j++){ if(i+1<47&&j<50&&t[i][j])ans.push_back(make_pair(make_pair(i+1,j+1),make_pair(i+2,j+1))); if(i<47&&j+1<50&&y[i][j])ans.push_back(make_pair(make_pair(i+1,j+1),make_pair(i+1,j+2))); } printf("%d\n",(int)(ans.size())); for(int i=0;i<ans.size();i++){ printf("%d %d %d %d\n",ans[i].first.first,ans[i].first.second,ans[i].second.first,ans[i].second.second); } }
