読者です 読者をやめる 読者になる 読者になる

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;
}