World Code Sprint #4 1/2
出ました。今回も無事賞金を得られたのでうれしい。今後も毎月開催してくれると財布が潤うので、よろしくお願いします。
Minimum Distances
自明
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>pint; typedef vector<int>vint; typedef vector<pint>vpint; #define pb push_back #define mp make_pair #define fi first #define se second #define all(v) (v).begin(),(v).end() #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;} template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;} signed main(){ int n;cin>>n; vint a(n);rep(i,n)cin>>a[i]; int ans=1001001001; rep(i,n)reps(j,i+1,n){ if(a[i]==a[j])chmin(ans,j-i); } if(ans==1001001001)cout<<-1<<endl; else cout<<ans<<endl; return 0; }
Equal Stacks
ある時点で各stackの高さがh1,h2,h3だったとする。一般性を失わずh1>=h2,h3と仮定できる(言い方がかっこいいから一回書いてみたかった)
h1=h2=h3なら、完成。そうでないなら、もう答えをh1にできる見込みがないので、積極的にstack1のtopをpopしていける。
上記の操作をh1=h2=h3となるまで続ければok。
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>pint; typedef vector<int>vint; typedef vector<pint>vpint; #define pb push_back #define mp make_pair #define fi first #define se second #define all(v) (v).begin(),(v).end() #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;} template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;} signed main(){ int n[3];rep(i,3)cin>>n[i]; vint a[3]; int s[3]; rep(i,3){ a[i].resize(n[i]); rep(j,n[i])cin>>a[i][j]; reverse(all(a[i])); s[i]=accumulate(all(a[i]),0ll); } while(true){ if(s[0]==s[1]&&s[1]==s[2]){ cout<<s[0]<<endl; return 0; } int i=max(pint(s[0],0),max(pint(s[1],1),pint(s[2],2))).se; s[i]-=a[i].back(); a[i].pop_back(); } return 0; }
A or B
とりあえず、A|B=Cとなるように操作をする(まだA,Bを最小にしようとはしない)。
ある桁iを見てるとき、A[i]|B[i]=C[i]ならok。
そうでないとき、C[i]=0ならA[i]=B[i]=0となるように操作する。C[i]=1ならB[i]=1とする。(A[i]=1としてもいいけど闇が生えるのでB[i]=1とする)
この時点で操作回数が足りなくなったら不可能。そうでないならとりあえず可能なので、A,Bを最小化していく。
できるだけ上の桁を0にしたいので、上の桁から変更していく。
ある桁iを見る。C[i]=0ならA[i]=B[i]=0となっているので、これ以上何もしなくてもいい。
C[i]=1だとする。A[i]=0,B[i]=1なら何もしない。A[i]=1,B[i]=0なら、A[i]=0,B[i]=1とする。A[i]=1,B[i]=1ならA[i]=0とする。(もちろん、操作回数が許容範囲なら)
まあ操作partは自明だけど、16進と2進の変換とかいろいろめんどくさかったので最初からbit列を渡してくれと思った。
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>pint; typedef vector<int>vint; typedef vector<pint>vpint; #define pb push_back #define mp make_pair #define fi first #define se second #define all(v) (v).begin(),(v).end() #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;} template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;} string L="0123456789ABCDEF"; void convert(vint &A,string &a){ reverse(all(a)); rep(i,a.size()){ int t=find(all(L),a[i])-L.begin(); rep(j,4)A[i*4+j]=t>>j&1; } reverse(all(A)); } void inverse_convert(string &a,vint &A){ reverse(all(A)); a=""; bool flag=false; for(int i=A.size()/4-1;i>=0;i--){ int t=0; rep(j,4)t+=A[i*4+j]<<j; if(t||(!t&&(flag||!i))){ flag=true; a.pb(L[t]); } } } int N,K; void solve(){ cin>>K; string a,b,c; cin>>a>>b>>c; N=max(a.size(),max(b.size(),c.size()))*4; vint A(N),B(N),C(N); convert(A,a); convert(B,b); convert(C,c); rep(i,N){ if((A[i]|B[i])==C[i])continue; if(C[i]){ B[i]=1;K--; } else{ if(A[i]){ A[i]=0;K--; } if(B[i]){ B[i]=0;K--; } } } if(K<0){ cout<<-1<<endl; return; } rep(i,N){ if(C[i]==0)continue; if(A[i]==1&&B[i]==1&&K){ A[i]=0;K--; } else if(A[i]==1&&B[i]==0&&K>1){ A[i]=0;B[i]=1;K-=2; } } inverse_convert(a,A); inverse_convert(b,B); cout<<a<<endl; cout<<b<<endl; } signed main(){ int Q; scanf("%lld",&Q); while(Q--)solve(); return 0; }
Roads in HackerLand
任意の非負整数nに対して、2^n>2^0+2^1+...+2^(n-1)であるから、できるだけ指数部の小さい辺だけを通っていきたい。
グラフの最小全域木を取ると、最小全域木に含まれない辺は使う必要がないことがわかる。クラスカル法の過程である辺iを見ているとき、すでにu_iとv_i(辺iの両端)が連結なら、i未満の辺のみを使ってu_iからv_iに到達できる。冒頭の不等式より、辺iを使うよりお得なので、辺iは不要。
入力が木の場合は自明に解けるので、終了。
#include<bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int>pint; typedef vector<int>vint; typedef vector<pint>vpint; #define pb push_back #define mp make_pair #define fi first #define se second #define all(v) (v).begin(),(v).end() #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) template<class T,class U>inline void chmin(T &t,U f){if(t>f)t=f;} template<class T,class U>inline void chmax(T &t,U f){if(t<f)t=f;} struct UF{ vint par; void init(int n){ par.resize(n); rep(i,n)par[i]=i; } int find(int x){ return x==par[x]?x:par[x]=find(par[x]); } void unite(int x,int y){ x=find(x);y=find(y); par[y]=x; } }; int N,M; vpint G[100000]; int ans[10000000]; int sz[100000]; void dfs(int v,int p){ sz[v]=1; rep(i,G[v].size()){ int u,j; tie(u,j)=G[v][i]; if(u==p)continue; dfs(u,v); sz[v]+=sz[u]; int tmp=sz[u]*(N-sz[u]); while(tmp){ ans[j]+=tmp&1; tmp>>=1; j++; } } } signed main(){ scanf("%lld%lld",&N,&M); vector<tuple<int,int,int>>es; rep(i,M){ int a,b,c; scanf("%lld%lld%lld",&a,&b,&c); a--;b--; es.pb(make_tuple(c,a,b)); } sort(all(es)); UF uf;uf.init(N); rep(i,M){ int a,b,c; tie(c,a,b)=es[i]; if(uf.find(a)==uf.find(b))continue; uf.unite(a,b); G[a].pb(pint(b,c)); G[b].pb(pint(a,c)); } dfs(0,-1); int u=0; rep(i,1000000){ if(ans[i]>1){ ans[i+1]+=ans[i]>>1; ans[i]&=1; } if(ans[i])u=i; } for(int i=u;i>=0;i--){ printf("%lld",ans[i]); } puts(""); return 0; }
Roads in HackerLandがそこそこ好き。
