PKU演習問(8/11)
一日中考えてるんたけど、それでもこれしか問題解けないとか才能なさすぎて終わってる。つらい。
| No. | 問題名 | 問題の種類および解法 | 難易度 |
|---|---|---|---|
| 2559 | Largest Rectangle in a Histogram | データ構造（スタック） | ★★★☆☆ |
| 3342 | Party at Hali-Bula | 動的計画法(TreeDP) | ★★★☆☆ |
| 3184 | Finicky Grazers | 動的計画法 | ★★★☆☆ |
| 3272 | Cow Traffic | 動的計画法 | ★★★★☆ |
| 3298 | Antimonotonicity | 動的計画法 | ★★★★☆ |
2559 Largest Rectangle in a Histogram
解法
AOJのときか何かで、このブログで取り上げたことあったような。
気のせいかなあ。
Algorithm Noteの神解説を参照に。（http://algorithms.blog55.fc2.com/blog-category-6.html）
ソースコード
int n,h[100001]; int main() { while(scanf("%d",&n),n) { rep(i,n)scanf("%d",h+i); h[n]=0; ll ans=0; stack<pi> S; rep(i,n+1) { if(S.empty()) { S.push(mp(0,h[0])); continue; } int t=S.top().second,l=i; if(t==h[i])continue; if(t<h[i]) { S.push(mp(i,h[i])); continue; } while(!S.empty()&&S.top().second>=h[i]) { t=S.top().second,l=S.top().first; S.pop(); ans=max(ans,(ll)t*(i-l)); } S.push(mp(l,h[i])); } printf("%lld\n",ans); } return 0; }
3342 Party at Hali-Bula
問題概要
メモ化を間違えていてWA出しまくった……
別にこれは難しい問題じゃないぞー……なんかだめぽ。調子悪いのかなあ。
n個の頂点からなる木が与えられる。独立頂点集合の頂点数および、それが一意に定まるかを出力せよ。
n≦200を満たす
解法
木の最適解が一意に定まる⇔
- 部分木の最適解が全て一意に定まる
- 木の根を独立頂点集合に含めた場合の最適解と木の根を独立頂点集合に含めない最適解が同一ではない
の両方が成り立つこと。
これを葉まで再帰的にチェックすればいい。
最大独立集合の部分は典型的なTree DP.（あるいは典型的な二部グラフの最大マッチング）
ソースコード
int n; vector<vi> e; int dp[200][2]; bool uni[200][2]; void rec(int c,int f,int p) { if(dp[c][f]>=0)return; bool uni1=1,uni2=1; int ret1=1,ret2=0; if(f)fr(i,e[c])if(*i!=p) { rec(*i,0,c); uni1=uni1&&uni[*i][0]; ret1+=dp[*i][0]; } fr(i,e[c])if(*i!=p) { rec(*i,1,c); uni2=uni2&&uni[*i][1]; ret2+=dp[*i][1]; } if(!f) { dp[c][f]=ret2; uni[c][f]=uni2; return; } dp[c][f]=max(ret1,ret2); if(ret1==ret2)uni[c][f]=0; else uni[c][f]=ret1>ret2?uni1:uni2; } int main() { while(scanf("%d",&n),n) { e.clear(); e.resize(n); string str,str2; map<string,int> id; int cnt=0; cin>>str; id[str]=cnt++; rep(i,n-1) { cin>>str; if(!id.count(str))id[str]=cnt++; cin>>str2; if(!id.count(str2))id[str2]=cnt++; e[id[str]].pb(id[str2]); e[id[str2]].pb(id[str]); } rep(i,n)rep(j,2)dp[i][j]=-1; rec(0,1,0); printf("%d %s\n",dp[0][1],uni[0][1]?"Yes":"No"); } return 0; }
3184 Finicky Grazers
問題概要
n頭の牛が長さ0からLの区間（両端含む）に並んで居る。
これらの牛を、隣り合う牛の区間の幅の最小値が最大になるよう牛を移動したい。
（順番は変えないで、位置を動かす）
このとき、必要な牛の移動量の和の最小値を求めよ。
n≦10000かつ、牛の間隔は常に全て整数であるように動かすものとする。
解法
牛と牛の隙間はn-1個で、その長さの合計はL-n+1になる。
全ての牛の位置は整数なので、区間は長さD,D+1の2種類で、
である。
したがって、dp[牛][その牛まででD+1の区間の個数]=(最小コスト)
のようなDPによりO(n^2)で最適解が求められる。
そのまま実装すると、制限時間オーバーおよびメモリ使用量オーバーになるので、
- テーブルは2列のみ保持する
- 数の少ないほうの区間を覚える
工夫をする必要がある。
ソースコード
const int MX=50000; int n,l,p[MX]; int dp[2][MX]; int solve(int lena,int lenb,int m) { rep(j,m+1)dp[0][j]=inf; dp[0][0]=p[0]; int cur=0,next=1; for(int i=1;i<n;i++) { rep(j,m+1)dp[next][j]=inf; rep(j,min(i,m+1)) { dp[next][j]=min(dp[next][j],dp[cur][j]+abs(p[i]-i-lena*j-lenb*(i-j))); if(j+1<=m)dp[next][j+1]=min(dp[next][j+1],dp[cur][j]+abs(p[i]-i-lena*(j+1)-lenb*(i-j-1))); } swap(cur,next); } return dp[cur][m]; } int main() { scanf("%d%d",&n,&l); rep(i,n)scanf("%d",p+i); int bg=(l-n+1)%(n-1),sml=n-1-bg,tmp=(l-n+1)/(n-1); printf("%d\n",sml<bg?solve(tmp,tmp+1,sml):solve(tmp+1,tmp,bg)); return 0; }
3272 Cow Traffic
問題概要
n個の牧場(番号1,2...,N)と、それらを結ぶ片道通行のm本の道がある。
全ての牧場について、N番の牧場へ行く経路が一つ以上存在する。
また、道ははつねに番号の小さい牧場から番号の大きい牧場への一方通行である。
どこからも道が入っていない牧場には牛がいる。
このとき、全ての牛が牧場Nへ移動するような移動方法で、通る回数が最も多い道における通行回数を求めよ。
n≦50000を満たす。
解法
問題文理解するまでに物凄く時間がかかった。問題文理解した後も、WA出し続けて物凄く時間がかかった。
入出力を取り寄せた後ですらハマった。模範解法のソースを見た後も答えが合わずハマった。
つまりは、はまりまくった。
問題自体も結構難しいと思うのだけど、AC多い……
グラフは木ではない（葉から根に行くのにパスが一意に決まるとは限らない）が、
どのノードからも必ずN番のノードにたどり着けるかつ、ループはないので、木の用語を使って、N番のノードを根、そのノードに入るような道がないノードを葉と呼ぶことにする。
問題文で求められているのは、葉から根に向かうルート全てについて、
通るエッジに1を足していったとき、最大の数はいくつかという問題である。
以下のようにして解く。
あるエッジについて、そのエッジに書かれる数は、(そこから葉へ向かう経路の数)×(そこから根へ向かう経路の数)に等しい。
これらは動的計画法により解けるので、それらを掛け合わせればよい。
……のだが、実は添え字がかなり厄介。
辺の、根側のノードから葉へ向かう経路×葉側のノードから根へ向かう経路は正しいが、
辺の、根側のノードから根へ向かう経路×葉側のノードから葉へ向かう経路ではWAになる。
ソースコード
int n,m,lo[50000],hi[50000]; vector<vi> toroot,toleaf; int goroot[50000],goleaf[50000]; int main() { scanf("%d%d",&n,&m); toroot.resize(n); toleaf.resize(n); rep(i,m) { int s,t; scanf("%d%d",&s,&t); lo[i]=--s; hi[i]=--t; toroot[s].pb(t); toleaf[t].pb(s); } rep(i,n) { goroot[i]=goleaf[i]=0; if(toleaf[i].empty())goroot[i]=1; } goleaf[n-1]=1; for(int i=n-1;i>=0;i--)fr(j,toleaf[i])goleaf[*j]+=goleaf[i]; rep(i,n)fr(j,toroot[i])goroot[*j]+=goroot[i]; int ans=0; rep(i,m)ans=max(ans,goleaf[hi[i]]*goroot[lo[i]]); printf("%d\n",ans); return 0; }
3298 Antimonotonicity
問題概要
n項からなる数列Aが与えられる。
その数列の（必ずしも連続しない）部分列で
B[0]＞B[1]＜B[2]＞……
を満たす最長のものの長さを求めよ。
n≦30000を満たす。
解法
O(n^2)の自明な解法はTLE.
で、O(nlogn)がないかずっと悩んでたのだけど、O(n)で解けるよう……
uに次に上がる,dに次に下がるような列の長さの最長のものを持って、更新していく。
あーあー何でこれ解らないかねえ。しにてえ。
ソースコード
int n,a[30000]; int main() { int cs; scanf("%d",&cs); while(cs--) { int n; scanf("%d",&n); rep(i,n)scanf("%d",a+i); int u=-inf,d=1; rep(i,n-1) { if(a[i+1]<a[i])u=max(u,d+1); if(a[i+1]>a[i])d=max(u+1,d); } printf("%d\n",max(u,d)); } return 0; }
