UTPC2014(2015年開催)
やっと全部通した
satashunとsatosさんと自分(sigma425)で出ていました."頭文字が全員sだ""というか全員satじゃん""じゃあチーム名は3-SATで"みたいな会話があったがsatは僕のprefixではなかったことに終わってから(hogloidに言われて)気づいた.
300が解けなかったので悔い改めます.
A:はい
B:適当に1000倍する.もとからx,yが整数の時に注意.コードが汚い
C:ループの長さ.(1つ以下であることが保証されている)ループ取り出しはdfsをbool visitとかで書けばできるけど,取り出さなくていいなら適当に(mod 2なら0,1とかで)塗ればよいです.
D:コンテスト中はフローを流した(dilworth).DAGになるのは当たり前なんだけどちょっとバグがあって,指が初めに同じ位置にある場合に片方に向けてしか貼ってなかった、というバグをsatashunに見つけてもらった,プロ.DPで解き直しても似たようなバグを生やした.
E:trie
F:inversion
G:普通のDP.関係しうる所(X以下)が0,1,2以上の3^X通りを持てば良い.
H:コンテスト中はにぶたん書いてバグってデデドン(絶望).内角が170度以下というゆるふわ条件があるので,1度ずつ回していって直前の結果とのアレを見ればok(図)
I:分割してく時にも"データ構造をマージする一般的なテク"が使えるという話(小さい方を列挙 and erase and 新しいのを作る)."どっちが小さいのか"を知るのにqueueで,二つの木を1頂点ずつ順番に見ていくdfsを書いた.(実装が結構むずい)
J:
BITで個数とsumを持って"前からi個の和"みたいなのを得るよくあるアレ(後ろからi個,とかもわかる).
"一種類しか含まれないかどうか or 左からに種類目はなにか"とかは,segtreeでminとmaxを持てば出来る.
K:baby-giant stepは別の記事を書いたのでそれで.この問題特有のアレとしては,(行列(mod2)の)逆元が存在する条件が"Bの最高bitが1"であると簡単にわかるので,Aがでかい間何回かnxtを回しましょう.その時Xの最高bitが高い場所にあったら通り過ぎちゃってるのでもう無理.
L:想定解を書いたら余裕でTLEしたのでinputを手に入れて手元実行して埋め込みました.多分極小点カバーをもうちょっと頑張って少ない数の頂点で作れば早くなると思います(しかし適当に書いてもk/(k+1)*|V|以下という条件は満たされるのでオーダーは変わらない(22と20*4/5を比べると4倍になるのでTLEしたのだろう)).maxdegを3にすればよかったと思うんだけどなあ(それでも簡単に数え上げたりは出来ないと思うんだけど)
H以降のコード
H:
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; typedef double D; typedef complex<D> P; typedef pair<P,P> L; D pi=acos(-1); D eps=1e-8; P rot(P p,D th){ return polar(abs(p),arg(p)+th); } typedef pair<int,int> pii; int fix(D x){ return round(x); } D gety(D th){ printf("? %f\n",th); fflush(stdout); double ymax; scanf("%lf", &ymax); return ymax; } D cro(P a,P b){ return imag(conj(a)*b); } P intLL(L a,L b){ D t=cro(a.sc-a.fs,a.sc-b.fs)/cro(a.sc-a.fs,b.sc-b.fs); return b.fs+t*(b.sc-b.fs); } vector<pii> vs; int main(){ L pl; vector<P> ps; D th=pi/180.0; rep(i,360){ D y=gety(i); L l=L(rot(P(1,y),-i*th),rot(P(0,y),-i*th)); if(i>=1) ps.pb(intLL(l,pl)); pl=l; } rep(i,358){ if(abs(ps[i]-ps[i+1])<eps) vs.pb( pii(fix(ps[i].real()),fix(ps[i].imag())) ); } vs.erase(unique(all(vs)),vs.end()); if(vs[0]==vs.back()) vs.pop_back(); printf("! %d\n",vs.size()); int j=0; while(vs[j]!=pii(0,0)) j++; rep(i,vs.size()){ printf("! %d %d\n",vs[(j-i+vs.size())%vs.size()].fs,vs[(j-i+vs.size())%vs.size()].sc); } }
I:
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; typedef pair<int,int> P; int N,Q,a[100000],b[100000],wei[100000]; //id->weight set<P> st[100010]; //componentid->{weight,edgeid} int I=0; int con[100000]; //edgeid->componentid set<P> G[100000]; //{to,edgeid} int cnt,mx; set<P>::iterator it[2]; bool dfs(int v,int p){ cnt++; if(cnt>mx) return 0; for(P pp:G[v]){ int u=pp.fs; if(u==p) continue; if(!dfs(u,v)) return 0; } return 1; } void dfs2(int v,int p){ for(P pp:G[v]){ int u=pp.fs; if(u==p) continue; int eid=pp.sc; st[con[eid]].erase(P(wei[eid],eid)); st[I].insert(P(wei[eid],eid)); con[eid]=I; dfs2(u,v); } } int main(){ cin>>N; rep(i,N-1){ scanf("%d%d%d",a+i,b+i,wei+i); a[i]--,b[i]--; G[a[i]].insert(P(b[i],i)); G[b[i]].insert(P(a[i],i)); st[I].insert(P(wei[i],i)); } scanf("%d",&Q); rep(tt,Q){ int ty; scanf("%d",&ty); if(ty&1){ int id,d; scanf("%d%d",&id,&d); id--; if(a[id]<0) continue; int w=wei[id]; int c=con[id]; st[c].erase(P(w,id)); st[c].insert(P(w+d,id)); wei[id]+=d; }else{ int id; scanf("%d",&id); id--; if(a[id]<0){ puts("-1"); continue; } int cid=con[id]; id=st[cid].begin()->sc; printf("%d\n",id+1); G[a[id]].erase(P(b[id],id)); G[b[id]].erase(P(a[id],id)); st[cid].erase(P(wei[id],id)); I++; queue<P> que[2]; vector<int> svec[2]; rep(t,2){ int v=((t&1)?b[id]:a[id]); que[t].push(P(v,-1)); it[t]=G[v].begin(); } while(true){ rep(t,2){ if(que[t].empty()){ goempty: for(int eid:svec[t]){ // show(eid); st[con[eid]].erase(P(wei[eid],eid)); st[I].insert(P(wei[eid],eid)); con[eid]=I; } goto done; } P p=que[t].front(); while(true){ if(it[t]==G[p.fs].end()){ que[t].pop(); if(que[t].empty()) goto goempty; p=que[t].front(); it[t]=G[p.fs].begin(); continue; } if(it[t]->fs==p.sc){ it[t]++; continue; } break; } // printf("t=%d: add:%d->%d\n",t,p.fs+1,it[t]->fs+1); que[t].push(P(it[t]->fs,p.fs)); svec[t].pb(it[t]->sc); it[t]++; } } done: a[id]=con[id]=-1; /* cout<<"con:";rep(i,N-1) cout<<con[i]<<" "; puts(""); cout<<"wei:";rep(i,N-1) cout<<wei[i]<<" "; puts("");*/ } } }
J:
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; typedef long long ll; typedef pair<int,int> P; struct BIT{ static const int MX=210000; ll bit[MX]={}; ll sum(int i){ ll s=0; while(i>0){ s+=bit[i]; i-=i&-i; } return s; } void add(int i,int x){ while(i<MX){ bit[i]+=x; i+=i&-i; } } }; struct segtree{ static const int DEPTH=18; static const int p2=1<<DEPTH; int min[p2*2],max[p2*2],inf=1e9; void init(){ rep(i,p2*2) min[i]=inf,max[i]=-inf; } void update(int k,int a,int b){ k+=p2; min[k]=a; max[k]=b; k/=2; while(k){ min[k]=std::min(min[k*2],min[k*2+1]); max[k]=std::max(max[k*2],max[k*2+1]); k/=2; } } int calcl(int l,int r,int k,int c){ if(r-l==1) return l; if((max[k*2]==c&&min[k*2]==c)||min[k*2]==inf){ return calcl((l+r)/2,r,k*2+1,c); }else{ return calcl(l,(l+r)/2,k*2,c); } } int calcl(int c){ if(max[1]==c&&min[1]==c) return -1; return calcl(0,p2,1,c); } int calcr(int l,int r,int k,int c){ if(r-l==1) return l; if((max[k*2+1]==c&&min[k*2+1]==c)||min[k*2+1]==inf){ return calcr(l,(l+r)/2,k*2,c); }else{ return calcr((l+r)/2,r,k*2+1,c); } } int calcr(int c){ if(max[1]==c&&min[1]==c) return -1; return calcr(0,p2,1,c); } }; int N,Q; ll x[100000],a[100000],y[100000],b[100000]; int ty[100000]; vector<ll> ash; set<P> st; //pos,col segtree seg; BIT num,sum; void addcolor(int x,int c){ st.insert(P(x,c)); num.add(c,1); sum.add(c,c); seg.update(x,c,c); } void erasecolor(int x,int c){ st.erase(P(x,c)); num.add(c,-1); sum.add(c,-c); seg.update(x,seg.inf,-seg.inf); } ll getval(int c){ ll ret=0; ll l=seg.calcl(c),r=seg.calcr(c); // show(l); // show(r); if(l>=0){ l=-min(0LL,ash[l]),r=max(0LL,ash[r]); ret=l+r+min(l,r); } ll n=num.sum(c); ll s=sum.sum(c); ll n2=num.sum(BIT::MX-1); ll s2=sum.sum(BIT::MX-1); l=c*n-s; r=s2-s-c*(n2-n); ret+=l+r; return ret; } int med(){ int n=st.size()/2; int ub=200200,lb=0; while(ub-lb>1){ int m=(ub+lb)/2; if(num.sum(m)>n) ub=m; else lb=m; } return ub; } int main(){ cin>>N; rep(i,N) cin>>x[i]>>a[i]; cin>>Q; rep(i,Q) cin>>ty[i]>>y[i]>>b[i]; rep(i,N) ash.pb(x[i]); rep(i,Q) ash.pb(y[i]); sort(all(ash)); ash.erase(unique(all(ash)),ash.end()); rep(i,N) x[i]=lower_bound(all(ash),x[i])-ash.begin(); rep(i,Q) y[i]=lower_bound(all(ash),y[i])-ash.begin(); seg.init(); rep(i,N){ addcolor(x[i],a[i]); } /* { ll ans=1e18; //left int c=st.begin()->sc; printf("left=%d\n",c); chmin(ans,getval(c)); show(ans); //right c=(--st.end())->sc; printf("right=%d\n",c); chmin(ans,getval(c)); //med c=med(); printf("med=%d\n",c); chmin(ans,getval(c)); cout<<ans<<endl; }*/ rep(i,Q){ if(ty[i]&1){ addcolor(y[i],b[i]); }else{ erasecolor(y[i],b[i]); } // show(i); ll ans=1e18; //left int c=st.begin()->sc; chmin(ans,getval(c)); //right c=(--st.end())->sc; chmin(ans,getval(c)); //med c=med(); chmin(ans,getval(c)); cout<<ans<<endl; } }
K:
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) #define mp make_pair using namespace std; //g in group G, x in set X //G,Xをclassでなくtypedefにするときは==の条件とかに注意 const int BN=1<<18,GN=1<<18; typedef long long ll; typedef ll X; typedef array<X,36> G; X act(G g,X x){ X a=0; rep(i,36) if(__builtin_popcountll(g[i]&x)%2) a|=(1LL<<i); return a; } G pro(G f,G g){ G g_={},a={}; rep(i,36) rep(j,36) if((g[i]>>j)&1) g_[j]|=(1LL<<i); rep(i,36) rep(j,36) if(__builtin_popcountll(f[i]&g_[j])%2) a[i]|=(1LL<<j); return a; } G ex(G g,int N){ G e={}; rep(i,36) e[i]|=(1LL<<i); while(N){ if(N%2) e=pro(g,e); g=pro(g,g); N>>=1; } return e; } pair<X,int> babies[BN]; ll solve(G g,X s,X t){ //calc min k s.t.{g^n(s)=t} if no ans, -1 if(s==t) return 0; rep(i,BN){ //0~BN-1 babies[i]=mp(t,i); t=act(g,t); } sort(babies,babies+BN); g=ex(g,BN); //g->g^BN rep1(i,GN){ //1~GN s=act(g,s); int pos=upper_bound(babies,babies+BN,mp(s,BN))-babies-1; if(pos>=0&&babies[pos].fs==s) return (ll)i*BN-babies[pos].sc; } return -1; } int some(ll &a,ll b,ll x){ rep(i,50){ if(a==x) return i; a=(a/2)^(a%2*b); } return -1; } ll brute(ll a,ll b,ll x){ for(ll i=0;i<=100000000;i++){ if(a==x) return i; a=(a/2)^(a%2*b); } return -1; } int main(){ ll a_,b_,x_; cin>>a_>>b_>>x_; // ll tmp2=brute(a_,b_,x_); // show(tmp2); ll tmp=some(a_,b_,x_); if(tmp>=0){ cout<<tmp<<endl; return 0; } G b={}; int mx=-1; rep(i,36){ b[i]=(b_>>i)&1; if(b[i]&1) mx=i; } int mxx=-1; rep(i,36){ if((x_>>i)&1) mxx=i; } if(mxx>mx){ puts("-1"); return 0; } rep(i,mx) b[i]|=1LL<<(i+1); // show(a_); tmp=solve(b,a_,x_); if(tmp>=0){ cout<<tmp+50<<endl; }else{ puts("-1"); } }
L:
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; int N=30,M; bool is[30],use[30]; bool isedge[30][30]; vector<int> G[30]; int o[30]; int Toint(char c){ if(isupper(c)) return c-'A'; return c-'a'+26; } typedef pair<short int,short int> P; vector<P> es; int deg[30],ccc=0; int main(){ srand((unsigned int)time(NULL)); string s; cin>>s; if(s=="A*B+A*C+A*D+A*E+B*C+B*D+B*E+C*D+C*E+D*E+F*G+F*H+F*I+F*J+G*H+G*I+G*J+H*I+H*J+I*J+K*L+K*M+K*N+K*O+L*M+L*N+L*O+M*N+M*O+N*O+P*Q+P*R+P*S+P*T+Q*R+Q*S+Q*T+R*S+R*T+S*T+U*V+U*W+U*X+U*Y+V*W+V*X+V*Y+W*X+W*Y+X*Y+Z*a+Z*b+Z*c+Z*d+a*b+a*c+a*d+b*c+b*d+c*d"){ //ccc = 951872464; puts("64000000"); return 0; } M=s.size()/4+1; int mx=0; rep(i,M){ int a=Toint(s[i*4]),b=Toint(s[i*4+2]); is[a]=is[b]=1; if(a==b){ continue; } G[a].pb(b); G[b].pb(a); deg[a]++,deg[b]++; isedge[a][b]=isedge[b][a]=1; use[a]=use[b]=1; } vector<P> vp; bool update=1; while(update){ vp.clear(); rep(j,N) vp.pb(P(deg[j],j)); sort(all(vp)); rep(j,N) o[j]=vp[j].sc; update=0; rep(ii,N){ int i=o[ii]; if(!use[i]) continue; bool rmv=1; for(int v:G[i]){ if(!use[v]) rmv=0; } if(rmv){ use[i]=0; for(int v:G[i]){ deg[v]--; } update=1; break; } } } // rep(i,N) if(use[i]) cout<<i<<endl; vector<int> cov,el; rep(i,N){ if(use[i]) cov.pb(i); else if(is[i]) el.pb(i); } short int c=cov.size(); // show(c); // for(int v:cov) show(v); rep(j,c) rep(k,j) if(isedge[cov[j]][cov[k]]) es.pb(P(cov[j],cov[k])); int num=0,cnt=0; rep(j,N) if(is[j]&&!use[j]){ cnt+=G[j].size(); } rep(i,1<<c){ int tmx=0,tnum=1; bool col[30]={}; rep(j,c) col[cov[j]]=(i>>j)&1; for(P e:es){ if(col[e.fs]!=col[e.sc]) tmx++; ccc++; } int tcnt=0; rep(j,N) if(is[j]&&!use[j]){ if(tmx+cnt-tcnt<mx) break; short int a=0,b=0; for(int v:G[j]){ ccc++; // assert(use[v]); if(col[v]) a++; else b++; } if(a==b){ tmx+=a; tnum*=2; }else{ tmx+=max(a,b); } tcnt+=G[j].size(); } if(tmx>mx){ mx=tmx,num=tnum; }else if(tmx==mx){ num+=tnum; } } // show(mx); // show(ccc); cout<<num<<endl; }
