AOJ2453 Presentation

問題:
Presentation | Aizu Online Judge

概要:
二分木をコピペして作る

解法:
面白かったけど構文解析パート必要ない。あと配列サイズ難しい。

重要なのは,
切り貼りすると1番深いところの深さが元のやつより増加するので,最終的に1番深いところ(どれでもいい)に注目すると,それを含んで貼り付けたやつは部分木丸ごとであること(日本語難しい)
v以下の部分木を貼り付けて作れる必要条件にsz[v] | sz[root] (葉は含めない)があり,また1番深いところから根までに候補がO(N)通りありsz[root]の約数なのでO(sqrt(N))個
これらについてそれぞれO(N)かけて最終的な木が作れるかチェックする ここまで(O(Nsqrt(N)))
また調べる過程でそれぞれの候補について,それより下を使ってそれ自体が作れるかを調べ直す必要はない(最終的に1番深いやつはコピペする前でも1番深いところにあったりいい感じになってる)
あとは普通のdp(二重だけどO(N))

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define MX 400010

struct node{
    int sz;
    bool lf;
    node *p,*l,*r;
    node():sz(1),lf(0),p(NULL),l(NULL),r(NULL){}
};

node pool[MX];
int now;

inline node *get(){return &pool[now++];}

int ma;
node *st;

node *read(const string& s,node *par,int& p,int d){
    node *v=get();
    if(par)v->p=par;
    if(s[p+1]==')'){
	v->sz=0,v->lf=1;
	p+=2;
	if(ma<d)ma=d,st=v;
	return v;
    }
    ++p;
    v->l=read(s,v,p,d+1);
    v->r=read(s,v,p,d+1);
    ++p;
    v->sz+=v->l->sz+v->r->sz;
    return v;
}

bool ok(node* v,node* v2,node* gen){
    if(v->lf)return v2->lf;
    node *lc=v2->l,*rc=v2->r;
    if(v2->lf)lc=gen->l,rc=gen->r;
    return ok(v->l,lc,gen) && ok(v->r,rc,gen);
}

int sz,k;
char in[MX];
string s;
node *root;
vector<node*> sub;
vector<int> vec,dp;

main(){
    scanf("%s",in);
    s=in;
    root=read(s,NULL,k,0);
    sz=root->sz;
    while(st->p){
	if(sz%st->p->sz==0)
	    sub.pb(st->p);
	st=st->p;
    }
    for(auto &v:sub)if(ok(root,v,v))
	vec.pb(v->sz);
    dp.resize(vec.size(),200000);
    dp[0]=0;
    rep(i,vec.size())rep(j,i)
	if(vec[i]%vec[j]==0)
	    dp[i]=min(dp[i],dp[j]+vec[i]/vec[j]-1);
    printf("%d\n",dp.back());
}