AOJ2636 Distance Sum

問題:
Distance Sum | Aizu Online Judge

ブログ書くのめんどくさい.
問題文はとても読みやすいので読んでください.





解説:

普通に順番に1からNまで追加してシミュレーションします.

まず, i番目を追加した時, i-1番目の時和を最小化する頂点(vとする)とのパス上に新しい候補点がありそう.

vからそっち方向に辺を1つ移動した点に変えた時のcostの変化を考えると, それよりこっち側の部分木の頂点数と向こう側の頂点数(今まで追加された分)(それぞれnum1, num2とする)とcost * (num2 - num1 + 1)減る(1は新しい頂点の分) costは全体にかかるので難しい計算はしなくてよい. i-1番目まででの最小性より num2 - num1 <= 0になっている. num1 + num2 = i - 1 また, 今までの点かlcaっぽいところでnum2 - num1が減少し, 1回変化すると最小となる.

この辺の操作は行き掛け順で管理してsegtreeとかBITとかでサポートするとなんとかなる. (こっちは慣れっぽい)

AOJ-ICPC-favorite

好みが普通すぎて面白く無いかもしれません
現在の難易度でsortします

・500

2333 My friends are small
My friends are small | Aizu Online Judge

・600

2439 Hakone
Hakone | Aizu Online Judge

2336 Spring Tiles
Spring Tiles | Aizu Online Judge

2256 Divide the Cake
Divide the Cake | Aizu Online Judge

・650

1333 Beautiful Spacing
Beautiful Spacing | Aizu Online Judge

2374 RabbitLunch
RabbitLunch | Aizu Online Judge

2376 DisconnectedGame
DisconnectedGame | Aizu Online Judge

・700

1322 ASCII Expression
ASCII Expression | Aizu Online Judge

・750

1197 A Die Maker
A Die Maker | Aizu Online Judge
サイコロが面倒要素以外で活用されているのを初めて見た

1343 Hidden Tree
Hidden Tree | Aizu Online Judge

2445 MinimumCostPath
MinimumCostPath | Aizu Online Judge

・900

1353 Sweet War
Sweet War | Aizu Online Judge

・1000

2291 Brilliant Stars
Brilliant Stars | Aizu Online Judge

2337 Remodeling Plan for Neko-Nabe (tentative)
Remodeling Plan for Neko-Nabe (tentative) | Aizu Online Judge

2617 Air Pollution
Air Pollution | Aizu Online Judge

・1100

1185 Patisserie ACM
Patisserie ACM | Aizu Online Judge

2453 Presentation
Presentation | Aizu Online Judge

2339 問題文担当者は働かない!
Person responsible for problem description don't w | Aizu Online Judge

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

AOJ2338 よくわかる二重魔法

問題:
Intelligible Double Magic | Aizu Online Judge

要約すると、N頂点M辺の無向グラフが与えられるので好きに辺を有向にして(u,v)...uからvにいける ような組を多くせよ、という問題(N<=100,M<=N_C_2)





