Presentation (AOJ2453) - sigma425のブログ

考えれば解ける系の綺麗な問題.
でも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;
}