エキシビション大会中に編集しています。
さすがに今やっているコンテストの解法についてつぶやくのはいかがなものかと思うので、とりあえず昼のコンテストの参加記を書くことにします。
なぜか3位をとれました。やったぜ。
A,B,C,D,E:カンタン枠
簡単。こういうのは昔は早い人だったけど最近はのんびりやっています。パソコンの操作スピード的に勝てないし。
A:
#include<stdio.h> #include<algorithm> using namespace std; int main(){ int a,b; scanf("%d",&a); printf("%.12f\n",50.0/a); }
B:
#include<stdio.h> #include<algorithm> using namespace std; char str[114514]; int main(){ scanf("%s",str); int ret=0; for(int i=0;str[i];i++){ if(i%2)ret-=str[i]-'0'; else ret+=str[i]-'0'; } printf("%d\n",ret); }
C:
#include<stdio.h> #include<algorithm> using namespace std; char str[20]; int main(){ long long a;scanf("%lld",&a); for(int i=10;;i++){ long long v=0; sprintf(str,"%d",i); for(int j=0;str[j];j++){ v*=i; v+=str[j]-'0'; } if(v>a){ printf("-1\n");return 0; } if(v==a){ printf("%d\n",i);return 0; } } }
D:
#include<stdio.h> #include<algorithm> using namespace std; int main(){ long long a; scanf("%lld",&a); printf("%lld 2\n",a+1); }
E:
#include<stdio.h> #include<algorithm> using namespace std; int dp[2][3100]; int b[3100]; int main(){ int a;scanf("%d",&a); for(int i=0;i<a;i++)scanf("%d",b+i); for(int i=0;i<3100;i++)dp[0][i]=dp[1][i]=1; for(int i=0;i<a;i++){ // printf("%d %d\n",dp[0][i],dp[1][i]); for(int j=i+1;j<a;j++){ if(b[i]>b[j]){ dp[0][j]=max(dp[0][j],dp[1][i]+1); } if(b[j]>b[i]){ dp[1][j]=max(dp[1][j],dp[0][i]+1); } } } int ret=0; for(int i=0;i<a;i++){ ret=max(ret,dp[0][i]); ret=max(ret,dp[1][i]); } if(ret<3)ret=0; printf("%d\n",ret); }
H:
お得意の期待値なので適当に後ろからやればいいんだろうな～と思って後ろから上手い感じの方法を見つけてやったら通った。全員が同時に添い寝するケースだけ落ちていたんだけど、何かやたらと落ちているケース数が多かったのは気のせいだろうか。
#include<stdio.h> #include<vector> #include<algorithm> #include<set> using namespace std; char str[210000]; int c[210000]; double ret[210000]; double now[210000]; int num[210000]; int main(){ int a,b; scanf("%d%d",&a,&b); scanf("%s",str); multiset<int> S; for(int i=0;i<b;i++){ S.insert(0); } for(int i=0;i<a;i++){ if(str[i]=='1'){ int val=*(S.rbegin()); c[i]=val+1; S.insert(val+1); S.erase(S.lower_bound(val)); }else{ int val=*(S.begin()); c[i]=val+1; S.insert(val+1); S.erase(S.lower_bound(val)); } } int sz=0; for(multiset<int>::iterator it=S.begin();it!=S.end();it++){ num[*it]++; } //for(int i=0;i<a;i++)printf("%d\n",c[i]); //for(int i=0;i<sz;i++)add(i,val[i]); for(int i=0;i<=a;i++)now[i]=i; for(int i=a-1;i>=0;i--){ ret[i]=now[c[i]]; now[c[i]-1]=(now[c[i]]+num[c[i]-1]*now[c[i]-1])/(num[c[i]-1]+1); num[c[i]]--; num[c[i]-1]++; } for(int i=0;i<a;i++)printf("%.12f\n",ret[i]); }
F:
考察の前半パートは簡単で、あとは巡回スケジューリングなんだけど、円環ゲーは本当に苦手なので3通り全部書いてごまかした。
#include<stdio.h> #include<algorithm> using namespace std; int b[110000]; int dame[110000]; int L[110000]; int gcd(int a,int b){ while(a){ b%=a;int c=a;a=b;b=c; } return b; } int last[110000][4]; int dp[110000][4]; int main(){ int a; scanf("%d",&a); if(a==1){ printf("0\n");return 0; } for(int i=0;i<a;i++)scanf("%d",b+i); if(a==2&&b[0]==b[1]){ printf("0\n");return 0; } if(a==2){ printf("1\n");return 0; } for(int i=0;i<a;i++){ if(b[(i+1)%a]%gcd(b[i],b[(i+2)%a]))L[(i+2)%a]=1; } int ret=999999999; for(int i=0;i<110000;i++) dp[i][0]=dp[i][1]=dp[i][2]=dp[i][3]=999999999; dp[0][0]=0; for(int i=0;i<a;i++){ if(!L[i]){ dp[i+1][0]=min(dp[i+1][0],min(dp[i][0],dp[i][1])); dp[i+1][1]=min(dp[i+1][1],dp[i][2]); dp[i+1][2]=min(dp[i+1][2],min(dp[i][0],min(dp[i][1],dp[i][2]))+1); }else{ dp[i+1][0]=min(dp[i+1][0],dp[i][1]); dp[i+1][1]=min(dp[i+1][1],dp[i][2]); dp[i+1][2]=min(dp[i+1][2],min(dp[i][0],min(dp[i][1],dp[i][2]))+1); } } ret=min(dp[a][0],min(dp[a][1],dp[a][2])); for(int i=0;i<110000;i++) dp[i][0]=dp[i][1]=dp[i][2]=999999999; dp[0][1]=1; for(int i=0;i<a-2;i++){ if(!L[i]){ dp[i+1][0]=min(dp[i+1][0],min(dp[i][0],dp[i][1])); dp[i+1][1]=min(dp[i+1][1],dp[i][2]); dp[i+1][2]=min(dp[i+1][2],min(dp[i][0],min(dp[i][1],dp[i][2]))+1); }else{ dp[i+1][0]=min(dp[i+1][0],dp[i][1]); dp[i+1][1]=min(dp[i+1][1],dp[i][2]); dp[i+1][2]=min(dp[i+1][2],min(dp[i][0],min(dp[i][1],dp[i][2]))+1); } } ret=min(ret,min(dp[a-2][0],min(dp[a-2][1],dp[a-2][2]))); for(int i=0;i<110000;i++) dp[i][0]=dp[i][1]=dp[i][2]=999999999; dp[0][2]=1; for(int i=0;i<a-1;i++){ if(!L[i]){ dp[i+1][0]=min(dp[i+1][0],min(dp[i][0],dp[i][1])); dp[i+1][1]=min(dp[i+1][1],dp[i][2]); dp[i+1][2]=min(dp[i+1][2],min(dp[i][0],min(dp[i][1],dp[i][2]))+1); }else{ dp[i+1][0]=min(dp[i+1][0],dp[i][1]); dp[i+1][1]=min(dp[i+1][1],dp[i][2]); dp[i+1][2]=min(dp[i+1][2],min(dp[i][0],min(dp[i][1],dp[i][2]))+1); } } ret=min(ret,min(dp[a-1][0],min(dp[a-1][1],dp[a-1][2]))); printf("%d\n",ret); }
I:
JOIの合宿を大量にこなしていればすぐにかけると思います。
#include<stdio.h> #include<algorithm> #include<set> #include<vector> using namespace std; pair<pair<int,int> ,pair<int,int> > ev[1010000]; vector<int> g[110000]; int v[110000]; pair<int,int> fx[110000]; int rev[110000]; int q[110000][2]; int segtree[524288]; int query(int a,int b,int c,int d,int e){ if(d<a||b<c)return 999999999; if(c<=a&&b<=d)return segtree[e]; return min(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]=min(segtree[a],b); a/=2; } } int vn[300000]; int eul[300000]; int depth[110000]; int conv[110000]; int prev[110000]; int tmp; int len; void dfs(int a,int b){ conv[tmp]=a; vn[a]=tmp++; eul[len++]=vn[a]; depth[a]=b; for(int i=0;i<g[a].size();i++){ dfs(g[a][i],b+1); eul[len++]=vn[a]; } } int fi[300000]; int main(){ int a; scanf("%d",&a); int sz=0; for(int i=0;i<524288;i++)segtree[i]=999999999; for(int i=0;i<a;i++){ int p,q,r; scanf("%d%d%d",&p,&q,&r); int x=p+q; int y=p-q; x*=2;y*=2;r*=2; fx[i]=make_pair(x-r,i); ev[sz++]=make_pair(make_pair(x-r,1),make_pair(i,y-r)); ev[sz++]=make_pair(make_pair(x-r,1),make_pair(i,y+r)); ev[sz++]=make_pair(make_pair(x+r,-1),make_pair(i,y-r)); ev[sz++]=make_pair(make_pair(x+r,-1),make_pair(i,y+r)); } std::sort(fx,fx+a); for(int i=0;i<a;i++)rev[fx[i].second]=i; for(int i=0;i<sz;i++){ ev[i].second.first=rev[ev[i].second.first]+1; } ev[sz++]=make_pair(make_pair(-1000000007,1),make_pair(0,-1000000007)); ev[sz++]=make_pair(make_pair(-1000000007,1),make_pair(0,1000000007)); int b;scanf("%d",&b); for(int i=0;i<b;i++){ int p,q,r,s; scanf("%d%d%d%d",&p,&q,&r,&s); int x1=p+q; int y1=p-q; int x2=r+s; int y2=r-s; x1*=2;y1*=2;x2*=2;y2*=2; ev[sz++]=make_pair(make_pair(x1,0),make_pair(3+i*2,y1)); ev[sz++]=make_pair(make_pair(x2,0),make_pair(3+i*2+1,y2)); } set<pair<int,int> > S; std::sort(ev,ev+sz); for(int i=0;i<sz;i++){ if(ev[i].first.second==0){ set<pair<int,int> > ::iterator it=S.lower_bound(make_pair(ev[i].second.second,0)); int R=(*it).second; it--; int L=(*it).second; int num=ev[i].second.first-3; q[num/2][num%2]=min(L,R); } if(ev[i].first.second==1){ if(ev[i].second.first&&!v[ev[i].second.first]){ v[ev[i].second.first]=1; set<pair<int,int> > ::iterator it=S.lower_bound(make_pair(ev[i].second.second,0)); int R=(*it).second; it--; int L=(*it).second; int par=min(L,R); prev[ev[i].second.first]=par; // printf("%d %d %d %d\n",ev[i].second.first,par,L,R); g[par].push_back(ev[i].second.first); S.insert(make_pair(ev[i].second.second,ev[i].second.first)); }else if(ev[i].second.first){ S.insert(make_pair(ev[i].second.second,ev[i].second.first)); S.insert(make_pair(ev[i].second.second+1,prev[ev[i].second.first])); }else S.insert(make_pair(ev[i].second.second,ev[i].second.first)); } if(ev[i].first.second==-1){ if(v[ev[i].second.first]){ v[ev[i].second.first]=0; S.erase(make_pair(ev[i].second.second,ev[i].second.first)); }else{ S.erase(make_pair(ev[i].second.second,ev[i].second.first)); S.erase(make_pair(ev[i].second.second+1,prev[ev[i].second.first])); } } } dfs(0,0); for(int i=0;i<len;i++)update(i,eul[i]); for(int i=0;i<len;i++){ fi[eul[i]]=i; } for(int i=0;i<b;i++){ // printf("%d %d %d %d\n",q[i][0],q[i][1],fi[q[i][0]],fi[q[i][1]]); int A=fi[vn[q[i][0]]]; int B=fi[vn[q[i][1]]]; if(A>B)swap(A,B); int lca=conv[query(0,262143,A,B,1)]; printf("%d\n",depth[q[i][0]]+depth[q[i][1]]-depth[lca]*2); } }
コンテストは3位でした。残った2問は自分の今の実力ではとても解けないだろうし、解けるべき問題をちゃんと全部特に嵌らずに通せたのはよかった。(いつもそうだけど。)
ということで今日の残りと明日も楽しみます。