lowlinkを使って二重辺連結成分分解し重みつき木にしてdpすれば求めることができる
DEGwerが言っていたので考えてみたけど、ループの中身を見るとよくある木dp(O(n^3)と思いきやO(n^2)だった系の要素
(参考:二乗の木 DP - (iwi) { 反省します - TopCoder部)
があるのでO(n^4)->O(n^3)な気がする。違うかも。

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

int n,m;
int szt[110],cmp[110],sz[110];
map<string,int> T;
vector<int> g[110],g2[110];
pii es[5010];
int now,ret;
int vis[110],ord[110],low[110],br[110][110];

void dfs(int v,int p){
    vis[v]=1;
    ord[v]=low[v]=now++;
    for(int &to:g[v])if(to!=p){
	if(!vis[to]){
	    dfs(to,v);
	    low[v]=min(low[v],low[to]);
	    if(ord[v]<low[to])br[v][to]=br[to][v]=1;
	}else low[v]=min(low[v],ord[to]);
    }
}

void dfs2(int v){
    vis[v]=szt[v]=1;
    for(int &to:g[v]){
	if(!vis[to]&&!br[v][to]){
	    dfs2(to);
	    szt[v]+=szt[to];
	}
    }
}

void dfs3(int v,int k){
    sz[now]=k;
    cmp[v]=now;
    vis[v]=1;
    for(int &to:g[v])
	if(!vis[to]&&!br[to][v])
	    dfs3(to,k);
}

int dp[110][110][110],m1[110][110],m2[110][110],wg[110];

void DFS(int v,int p){
    dp[v][sz[v]][sz[v]]=sz[v]*sz[v];
    wg[v]=sz[v];
    for(int &to:g2[v])if(to!=p){
	DFS(to,v);
	for(int i=wg[v];i;--i){
	    for(int j=wg[v];j;--j){
		if(dp[v][i][j]==0)continue;
		for(int k=wg[to];k;--k){
		    int x=m1[to][k];
		    if(x)dp[v][i+k][j]=max(dp[v][i+k][j],dp[v][i][j]+x+j*k);
		    x=m2[to][k];
		    if(x)dp[v][i][j+k]=max(dp[v][i][j+k],dp[v][i][j]+x+i*k);
		}
	    }
	}
	wg[v]+=wg[to];
    }
    rep(i,110)rep(j,110){
	m1[v][i]=max(m1[v][i],dp[v][i][j]);
	m2[v][j]=max(m2[v][j],dp[v][i][j]);
    }
}

main(){
    cin>>n>>m;
    string s;
    rep(i,n)cin>>s,T[s]=i;
    rep(i,m){
	string a,b;
	cin>>a>>b;
	int p=T[a],q=T[b];
	g[p].pb(q);g[q].pb(p);
	es[i]=mp(p,q);
    }
    dfs(0,-1);
    now=0;
    rep(i,n)vis[i]=0;
    rep(i,n)if(!vis[i])dfs2(i);
    rep(i,n)vis[i]=0;
    rep(i,n)if(!vis[i]){
	dfs3(i,szt[i]);
	now++;
    }
    rep(i,m){
	int p=cmp[es[i].first],q=cmp[es[i].second];
	if(p!=q)g2[p].pb(q),g2[q].pb(p);
    }
    DFS(0,-1);
    rep(i,110)rep(j,110)ret=max(ret,dp[0][i][j]);
    cout<<ret<<endl;
}

AOJ2377 ThreeRooks

これで1200+以外は1問以上解いた事になった




概要

X*YのマスにK匹のうさぎがいる。互いに攻撃できないように3個のルークを置く場合の数をmod 10^9+7で求めよ

X,Y<=10^9,K<=10^5



解法

3個同じ所に並んでいる場合

2個並んでいて1個はその範囲にはない

3個が直角に並んでいる場合

を数えると解ける。
1,2個目は普通に求まって, 3個目は気合で平面走査する
平面走査では、区間全体にある値を足す,あるところを0にする,ある範囲の和を求める
が出来ると良いのでよくあるsegment treeを使う(座標圧縮はそんなに面倒でもない)

こういうのはvectorをもらって計算する関数を作っておくと、座標を入れ替えるだけで良くて嬉しみがある

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;++i)

const ll MOD=1000000007;
ll ret,p2,p6;
ll X,Y,K,zan;

inline ll c2(ll x){return x*(x-1)%MOD*p2%MOD;}
inline ll c3(ll x){return x*(x-1)%MOD*(x-2)%MOD*p6%MOD;}
inline void md(ll &x,ll y){x+=y;if(x>=MOD)x-=MOD;}

vector<int> xs;
inline int p(int x){return lower_bound(xs.begin(),xs.end(),x)-xs.begin();}
int sz;
struct segtree{
    vector<ll> dat1, dat2;
    void init(int n_){
	for(sz=1;sz<n_;sz*=2);
	dat1=vector<ll>(sz*2,0);
	dat2=vector<ll>(sz*2,0);  
    }
    void add(int a,int b,ll x,int k=0,int l=0,int r=sz){
	if(b<=l||r<=a)return ;
	if(a<=l&&r<=b)md(dat1[k],x);
	else{
	    md(dat2[k],x*(xs[min(b,r)]-xs[max(a,l)])%MOD);
	    add(a,b,x,k*2+1,l,(l+r)/2);
	    add(a,b,x,k*2+2,(l+r)/2,r);
	}
    }

    ll sum(int a,int b,int k=0,int l=0,int r=sz){
	if(b<=l||r<=a)return 0;
	if(a<=l&&r<=b)return (dat1[k]*(xs[r]-xs[l])+dat2[k])%MOD;
	else{
	    ll res=dat1[k]*(xs[min(b,r)]-xs[max(a,l)]);
	    res+=sum(a,b,k*2+1,l,(l+r)/2);
	    res+=sum(a,b,k*2+2,(l+r)/2,r);
	    return res%MOD;
	}
    }
}seg;

ll calc_23(ll h,ll w,vector<pii>& pt){
    ll s=0,my=h;
    sort(pt.begin(),pt.end());
    for(int i=0;i<pt.size();--my){
	int y=pt[i].fi,j=i;
	while(j<pt.size()&&pt[j].fi==y)++j;
	vector<int> v(j-i);
	for(int k=i;k<j;++k)v[k-i]=pt[k].se;
	md(s,(c3(v[0])+c2(v[0])*(zan-v[0]))%MOD);
	for(int k=1;k<v.size();++k){
	    ll t=v[k]-v[k-1]-1;
	    md(s,c3(t)+c2(t)*(zan-t)%MOD);
	}
	ll t=w-1-v.back();
	md(s,c3(t)+c2(t)*(zan-t)%MOD);
	i=j;
    }
    return (s+(my*c3(w)+(zan-w)*c2(w)%MOD*my))%MOD;
}

ll calc_L(ll h,ll w,vector<pii>& pt){
    sort(pt.begin(),pt.end());
    xs.resize(pt.size()*2);
    rep(i,pt.size()){xs[i*2]=pt[i].se;xs[i*2+1]=pt[i].se+1;}
    xs.pb(0);xs.pb(w);
    sort(xs.begin(),xs.end());
    xs.erase(unique(xs.begin(),xs.end()),xs.end());
    seg.init(xs.size());
    int rr=xs.size()-1;

    ll s=0,la=-1;
    for(int i=0;i<pt.size();){
	int y=pt[i].fi,j=i;
	ll g=seg.sum(0,rr);

	seg.add(0,rr,y-la-1);
	ll ng=seg.sum(0,rr);
	md(s,((w-1)*(g+ng-w)%MOD*(y-la-1)%MOD*p2)%MOD);
	while(j<pt.size()&&pt[j].fi==y)++j;
	vector<int> v(j-i);
	for(int k=i;k<j;++k)v[k-i]=pt[k].se;

	if(v[0]>1)md(s,(v[0]-1)*seg.sum(0,p(v[0]))%MOD);

	for(int k=1;k<v.size();++k){
	    ll t=v[k]-v[k-1]-1;
	    if(t>1)md(s,(t-1)*seg.sum(p(v[k-1]+1),p(v[k]))%MOD);
	}
	ll t=w-1-v.back();
	if(t>1)md(s,(t-1)*seg.sum(p(v.back()+1),rr)%MOD);
	seg.add(0,rr,1);
	for(int k=i;k<j;++k){
	    int l=p(pt[k].se);
	    ll x=seg.sum(l,l+1);
	    seg.add(l,l+1,-x);
	}
	i=j;
	la=y;
    }
    if(la!=h-1){
	ll num=h-1-la,t1=seg.sum(0,rr),t2=(t1+w*(num-1))%MOD;
	md(s,(w-1)*(t1+t2)%MOD*num%MOD*p2%MOD);
    }
    return s;
}

int main(){
    p2=(MOD+1)/2;p6=(MOD+1)/6;
    scanf("%lld%lld%lld",&X,&Y,&K);
    vector<pii> pt(K);
    rep(i,K){
	int x,y;
	scanf("%d%d",&x,&y);
	pt[i]=mp(x,y);
    }
    zan=(X*Y-K)%MOD;
    if(zan<3){puts("0");return 0;}
    ret=c3(zan);
    md(ret,MOD-calc_23(X,Y,pt));
    rep(i,K)swap(pt[i].fi,pt[i].se);
    md(ret,MOD-calc_23(Y,X,pt));
    rep(i,K)swap(pt[i].fi,pt[i].se);
    ret+=calc_L(X,Y,pt);
    rep(i,K)pt[i].fi=X-1-pt[i].fi;
    ret+=calc_L(X,Y,pt);
    printf("%d\n",ret%MOD);
    return 0;
}

AOJ2603 Time Table

バスをm本走らせてn人拾う時の待ち時間の和の最小値を求める問題






とりあえずバス停の場所を時間からひくといつ出発するとちょうどかがわかるので、それをsortしてTiとおく

まず何も考えずに愚直なdpの式を立てると
dp[i][d] = min{0<=j<=i}(dp[j][d-1] + sum{j+1<=k<=i}(t[i]-t[j]) )となり、変形すると

dp[i][d] = i * t[i] - Si + min{0<=j<=i}(dp[j][d-1]+Sj - j * Ti) (ただしSiはTiの累積和)

となり、iとjがいい感じに分離できる。

  • jが単調減少, Tiが広義単調増加するので蟻本に載っている形のconvex-hull trickを使うことで加速できる
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;

int dp[2010][2010];
int s[2010],t[2010];

ll f(int j,int pos,int d){return dp[d][j]+s[j]-j*pos;}

bool ng(int t1,int t2,int t3,int d){
    ll a1=-t1, b1=dp[d][t1]+s[t1];
    ll a2=-t2, b2=dp[d][t2]+s[t2];
    ll a3=-t3, b3=dp[d][t3]+s[t3];
    return (a2-a1)*(b3-b2)>=(b2-b1)*(a3-a2);
}

int p[2010];
int a,n,m;
int l,r;
int deq[2010];

int main(){
    scanf("%d%d%d",&a,&n,&m);
    rep(i,a)scanf("%d",p+i);
    rep(i,n){int y;scanf("%d%d",t+i,&y);t[i]-=p[y-1];}
    sort(t,t+n);

    rep(i,n) rep(j,i) dp[0][i+1]+=t[i]-t[j];    
    rep(i,n) s[i+1]=s[i]+t[i];

    for(int j=1;j<m;++j){
	l=0,r=0;
	for(int i=1;i<=n;++i){
	    while(l+1<r && ng(deq[r-2],deq[r-1],i,j-1)) --r;
	    deq[r++]=i;
	    while(l+1<r && f(deq[l],t[i-1],j-1) >= f(deq[l+1],t[i-1],j-1)) ++l;
	    dp[j][i]=i*t[i-1]-s[i]+f(deq[l],t[i-1],j-1);
	}
    }
    printf("%d\n",dp[m-1][n]);
    return 0;
}

AOJ2445 MinimumCostPath

MinimumCostPath | Aizu Online Judge


まあまあ面白かった

n * n (n<=10^6)のマス目があって左下から右上に最短距離で行く場合の数(障害物は50個まで)

どう見てもスカスカで、殆ど邪魔されずに行けそうだけど左下と右上付近は混雑するかもしれないので、近くだけbfsして後はdp(経路を最初に通る障害物で区別したりするとなんとかなる)