CODE_FESTIVAL 2015 本選(コンテスト)
非コンテスト編は一個前です.
A~E:解く.
F:見た時に去年の国内予選のサイコロを思い出した.とりあえず変数を置いて式を書くと全部の辺を使う個数が確定したので,ちゃんと0以上になってるか,連結かどうかなどを見ればOK.出したらWAったのでGを見る.
G:subtreeは区間になるからdp[i][j]=[i,j)を木にする方法 でいけるな→あれこれ更新でO(N^4)じゃね?→後ろから見れば大丈夫だったけど書きにくい→バグる→dp[i][j]=[i,j)を(正しく)森にする方法で書きなおしてAC.
Fを見る.あれこれデバグ出力消してねえじゃん→出す→まだ消してなかった・・・消す→AC あってたんかーい.
H,I,Jを見る.I,J考えてもわからないうちにHがわかりはじめたのでHを実装したらバグった,10分前くらいにやっとバグが取れてAC.おしまい.
別にわざわざ記事わけるほどじゃなかった.
Iは帰ってからやった.発想は簡単だし実装も簡単なはずなんだけどバグった.BIT毎回indexミスってる気がするし一度ちゃんと理解しないと(え,してないの).
Jはまだわかってない・・・(解説聞いてない)
コード
F:
#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; int main(){ ll a[7]; rep(i,7) cin>>a[i]; if(accumulate(a,a+7,0)==1&&a[0]==1){ puts("YES"); return 0; } if(a[0]<2){ puts("NO"); return 0; } ll x[14]={}; rep(k,7) x[k]=a[k]*2; x[0]-=2; rep(k,7) x[k+7]=x[k]; bool can=1; ll e[7]; rep(k,7) e[k]=(x[0+k]+x[1+k]-x[2+k]+x[3+k]-x[4+k]+x[5+k]-x[6+k])/2; rep(k,7) if(e[k]<0) can=0; // rep(k,7) cout<<e[k]<<" "; int L=0,R=6; while(L<7&&e[L]>0) L++; while(R>=0&&e[R]>0) R--; // show(L); // show(R); if(L<R){ for(int x=L;x<R;x++) if(e[x]>0) can=0; } if(can) puts("YES"); else puts("NO"); }
G:
#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; ll mod=1e9+7; int N,c[256]; ll dp[257][257]; void add(ll &x,ll y){ x+=y; x%=mod; } int main(){ cin>>N; rep(i,N) cin>>c[i]; if(c[0]!=1){ puts("0"); return 0; } rep(i,N+1) dp[i][i]=1; for(int len=1;len<=N;len++){ for(int l=0;l+len<=N;l++){ int r=l+len; for(int i=l+1;i<r;i++){ if(c[l]<c[i]) add(dp[l][r],dp[l+1][i]*dp[i][r]); } add(dp[l][r],dp[l+1][r]); // printf("dp[%d][%d]=%lld\n",l,r,dp[l][r]); } } cout<<dp[1][N]<<endl; }
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 pair<int,int> P; const int p2=1<<17; int N,M; int sega[p2*2],segb[p2*2],a[100000],b[100000]; int inf=1e9; vector<P> vc; int mx(int a,int b,int l,int r,int k,int* seg){ if(b<=l||r<=a) return -inf; if(a<=l&&r<=b) return seg[k]; return max(mx(a,b,l,(l+r)/2,k*2,seg),mx(a,b,(l+r)/2,r,k*2+1,seg)); } void update(int x,int v,int* seg){ x+=p2; if(seg[x]>v) return; seg[x]=v; while(x>1){ x/=2; chmax(seg[x],max(seg[x*2],seg[x*2+1])); } } int main(){ rep(i,p2*2) sega[i]=segb[i]=-inf; update(0,0,sega);update(0,0,segb); cin>>N>>M; rep(i,N){ cin>>a[i]>>b[i]; vc.pb(P(a[i],a[i]+b[i])); } sort(all(vc)); rep(i,N) a[i]=vc[i].fs,b[i]=vc[i].sc; rep(i,N){ int L=a[i],R=b[i]; int val=0; int mx1=mx(0,L+1,0,p2,1,sega); chmax(val,mx1+R-L); int mx2=mx(L,R+1,0,p2,1,segb); chmax(val,mx2+R+L); update(R,val,sega); update(R,val-2*R,segb); } cout<<mx(0,M+1,0,p2,1,sega)<<endl; }
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; int N,Q; typedef pair<int,int> P; vector<int> G[100000],ash; int l[100000],h[100000],mx[100000]; int dfs2(int v,int d){ h[v]=d; int m=h[v]; for(int u:G[v]){ chmax(m,dfs2(u,d+l[u])); } mx[v]=m; return m; } int bit[100001]; int sum(int i){ int s=0; while(i>0){ s+=bit[i]; i=(i&(i-1)); } return s; } void add(int i,int x){ while(i<=N){ bit[i]+=x; i+=(i&-i); } } int a[100000]; void dfs(int v,int p){ if(p>=0) add(mx[v]+1,-1); for(int u:G[v]) if(u!=p){ add(mx[u]+1,1); } // show(v); // rep(i,N) cout<<sum(i+1)-sum(i)<<" "; // puts(""); // show(sum(N)-sum(h[v])); chmin(a[h[v]],sum(N)-sum(h[v]+1)); for(int u:G[v]){ if(u==p) continue; dfs(u,v); } for(int u:G[v]) if(u!=p){ add(mx[u]+1,-1); } if(p>=0) add(mx[v]+1,1); } int main(){ cin>>N; rep(i,N) cin>>l[i]; rep1(i,N-1){ int p; cin>>p; p--; G[p].pb(i); } dfs2(0,l[0]); rep(i,N) ash.pb(h[i]); sort(all(ash));ash.erase(unique(all(ash)),ash.end()); rep(i,N) h[i]=lower_bound(all(ash),h[i])-ash.begin(); rep(i,N) mx[i]=lower_bound(all(ash),mx[i])-ash.begin(); // rep(i,N) show(h[i]); // rep(i,N) show(mx[i]); rep(i,N) a[i]=1e9; dfs(0,-1); cin>>Q; rep(i,Q){ int x; cin>>x; if(binary_search(all(ash),x)){ x=lower_bound(all(ash),x)-ash.begin(); // show(x); cout<<a[x]<<endl; }else{ puts("-1"); } } }