ひとり地区予選 2018-2019 ACM-ICPC Southeastern European Regional
嫌いな問題ばっかりでやる気が失せた。
B: Broken Watch
やるだけ問題に時間を使うな
int main(){ long long a,b,c,n; scanf("%I64d%I64d%I64d%I64d",&a,&b,&c,&n); if(n==2){ printf("0\n");return 0; } unsigned long long ret=1; ret=n*(n-1); if(ret%6==0){ ret/=6;ret*=n-2; }else if(ret%3==0){ ret/=3;ret*=(n-2)/2; }else if(ret%2==0){ ret/=2;ret*=(n-2)/3; }else ret*=(n-2)/6; long long tmp=n*((n-1)/2); if(tmp%2==0){ tmp/=2;ret-=tmp*((n-1)/2-1); }else{ ret-=tmp*(((n-1)/2-1)/2); } if(a!=b&&b!=c&&c!=a){ ret*=6; }else if(a!=b||b!=c||c!=a){ ret*=3; }else{ ; } printf("%I64u\n",ret); }
C: Tree
虚無
int p[110]; vector<int>g[110]; int x[110]; int y[110]; vector<int>f; void dfs(int a,int b,int c){ if(p[a]==1){ f.push_back(c); } for(int i=0;i<g[a].size();i++){ if(g[a][i]==b)continue; dfs(g[a][i],a,c+1); } } int main(){ int a,b;scanf("%d%d",&a,&b); for(int i=0;i<a;i++)scanf("%d",p+i); for(int i=0;i<a-1;i++){ int s,t;scanf("%d%d",&s,&t); s--;t--;g[s].push_back(t); g[t].push_back(s); x[i]=s;y[i]=t; } int ret=mod; for(int i=0;i<a;i++){ f.clear(); dfs(i,-1,0); std::sort(f.begin(),f.end()); ret=min(ret,f[b-1]*2); } for(int i=0;i<a-1;i++){ f.clear(); dfs(x[i],y[i],0); dfs(y[i],x[i],0); std::sort(f.begin(),f.end()); ret=min(ret,f[b-1]*2+1); } printf("%d\n",ret); }
E: Fishermen
実家。
int X[210000]; int Y[210000]; int z[210000]; int q[210000]; int bit[210000]; vector<pair<pair<int,int> ,int > >ev; int sum(int a,int b){ if(a)return sum(0,b)-sum(0,a-1); int ret=0; for(;b>=0;b=(b&(b+1))-1)ret+=bit[b]; return ret; } void add(int a,int b){ for(;a<210000;a|=a+1)bit[a]+=b; } int ans[210000]; int main(){ int a,b,c; scanf("%d%d%d",&a,&b,&c); for(int i=0;i<a;i++){ scanf("%d%d",X+i,Y+i); z[i]=X[i]-Y[i]; ev.push_back(make_pair(make_pair(X[i]+Y[i],-1),X[i]-Y[i])); } std::sort(z,z+a); for(int i=0;i<b;i++){ scanf("%d",q+i); ev.push_back(make_pair(make_pair(q[i]+c,i),q[i]-c)); } std::sort(ev.begin(),ev.end()); for(int i=0;i<ev.size();i++){ if(ev[i].first.second==-1){ add(lower_bound(z,z+a,ev[i].second)-z,1); }else{ ans[ev[i].first.second]=sum(lower_bound(z,z+a,ev[i].second)-z,201000); } } for(int i=0;i<b;i++)printf("%d\n",ans[i]); }
F: Min Max Convert
手前まで全部変えて1対1にすればやりたい方にできる。
面倒すぎる。
int A[110000]; int B[110000]; int fr[110000]; int m[210000]; int L[210000]; int R[210000]; int segtree[524288]; int query(int a,int b,int c,int d,int e){ if(d<a||b<c)return -mod; 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; } } vector<pair<pair<int,int> ,int> >qu; int main(){ int a;scanf("%d",&a); for(int i=0;i<a;i++)scanf("%d",A+i); for(int i=0;i<a;i++)scanf("%d",B+i); int at=0; for(int i=0;i<a;i++){ while(at<a&&A[at]!=B[i]){ at++; } fr[i]=at; // printf("%d\n",fr[i]); } if(at==a){ printf("-1\n");return 0; } for(int i=0;i<a;i++)update(i,A[i]); int sz=0; int lL=mod; int lv=0; for(int i=a-1;i>=0;i--){ if(fr[i]<i){ L[sz]=fr[i]+1; R[sz]=i; m[sz]=1; int val=0; if(lL<=i)val=lv; val=max(val,query(0,262143,fr[i]+1,min(lL-1,i),1)); sz++; L[sz]=fr[i]; R[sz]=i; if(val<B[i])m[sz]=1; lv=B[i]; sz++; lL=fr[i]; } } for(int i=0;i<524288;i++)segtree[i]=0; reverse(qu.begin(),qu.end()); at=0; for(int i=0;i<qu.size();i++){ while(at<a&&at<qu[i].first.first){ update(at,A[at]);at++; } while(at<=qu[i].first.second){ update(at,qu[i].second); at++; } } while(at<a){ update(at,A[at]); at++; } lL=-mod; lv=0; for(int i=0;i<a;i++){ if(fr[i]>i){ L[sz]=i; R[sz]=fr[i]-1; m[sz]=1; int val=0; if(i<=lL)val=lv; val=max(val,query(0,262143,max(lL+1,i),R[sz],1)); sz++; L[sz]=i; R[sz]=fr[i]; if(val<B[i])m[sz]=1; lv=B[i]; sz++; lL=fr[i]; } } printf("%d\n",sz); for(int i=0;i<sz;i++){ if(m[i]==0)printf("m "); else printf("M "); printf("%d %d\n",L[i]+1,R[i]+1); } }
G: Matrix Queues
見るからに独立
int segtree[2][1<<21]; int t[2][21]; int cur[2][1<<20]; long long v[21]; int main(){ int a,b;scanf("%d%d",&a,&b); for(int i=0;i<=a;i++)t[0][i]=t[1][i]=(1<<i); while(b--){ int p,q;scanf("%d%d",&p,&q);q--; int ad=1; if(segtree[p][q+(1<<a)])ad=-1; int at=q+(1<<a); int lv=a; while(at){ if(segtree[p][at]==0||segtree[p][at]==(1<<(a-lv))){ t[p][lv]--; } segtree[p][at]+=ad; if(segtree[p][at]==0||segtree[p][at]==(1<<(a-lv))){ t[p][lv]++; } at/=2;lv--; } for(int i=0;i<=a;i++)v[i]=0; long long X=0; long long Y=0; long long ng=0; for(int i=0;i<=a;i++){ X=t[0][i]; Y=t[1][i]; v[i]=X*Y-ng; ng+=v[i]; ng*=4; } long long ret=0; long long tmp=0; for(int i=a;i>=0;i--){ tmp+=v[i]; ret+=tmp; tmp/=4; } printf("%I64d\n",ret); } }
H: Modern Djinn
問題文が意味不明。せっかく考えてどうせ乱択でしょってなると気が抜ける。
vector<pair<int,int> >g[110000]; int t[120000]; int at[2][220000]; int cnt[2]; int main(){ int T;scanf("%d",&T); while(T--){ int a,b;scanf("%d%d",&a,&b); for(int i=0;i<a;i++){ g[i].clear(); } for(int i=0;i<b;i++){ int p,q;scanf("%d%d",&p,&q);p--;q--; g[p].push_back(make_pair(q,i)); } while(1){ for(int i=0;i<a;i++)t[i]=rand()%2; // for(int i=0;i<a;i++)printf("%d",t[i]);printf("\n"); cnt[0]=cnt[1]=0; for(int i=0;i<a;i++){ for(int j=0;j<g[i].size();j++){ if(t[i]!=t[g[i][j].first]){ at[t[i]][cnt[t[i]]++]=g[i][j].second; } } } if(cnt[0]>b/4){ printf("%d\n",cnt[0]); for(int i=0;i<cnt[0];i++){ if(i)printf(" "); printf("%d",at[0][i]+1); }printf("\n"); break; }else if(cnt[1]>b/4){ printf("%d\n",cnt[1]); for(int i=0;i<cnt[1];i++){ if(i)printf(" "); printf("%d",at[1][i]+1); }printf("\n"); break; } } } }
I: 枝刈り探索だと思ってTLEばっかり出して完全にやる気が消えた。普通に順列が決まってDPも普通だがWAが続くともうやる気になれない。
D: 木DPするだけなんだけど細部が複雑すぎる。
単純にこのセットは一人でやるには重すぎる。
