面白いかどうかはさておき、教育された感がある。普段Aからやってると抜かされるのでBからやったら大失敗した。
| A | B | C | D | E | Place |
|---|---|---|---|---|---|
| 01:01 | 00:48 | - | 01:35 | - | 57th |
A:
やるだけ。
#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 dp[2][1<<7][2]; int p7[24]; int main(){ int a,b;scanf("%d%d",&a,&b); int A=0; int B=0; int c=a-1;int d=b-1; while(c){ c/=7; A++; } while(d){ d/=7; B++; } p7[0]=1; for(int i=1;i<24;i++)p7[i]=p7[i-1]*7; a--;b--; if(!A)A++; if(!B)B++; dp[0][0][0]=1; for(int i=0;i<A+B;i++){ int t=i%2; for(int j=0;j<(1<<7);j++)dp[!t][j][0]=dp[!t][j][1]=0; for(int j=0;j<(1<<7);j++){ for(int k=0;k<2;k++){ if(!dp[t][j][k])continue; // printf("%d %d %d: %d\n",i,j,k,dp[i][j][k]); for(int l=0;l<7;l++){ if(j&(1<<l))continue; int tk=k; if(i<A){ if(k==0&&a/p7[A-i-1]%7<l)continue; else if(a/p7[A-i-1]%7>l)tk=1; }else{ if(k==0&&b/p7[A+B-i-1]%7<l)continue; else if(b/p7[A+B-i-1]%7>l)tk=1; } if(i==A-1)tk=0; dp[!t][j+(1<<l)][tk]+=dp[t][j][k]; } } } } int ret=0; for(int i=0;i<(1<<7);i++)for(int j=0;j<2;j++)ret+=dp[(A+B)%2][i][j]; printf("%d\n",ret); }
B:
慣れないdsu on treeを練習した。慣れない。あと定数倍がきつすぎ
ポインタに造詣がない人には、dsu on treeのあの書き方はデマ一より有用？
#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<int>g[310000]; int sz[310000]; int num; int L[310000]; int R[310000]; int conv[310000]; int nx[310000]; void dfs(int a){ sz[a]=1; L[a]=num; conv[num]=a; int mn=0; num++; for(int i=0;i<g[a].size();i++){ dfs(g[a][i]); sz[a]+=sz[g[a][i]]; if(mn<sz[g[a][i]]){ mn=sz[g[a][i]]; nx[a]=i; } } R[a]=num; } int ans[310000]; set<pair<pair<int,int>,int> > S; set<pair<pair<int,int>,int> > T; int mx[310000]; void solve(int a,int b){ int to=-1; for(int i=0;i<g[a].size();i++){ mx[a]=max(mx[a],sz[g[a][i]]); if(nx[a]==i){ to=g[a][i];continue; } solve(g[a][i],0); } if(~to)solve(to,1); for(int i=0;i<g[a].size();i++){ if(to==g[a][i])continue; solve(g[a][i],1); } if(!~ans[a]){ T.insert(make_pair(make_pair(mx[a],sz[a]),a)); S.insert(make_pair(make_pair(sz[a],mx[a]),a)); int del=0; for(set<pair<pair<int,int>,int> > ::iterator it=S.begin();it!=S.end();it++){ if((*it).first.first*2<sz[a])del++; else break; } for(int i=0;i<del;i++){ pair<pair<int,int>,int> tmp=*(S.begin()); S.erase(tmp); swap(tmp.first.first,tmp.first.second); T.erase(tmp); } ans[a]=(*(T.begin())).second; } // printf("%d: %d %d %d\n",a,T.begin()->first.first,T.begin()->first.second,T.begin()->second); if(b==0){ for(int i=L[a];i<R[a];i++){ T.erase(make_pair(make_pair(mx[conv[i]],sz[conv[i]]),conv[i])); S.erase(make_pair(make_pair(sz[conv[i]],mx[conv[i]]),conv[i])); } } } int main(){ int a,b;scanf("%d%d",&a,&b); for(int i=0;i<a-1;i++){ int p;scanf("%d",&p);p--; g[p].push_back(i+1); } for(int i=0;i<a;i++)ans[i]=-1; dfs(0); solve(0,1); while(b--){ int p;scanf("%d",&p);p--;printf("%d\n",ans[p]+1); } }
D:
計算量的には O(n log n+kn)で余裕そうに見えるがO(kn)パートが定数4のついたsetを使うやつで結構重そう、というか実際重い。
Time Limitの設定が総じて雑...？
#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=1000010007; const long long inf=mod*mod; int r[110000]; int c[110000]; pair<int,int>p[110000]; pair<int,int>ev[210000]; long long ret[110000]; int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<a;i++){ scanf("%d%d",r+i,c+i); ev[i*2+1]=make_pair(r[i],i+1); ev[i*2]=make_pair(r[i]+b,-i-1); p[i]=make_pair(c[i],r[i]); } std::sort(p,p+a); std::sort(ev,ev+a*2); int last=-mod; set<pair<int,pair<int,int> > > S; for(int i=0;i<a*2;i++){ // printf("%d: %d %d\n",i,ev[i].first,ev[i].second); if(i==0||ev[i].first!=ev[i-1].first){ long long ks=ev[i].first-last; int las=-mod; int cnt=0; for(set<pair<int,pair<int,int> > >::iterator it=S.begin();it!=S.end();it++){ if(it==S.begin()||((*it).first!=las)){ if(cnt)ret[cnt]+=((long long)(*it).first-las)*ks; las=(*it).first; } cnt+=(*it).second.first; } last=ev[i].first; } if(ev[i].second>0){ S.insert(make_pair(c[ev[i].second-1],make_pair(1,ev[i].second))); S.insert(make_pair(c[ev[i].second-1]+b,make_pair(-1,ev[i].second))); }else{ S.erase(make_pair(c[-ev[i].second-1],make_pair(1,-ev[i].second))); S.erase(make_pair(c[-ev[i].second-1]+b,make_pair(-1,-ev[i].second))); } } for(int i=1;i<=a;i++){ if(i!=1)printf(" "); printf("%I64d",ret[i]); } printf("\n"); }
