World Code Sprint #4 2/2
後半の3問
Gridland Provinces
考えられる文字列はO(N^2)通りなので、それらを列挙してsortしてuniqueしたい。
しかし普通にやるとO(N^3logN)とかになってTLEするので、代わりにローリングハッシュで求めたハッシュ値を列挙する。
O(N^2)でハッシュ値を列挙するのは頑張ればいける。あとは前述の通りsortしてuniqueすればO(N^2logN)で勝利。
...と思ったが、最後のケースだけWAする。mod 2^64は簡単に衝突を起こせるみたいな記事を昔どこかでみた気がしたので、別の値でmodをとった。
具体的には、10^9程度の素数でmodをとる(ただし、10^9+7進数でローリングハッシュしているので、10^9+7は避ける)。
10^9程度だと普通に衝突するので、複数の素数に対してmodをとって、それらを要素とするベクトルをその文字列に対するハッシュ値とした(中国剰余定理的に)
#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;} typedef unsigned long long ull; const ull p=1000000007; const ull m[2]={1000000009,1000000033}; int N; char S[2][610]; ull power[2010]; ull hll[2][610],hlr[2][610],hrl[2][610],hrr[2][610]; void solve(){ scanf("%lld",&N); rep(i,2)scanf("%s",S[i]); vector<ull>vec[2]; rep(t0,2){ power[0]=1; rep(i,2000)power[i+1]=power[i]*p%m[t0]; rep(t1,2){ rep(t2,2){ memset(hll,0,sizeof(hll));memset(hlr,0,sizeof(hlr));memset(hrl,0,sizeof(hrl));memset(hrr,0,sizeof(hrr)); rep(i,N){ rep(j,2){ hll[j][i+1]=(hll[j][i]*p+S[j][i])%m[t0]; hlr[j][i+1]=(hlr[j][i]+S[j][i]*power[i])%m[t0]; } } for(int i=N-1;i>=0;i--){ rep(j,2){ hrr[j][i]=(hrr[j][i+1]*p+S[j][i])%m[t0]; hrl[j][i]=(hrl[j][i+1]+S[j][i]*power[N-1-i])%m[t0]; } } rep(i,N){ ull h=(hll[0][i+1]+hlr[1][i+1]*power[i+1])%m[t0]; vec[t0].pb((h+hrr[1][i+1]*power[(i+1)*2]+hrl[0][i+1]*power[N+i+1])%m[t0]); reps(j,i+1,N){ h=(h+S[1][j]*power[j*2+1-(j-i)%2])%m[t0]; h=(h+S[0][j]*power[j*2+(j-i)%2])%m[t0]; vec[t0].pb((h+hrr[1-(j-i)%2][j+1]*power[(j+1)*2]+hrl[(j-i)%2][j+1]*power[N+j+1])%m[t0]); } } rep(i,N)swap(S[0][i],S[1][i]); } rep(i,2)reverse(S[i],S[i]+N); } } vector<pair<ull,ull>>v; rep(i,vec[0].size())v.pb(pair<ull,ull>(vec[0][i],vec[1][i])); sort(all(v));v.erase(unique(all(v)),v.end()); cout<<v.size()<<endl; } signed main(){ int T; scanf("%lld",&T); while(T--)solve(); return 0; }
Robanukkah Tree
僕の想像力では正多面体を想像できないので、つらかった(正六面体だけは手元にルービックキューブがあったのでちょっと嬉しかった)
正n面体をk色で塗る組み合わせの数を求めたくなる。そのために、まずは正n面体をk色以下で塗る組み合わせの数を求める。ポリアの数え上げ定理(?)みたいなやつで数えてたけど、正6面体をやっているときに無理だと悟ったので、調べたら普通に公式が出てきた。k色以下で塗る組み合わせの数を求められれば、dpをすることでちょうどk色で塗る組み合わせの数がわかる。
上記の組み合わせの数さえわかれば、木dpができる。dp[v][p][k]:=頂点vの親ノードに正p面体が置かれていて、k色に塗られているとき、頂点vを根とする部分木に配置する方法の数、とする。ある頂点について、どの正多面体を置くか、何色で塗るか、を決めると、それぞれの子ノードは独立だから、子のdpの値を掛け合わせたものを足せばいい。
#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;} const int mod=1000000009; int mod_pow(int n,int m){ int ret=1; while(m){ if(m&1)ret=ret*n%mod; n=n*n%mod; m>>=1; } return ret; } int fact[222222],inv[222222]; int C(int n,int k){ return fact[n]*inv[k]%mod*inv[n-k]%mod; } int func(int n,int k){ if(n==4){ return k*k*(k*k+11)/12; } if(n==6){ return k*k*(k+1)*(k*k*k-k*k+4*k+8)/24; } if(n==8){ return k*k*(k*k*k*k*k*k+17*k*k+6)/24; } if(n==12){ return mod_pow(k,4)*(mod_pow(k,8)+15*k*k+44)%mod*mod_pow(60,mod-2)%mod; } return k*k*k*k*(mod_pow(k,16)+15*mod_pow(k,6)+20*mod_pow(k,4)+24)%mod*mod_pow(60,mod-2); } int fs[5]={4,6,8,12,20}; int dp[5][21]; int N,K,F; bool ex[5]; vint G[50000]; int memo[50000][6][21]; int dfs(int v,int p,int k){ if(K-k<=0)return 0; int &ret=memo[v][p][k]; if(ret!=-1)return ret; ret=0; for(int i=0;i<5;i++){ if(!ex[i]||i==p)continue; for(int j=1;j<=fs[i];j++){ if(K-k<j)break; int tmp=dp[i][j]*C(K-k,j)%mod; for(auto u:G[v]){ tmp=tmp*dfs(u,i,j)%mod; } ret=(ret+tmp)%mod; } } return ret; } signed main(){ fact[0]=1; reps(i,1,222222)fact[i]=fact[i-1]*i%mod; inv[222222-1]=mod_pow(fact[222222-1],mod-2); for(int i=222222-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod; rep(i,5){ for(int j=1;j<=fs[i];j++){ dp[i][j]=func(fs[i],j); for(int k=1;k<j;k++){ dp[i][j]=(dp[i][j]-C(j,k)*dp[i][k]%mod+mod)%mod; } } } scanf("%lld%lld%lld",&N,&K,&F); rep(i,F){ int f;scanf("%lld",&f); ex[find(fs,fs+5,f)-fs]=true; } for(int i=1;i<N;i++){ int p; scanf("%lld",&p); p--; G[p].pb(i); } memset(memo,-1,sizeof(memo)); cout<<dfs(0,5,0)<<endl; return 0; }
Vertical Paths
解ける気がしない。ほんのちょっと考察したり部分点とったりしたので、それを書きます。
まず、木のノードの中には不要な頂点(その点を消して縮約してもokな頂点)があるので、それらを消すと、O(M)頂点になる(具体的には3M以下)。
これはまあなんとなくそうなりそうだなあという感じだが、一応帰納的に示したりできる(多分)
1時間考えたのにこれだけしか考えられなくて、本当に虚しくなった(最小費用流を流す方法を考えたんですけど、めちゃくちゃ嘘だったのでやめた。ただ、最小費用流で解けるらしい。やり方がまったくわからなくてつらい)
この問題以外を全部ACした時点で100位以内には入れるかなあと思ったが、終了30分前くらいで100位落ちしたので急遽全探索(2^M通り全部試す)をやった。なぜか45点ももらえたのでラッキーだった。
書きかけの縮約の実装と、部分点を取るやつがあるコード(泣)
#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;} int N,M; int A[1000],B[1000],C[1000]; int par[20][500000],dep[500000],parcost[500000]; vpint G[500000]; int mark[500000]; void init(){ par[0][0]=-1; dep[0]=0; vint v(1,0); for(int i=0;i<v.size();i++){ int u=v[i]; rep(j,G[u].size()){ int w,c;tie(w,c)=G[u][j]; if(w==par[0][u])continue; par[0][w]=u; parcost[w]=c; dep[w]=dep[u]+1; v.pb(w); } } rep(i,19)rep(j,N){ if(par[i][j]==-1)par[i+1][j]=-1; else par[i+1][j]=par[i][par[i][j]]; } } int lca(int u,int v){ if(dep[u]<dep[v])swap(u,v); rep(i,20)if((dep[u]-dep[v])>>i&1)u=par[i][u]; if(u==v)return u; for(int i=19;i>=0;i--)if(par[i][u]!=par[i][v])u=par[i][u],v=par[i][v]; return par[0][u]; } void solve(){ scanf("%lld%lld",&N,&M); assert(M<=16); rep(i,N)G[i].clear(); rep(i,N-1){ int a,b,c; scanf("%lld%lld%lld",&a,&b,&c); a--;b--; G[a].pb({b,c}); G[b].pb({a,c}); } init(); memset(mark,0,sizeof(mark)); rep(i,M){ scanf("%lld%lld%lld",&A[i],&B[i],&C[i]); A[i]--;B[i]--; chmax(mark[B[i]],2); chmax(mark[A[i]],1); } rep(i,M)rep(j,M){ int p=lca(B[i],B[j]); if(dep[p]<dep[A[i]]||dep[p]<dep[A[j]])continue; if(dep[p]!=dep[A[i]]||dep[p]!=dep[A[j]])chmax(mark[p],2); else chmax(mark[p],1); p=lca(B[i],A[j]); if(p==A[j]&&dep[A[i]]<dep[A[j]]){ chmax(mark[A[j]],2); } } vector<tuple<int,int,int>>es; vint vs; rep(i,N){ if(mark[i]!=2)continue; int v=i,c=1001001001; do{ chmin(c,parcost[v]); v=par[0][v]; }while(!mark[v]); es.pb(make_tuple(v,i,c)); vs.pb(v);vs.pb(i); } sort(all(vs));vs.erase(unique(all(vs)),vs.end()); rep(i,M){ A[i]=lower_bound(all(vs),A[i])-vs.begin(); B[i]=lower_bound(all(vs),B[i])-vs.begin(); } rep(i,es.size()){ get<0>(es[i])=lower_bound(all(vs),get<0>(es[i]))-vs.begin(); get<1>(es[i])=lower_bound(all(vs),get<1>(es[i]))-vs.begin(); } rep(i,N)G[i].clear(); int to[100],co[100]; int ans=0; rep(i,1<<M){ memset(to,0,sizeof(to)); memset(co,0,sizeof(co)); rep(j,es.size()){ int u,v,c; tie(u,v,c)=es[j]; to[v]=u; co[v]=c; } int val=0; rep(j,M){ if(!(i>>j&1))continue; int v=B[j]; while(v!=A[j]){ co[v]--; v=to[v]; } val+=C[j]; } bool ok=true; rep(j,vs.size())if(co[j]<0)ok=false; if(ok)chmax(ans,val); } cout<<ans<<endl; } signed main(){ int T; scanf("%lld",&T); while(T--)solve(); }
