Presentation (AOJ2453)
問題:
Presentation | Aizu Online Judge
考えれば解ける系の綺麗な問題.
でも1100はない気がするなあ(900くらい?)
一度ある木をコピーすると,その木を組み合わせたようなものしか出来ない.その木Xを使ってできるかの判定は根から順にdfsをすればできる(実際今どの頂点か+今Xでどの頂点にいるか を持つ). O(N)
どういうものがありえるか考える.N=200000くらいなんで選択肢がいっぱいあると困る.
適当に切った上の部分:正しいけど可能性がありすぎる
各頂点を根とする部分木:N個ある.ただし,辺の個数が元の木の約数じゃなきゃいけない ということを考えると結構減る がまだ不十分.
最も深い点(のうちの任意のひとつ) (vとする)の先祖たちを根とする部分木:これも最大N個あるが,明らかに辺の個数がdistinctになるので,高々約数個しか考えなくていい.N=200000までだと約数の個数は160が最大なので間に合う.
上記のやつだけでいいことはなぜわかるかというと,木Xを任意に取ってきて,それがvをどう覆うか考える.この時,Xの根に対応する頂点をrとする.Xがrを根とする部分木になってることを示せばOK.なってないとするとある頂点wがありXに覆われていない.従ってその頂点からさらにXが生えていることになるが,これはvが深さが最大であることに矛盾する.
で,コピーしてコピーして・・・みたいなグラフは結局どう考えるかというと,今やったことをXそれぞれに対してやってもいいけどかなりTLEギリギリっぽい.実は今OKと判定した木X,Yに対しては,「XからYが作れる」⇔「Xの辺の個数がYの辺の個数の約数」となる.(→は当たり前.←は,Xでのさっきのuを取ってくると,Yでそこいかが綺麗に埋まらなければおかしいことがわかるので)
なのでDAGが簡単に作れて,dpができます(最大160^2)
全体でO(Nσ(N) + σ(N)^2)
ちなみに,グラフ作るときにdfsするとスタックオーバーフローするので,魔法を使いましょう
#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 BEGIN_STACK_EXTEND(size) void * stack_extend_memory_ = malloc(size);void * stack_extend_origin_memory_;char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);*stack_extend_dummy_memory_ = 0;asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024)); #define END_STACK_EXTEND asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));free(stack_extend_memory_); using namespace std; int N; vector<int> G[200001]; int par[200001],dep[200001],num[200001]; void makegraph(){ string s; cin>>s; int v=-1; for(char c:s){ if(c=='('){ if(v>=0) G[v].pb(N),dep[N]=dep[v]+1; par[N]=v; v=N; N++; }else{ num[v]=1; for(int u:G[v]) num[v]+=num[u]; v=par[v]; } } } bool dfs(int v,int w,int s){ if(G[v].size()==0&&G[w].size()==2) return false; if(G[v].size()==0&&G[w].size()==0) return true; if(G[v].size()==2&&G[w].size()==2) return dfs(G[v][0],G[w][0],s)&&dfs(G[v][1],G[w][1],s); return dfs(v,s,s); } bool ok(int v){ return dfs(0,v,v); } int main(){ BEGIN_STACK_EXTEND(128*1024*1024); makegraph(); vector<int> ds; int v=0; rep(i,N) if(dep[i]>dep[v]) v=i; v=par[v]; while(v>=0){ if((N-1)%(num[v]-1)==0){ if(ok(v)) ds.pb(num[v]-1); } v=par[v]; } int K=ds.size(); int dp[161]={}; rep(i,K) dp[i]=1e9; dp[0]=0; rep(i,K){ rep(j,i){ if(ds[i]%ds[j]==0){ chmin(dp[i],dp[j]+ds[i]/ds[j]-1); } } } cout<<dp[K-1]<<endl; END_STACK_EXTEND; }