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(経路を最初に通る障害物で区別したりするとなんとかなる)