ひとり地区予選 SEERC 2015
yosupot と kyuridenamidaの3人でやりました(チームではない)。
F:
試し割りをするだけ
#include<stdio.h> #include<algorithm> using namespace std; long long t[110]; long long s[110]; long long u[110]; int main(){ int a;scanf("%d",&a); for(int i=0;i<a;i++){ scanf("%lld",&t[a-1-i]); } t[a]=1; int cnt=a; for(int r=-10;r<=10;r++){ while(cnt){ for(int i=0;i<10;i++){ s[i]=t[i]; u[i]=0; } for(int i=cnt;i>0;i--){ long long ks=s[i]; u[i-1]=ks; s[i-1]-=ks*r; } if(s[0]==0){ cnt--; for(int i=0;i<10;i++)t[i]=u[i]; }else break; } /*for(int i=0;i<=cnt;i++){ printf("%lld ",t[cnt-i]); }printf("\n");*/ } printf("%d\n",cnt); }
I:
メモリ制限が4MBなことに気づかず
気づいたらやるだけ
#include<stdio.h> #include<algorithm> using namespace std; int c[110000]; int d[110000]; int main(){ int a,b;scanf("%d%d",&a,&b); for(int i=0;i<a;i++){ int e;scanf("%d",&e); c[e/10000]++; d[e%10000]++; } int ret=0; for(int i=0;i<=100000;i++)if(c[i]%b)ret=i*10000; for(int i=0;i<10000;i++)if(d[i]%b)ret+=i; printf("%d\n",ret); }
D:
適当に数論する
#include<stdio.h> #include<algorithm> using namespace std; long long gcd(long long a,long long b){ while(a){ b%=a;long long c=a;a=b;b=c; } return b; } long long lcm(long long a,long long b){ return a/gcd(a,b)*b; } int main(){ int a,b;scanf("%d%d",&a,&b); if(a>b)swap(a,b); if(a==b){ printf("1\n");return 0; } int c=b-a; long long ret=-1; int ans=1000000007; for(int i=1;i*i<=c;i++){ if(c%i==0){ int n=(i-a%i); long long tmp=lcm(a+n,b+n); if(ret==-1||ret>tmp||(ret==tmp&&ans>n)){ ret=tmp;ans=n; } n=(c/i-a%(c/i)); tmp=lcm(a+n,b+n); if(ret==-1||ret>tmp||(ret==tmp&&ans>n)){ ret=tmp;ans=n; } } } printf("%d\n",ans); }
B:
Heavy-Light Decomposition + 平方分割
Do useをコピペした
#include<stdio.h> #include<algorithm> #include<vector> #include<queue> #define BEGIN_STACK_EXTEND(size) void * stack_extend_memory_ = malloc(size);void * stack_extend_origin_memory_;char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);*stack_extend_dummy_memory_ = 0;asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024)); #define END_STACK_EXTEND asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));free(stack_extend_memory_); using namespace std; int c[510000]; int sz[510000]; int eu[1010000]; int conv[510000]; int rev[510000]; vector<int>g[510000]; int L[510000]; int par[510000]; int str[510000]; int ww[510000]; int wn[510000]; int SQ=500; int cur; int cur2; void dfs(int a,int b){ par[a]=b; conv[a]=cur; rev[cur]=a; cur++; L[a]=cur2; eu[cur2++]=a; sz[a]=1; str[a]=-1; for(int i=0;i<g[a].size();i++){ if(g[a][i]==b)continue; dfs(g[a][i],a); eu[cur2++]=a; sz[a]+=sz[g[a][i]]; if(str[a]==-1||sz[str[a]]<sz[g[a][i]]){ str[a]=g[a][i]; } } if(sz[str[a]]*2<sz[a])str[a]=-1; } struct wolf{ vector<int> node; vector<long long>val; vector<long long>sq; int par; int at; wolf(){ par=at=-1; } }; long long mod=1000000007; long long inf=(long long)mod*mod; vector<wolf> hl; int lcaseg[2097152]; int lcaupd(int a,int b){ a+=1048576; while(a){ lcaseg[a]=min(lcaseg[a],b); a/=2; } } int lcamin(int a,int b,int c,int d,int e){ if(d<a||b<c)return mod; if(c<=a&&b<=d)return lcaseg[e]; return min(lcamin(a,(a+b)/2,c,d,e*2),lcamin((a+b)/2+1,b,c,d,e*2+1)); } int main(){ // BEGIN_STACK_EXTEND(250*1024*1024) int a,b; scanf("%d",&a); for(int i=0;i<a-1;i++){ int p,q; scanf("%d%d",&p,&q); g[p].push_back(q); g[q].push_back(p); } for(int i=0;i<a;i++)scanf("%lld",c+i); dfs(0,-1); hl.push_back(wolf()); hl[0].node.push_back(0); queue<pair<int,int> >Q; Q.push(make_pair(0,0)); ww[0]=wn[0]=0; while(Q.size()){ int at=Q.front().first; int seq=Q.front().second; Q.pop(); for(int i=0;i<g[at].size();i++){ if(g[at][i]==par[at])continue; if(str[at]==g[at][i]){ ww[g[at][i]]=seq; wn[g[at][i]]=hl[seq].node.size(); hl[seq].node.push_back(g[at][i]); Q.push(make_pair(g[at][i],seq)); }else{ Q.push(make_pair(g[at][i],hl.size())); ww[g[at][i]]=hl.size(); wn[g[at][i]]=0; hl.push_back(wolf()); hl[hl.size()-1].node.push_back(g[at][i]); hl[hl.size()-1].par=seq; hl[hl.size()-1].at=wn[at]; } } } for(int i=0;i<2097152;i++)lcaseg[i]=mod; for(int i=0;i<cur2;i++){ lcaupd(i,conv[eu[i]]); } for(int i=0;i<hl.size();i++){ int sz=hl[i].node.size(); hl[i].val=vector<long long>(sz); hl[i].sq=vector<long long>((sz+SQ-1)/SQ); for(int j=0;j<sz;j++){ hl[i].val[j]=c[hl[i].node[j]]; hl[i].sq[j/SQ]+=c[hl[i].node[j]]; } } // for(int i=0;i<a;i++)printf("%d %d\n",ww[i],wn[i]); scanf("%d",&b); while(b--){ int K,u,v; long long x,y,A,B,C,D; scanf("%d%lld%lld%lld%lld%lld%lld%d%d",&K,&x,&y,&A,&B,&C,&D,&u,&v); int q=u; int r=v; if(L[q]>L[r])swap(q,r); int lca=rev[lcamin(0,1048575,L[q],L[r],1)]; int goal=ww[lca]; vector<pair<int,pair<int,int> > >ql; vector<pair<int,pair<int,int> > >qr; if(goal==ww[q]){ ql.push_back(make_pair(goal,make_pair(wn[q],wn[lca]))); }else{ ql.push_back(make_pair(ww[q],make_pair(wn[q],0))); int now=hl[ww[q]].par; int at=hl[ww[q]].at; while(now!=goal){ ql.push_back(make_pair(now,make_pair(at,0))); at=hl[now].at; now=hl[now].par; } ql.push_back(make_pair(goal,make_pair(at,wn[lca]))); } if(goal==ww[r]){ if(r!=lca)qr.push_back(make_pair(goal,make_pair(wn[r],wn[lca]+1))); }else{ qr.push_back(make_pair(ww[r],make_pair(wn[r],0))); int now=hl[ww[r]].par; int at=hl[ww[r]].at; while(now!=goal){ qr.push_back(make_pair(now,make_pair(at,0))); at=hl[now].at; now=hl[now].par; } if(at!=wn[lca])qr.push_back(make_pair(goal,make_pair(at,wn[lca]+1))); } if(qr.size()){ for(int i=qr.size()-1;i>=0;i--){ swap(qr[i].second.first,qr[i].second.second); ql.push_back(qr[i]); } } // printf("\n"); // for(int i=0;i<ql.size();i++){ // printf("%d (%d, %d)\n",ql[i].first,ql[i].second.first,ql[i].second.second); // } for(int i=0;i<K;i++){ hl[ww[x]].val[wn[x]]+=y; hl[ww[x]].sq[wn[x]/SQ]+=y; x=(A*x+B)%a; y=(C*y+D)%mod; } long long ret=0; for(int i=0;i<ql.size();i++){ if(ql[i].second.first>ql[i].second.second)swap(ql[i].second.first,ql[i].second.second); int p1=ql[i].second.first; int p2=ql[i].second.second; int z=ql[i].first; if(p1/SQ==p2/SQ){ for(int j=p1;j<=p2;j++){ // printf("%d: %lld\n",hl[z].node[j],hl[z].val[j]); ret+=hl[z].val[j]; } }else{ for(int j=p1;j%SQ;j++)ret+=hl[z].val[j]; for(int j=p2-p2%SQ;j<=p2;j++)ret+=hl[z].val[j]; for(int j=(p1+SQ-1)/SQ;j<p2/SQ;j++)ret+=hl[z].sq[j]; } } printf("%lld\n",ret); } //END_STACK_EXTEND }
夕食を食べる。
H:
imos法とかいろんなのをつかって上手いこと計算量を抑える。
#include<stdio.h> #include<algorithm> #include<vector> using namespace std; int imos[11000]; vector<pair<int,int> > v[1100]; vector<int> w[1100]; typedef unsigned long long wolf; wolf chk[16][11000]; int main(){ int a,b,c; scanf("%d%d%d",&a,&b,&c); for(int i=0;i<c;i++){ int p,q,r; scanf("%d%d%d",&p,&q,&r); p--;q--;r--; imos[q]++; imos[r]--; v[p].push_back(make_pair(q,1)); v[p].push_back(make_pair(r,-1)); w[p].push_back(q); } for(int i=0;i<a;i++)w[i].push_back(b-1); for(int i=0;i<a;i++)std::sort(v[i].begin(),v[i].end()); for(int i=0;i<a;i++)std::sort(w[i].begin(),w[i].end()); for(int i=0;i<b;i++){ imos[i+1]+=imos[i]; } for(int i=0;i<a;i++){ int cnt=0; int at=0; for(int j=0;j<b;j++){ while(at<v[i].size()&&v[i][at].first==j){ cnt+=v[i][at].second; at++; } if(cnt==0){ chk[i/64][j]+=(1LL<<(i%64)); } } } int ret=0; int left=0; for(int i=0;i<b;i++){ if(i&&imos[i-1]>=a){ left=i; } ret+=i-left; } for(int i=0;i<b-1;i++){ int tmp=0; for(int j=0;j<a;j++){ if(!(chk[j/64][i]&(1LL<<j)))continue; int at=*(lower_bound(w[j].begin(),w[j].end(),i)); tmp=max(tmp,at-i); } //printf("%d\n",tmp); ret-=tmp; } printf("%d\n",ret); }
E:
DijkstraとかbitDPを多用するよくある問題。
#include<stdio.h> #include<algorithm> #include<vector> #include<queue> using namespace std; vector<pair<int,int> > g[21000]; int ijk[21000]; int v[21000]; int g2[20][20]; int lis[20]; int sc[1<<15]; int dp[1<<15][16]; int dp2[1<<15]; int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<b;i++){ int p,q,r,s; scanf("%d%d%d%d",&p,&q,&r,&s); q--;r--; g[q].push_back(make_pair(r,s)); if(p==2){ g[r].push_back(make_pair(q,s)); } } int T; scanf("%d",&T); int V,K; scanf("%d%d",&V,&K); lis[K]=V-1; for(int i=0;i<K;i++){ scanf("%d",lis+i); lis[i]--; } for(int i=0;i<=K;i++){ int st=lis[i]; for(int j=0;j<a;j++){ v[j]=0;ijk[j]=1010101010; } ijk[st]=0; priority_queue<pair<int,int> > Q; Q.push(make_pair(0,st)); while(Q.size()){ int at=Q.top().second; int cost=-Q.top().first;Q.pop(); if(v[at])continue; v[at]=1; for(int j=0;j<g[at].size();j++){ int to=g[at][j].first; int toc=cost+g[at][j].second; if(!v[to]&&ijk[to]>toc){ ijk[to]=toc; Q.push(make_pair(-toc,to)); } } } for(int j=0;j<=K;j++)g2[i][j]=ijk[lis[j]]; } //for(int i=0;i<=K;i++)for(int j=0;j<=K;j++)printf("%d %d: %d\n",i,j,g2[i][j]); for(int i=0;i<(1<<K);i++)for(int j=0;j<=K;j++)dp[i][j]=1010101010; dp[0][K]=0; for(int i=0;i<(1<<K);i++){ if(__builtin_popcount(i)>=4)continue; for(int j=0;j<=K;j++){ for(int k=0;k<K;k++){ if(i&(1<<k))continue; dp[i+(1<<k)][k]=min(dp[i+(1<<k)][k],dp[i][j]+g2[j][k]); } } } for(int i=0;i<(1<<K);i++)sc[i]=1010101010; for(int i=0;i<(1<<K);i++)for(int j=0;j<=K;j++) sc[i]=min(sc[i],dp[i][j]); //for(int i=0;i<(1<<K);i++)printf("%d: %d\n",i,sc[i]); for(int i=0;i<(1<<K);i++)dp2[i]=1010101010; dp2[0]=0; for(int i=0;i<(1<<K);i++){ int rem=(1<<K)-1-i; int bit=rem; while(bit){ if(__builtin_popcount(bit)<=4){ dp2[i+bit]=min(dp2[i+bit],dp2[i]+sc[bit]+T); } bit=(bit-1)&rem; } } printf("%d\n",dp2[(1<<K)-1]); }
風呂に入ってのんびりしてからCを書くも間に合わない。
アディショナルタイム(C):
素因数の指数の集合の個数が少ないので全部列挙してDP
うまくまとめないとTLEする。
#include<stdio.h> #include<algorithm> #include<vector> #include<map> using namespace std; int p[110000]; int lis[110000]; map<vector<int>,int> m; double dp[2000][34]; vector<vector<int> > v; int use[20]; void dfs(long long now,int at,int r){ long long tmp=now; if(at){ vector<int>t; for(int i=0;i<at;i++)t.push_back(use[i]); m[t]=v.size(); v.push_back(t); } for(int i=1;i<=r;i++){ tmp*=lis[at]; if(tmp>10000000000LL)break; use[at]=i; dfs(tmp,at+1,i); } } int C[21][21]; int tt[21]; int cnt; int perm[40][40]; void dfs2(int a,int b,int ks){ if(b==v[a].size()){ vector<int>L; vector<int>R; for(int i=0;i<v[a].size();i++){ if(tt[i])L.push_back(tt[i]); if(v[a][i]-tt[i])R.push_back(v[a][i]-tt[i]); } if(L.size()==0||R.size()==0)return; //if(v[a].size()==2&&v[a][0]==3&&v[a][1]==2){ // printf("%d: ",ks); // for(int i=0;i<v[a].size();i++)printf("%d ",tt[i]); // printf("\n"); //} std::sort(L.begin(),L.end());reverse(L.begin(),L.end()); std::sort(R.begin(),R.end());reverse(R.begin(),R.end()); int j=m[L];int at=m[R]; int lcnt=0; int rcnt=0; for(int k=0;k<v[j].size();k++)lcnt+=v[j][k]; for(int k=0;k<v[at].size();k++)rcnt+=v[at][k]; for(int k=0;k<lcnt;k++){ for(int l=0;l<rcnt;l++){ dp[a][max(k,l)+1]+=dp[j][k]*dp[at][l]*ks; } } cnt+=ks; return; } int to=b; for(int i=b+1;i<v[a].size();i++)if(v[a][i]==v[a][b])to=i; int len=to-b+1; for(int i=0;i<len;i++)perm[b][i]=0; for(int i=0;i<v[a][b];i++)perm[b][len+i]=1; do{ int to=ks; int ch=0; int use=0; int n=len; int ind=0; for(int i=0;i<len+v[a][b];i++){ if(perm[b][i]==1){ ch++; if(use)to*=C[n][use]; n-=use; use=0; }else{ tt[b+ind++]=ch;use++; } } dfs2(a,b+len,to); }while(next_permutation(perm[b],perm[b]+len+v[a][b])); } int main(){ C[0][0]=1; for(int i=0;i<20;i++){ for(int j=0;j<=i;j++){ C[i+1][j]+=C[i][j]; C[i+1][j+1]+=C[i][j]; } } p[0]=p[1]=-1; for(int i=2;i<110000;i++){ if(p[i]==-1)continue; p[i]=1; for(int j=i+i;j<110000;j+=i)p[j]=-1; } int sz=0; for(int i=2;i<110000;i++){ if(p[i]==1)lis[sz++]=i; } dfs(1,0,99999999); int n=v.size(); dp[0][0]=1; int Q=0; for(int i=1;i<n;i++){ cnt=0; dfs2(i,0,1); if(cnt)for(int j=0;j<34;j++)dp[i][j]/=cnt; } int T;scanf("%d",&T); while(T--){ long long a; scanf("%lld",&a); vector<int>s; long long b=a; for(int i=0;(long long)lis[i]*lis[i]<=b;i++){ if(b%lis[i]==0){ int tmp=0; while(b%lis[i]==0){ b/=lis[i]; tmp++; } s.push_back(tmp); } } if(b>1)s.push_back(1); std::sort(s.begin(),s.end()); reverse(s.begin(),s.end()); int ind=m[s]; double ret=0; for(int i=0;i<=33;i++){ ret+=dp[ind][i]*i; } printf("%.12f\n",ret); } }
