PKU演習問メモ(4/23)

鬱期がきてるようだ……
僕のような才能のないクズにできることは問題を解きまくることだけだ。

No. Title 分類・解法 主観的難易度
1631 Bridging signals 動的計画法 ★★★☆☆
2922 Honeymoon Hike (拡張)ダイクストラ ★★★☆☆


以下問題概要解説ソースコード

1631 Bridging signals

問題概要

半導体の配線をデザインするのに、左側と右側にn個ずつのゲートがある。
左側のゲートと右側のゲートで、つなぐ候補は1対1に決定しており、それら以外をつなぐことはできない。
このうち配線が交差しない範囲で左側のゲートと右側のゲートを最大いくつつなぐことができるか。

解法

二部グラフの問題のように見える。辺の交差しないグラフの最大数を求める問題にも見える。
確かゼミで後者の問題を解いた記憶が……確か、二部グラフにグラフ上・グラフ下に対応する頂点を作りー……って書けばできそうだ。


しかしもう少しよく考えると、ゲートの対応候補が1対1であることから、右側の番号について最大増加部分列を求めてやればその項数がそのまま求める解になっていることに気づく!
なので動的計画法により最大増加部分列を求めてやれば良い。
のだが、前回の動的計画法の問題で用いたO(n^2)のアルゴリズムを使うとn=4万であるためTLEになる。(なった)
O(nlog n)で最大増加部分列を求めるアルゴリズムがあるため、それを用いる。
詳細はSpaghetti source参照。


A[i]に長さiの最長増加部分列の末端の項の番号、id[i]にa[i]がA[i]のどこに挿入されうるかを記録してある。

ソースコード
int n,p[40000];
int A[40000],id[40000];

int main()
{
  int cs; scanf("%d",&cs);
  while(cs--){
    scanf("%d",&n);
    rep(i,n)scanf("%d",p+i),A[i]=inf,id[i]=0;
    
    rep(i,n){
      id[i]=lower_bound(A,A+n,p[i])-A;
      A[id[i]]=p[i];
    }
    int m=*max_element(id,id+n);
    cout<<m+1<<endl;
  }
  return 0;
}

2922 Honeymoon Hike

問題概要

nxnのグリッドで表される山を、左上のマスから右下のマスへ移動したい。移動できる方向は上下左右のみである。
グリッドの各マスの高さが与えられたとき、道中における「最大の高さ-最小の高さ」を最小にするような道における「最大の高さ-最小の高さ」を求めよ。

解法

各マスの高さは0≦h≦200と狭いので、今までの道中における最小高度と最大高度をメモした動的計画法……で良いように思えるが、最短距離で移動しろとは言ってないので、今まで通った道の「高さの最小値」で各ノードを多重化したDijkstra法を使う。
計算時間はちょっと怪しい気がするが特に工夫せず間に合う。

ソースコード
int dx[]={-1,0,1,0},dy[]={0,-1,0,1};

int n,h[100][100];
int opt[100][100][200];

int main()
{
	int CS; scanf("%d",&CS);
	rep(cs,CS)
	{
		scanf("%d",&n);
		rep(i,n)rep(j,n)scanf("%d",h[i]+j);
		
		rep(i,n)rep(j,n)rep(k,201)opt[i][j][k]=inf;
		opt[0][0][h[0][0]]=h[0][0];
		
		priority_queue<pair<pi,pi> > Q; Q.push(mp(mp(0,-h[0][0]),mp(0,0)));
		while(!Q.empty())
		{
			int y=Q.top().second.first,x=Q.top().second.second;
			int mx=-Q.top().first.first,mn=-Q.top().first.second; Q.pop();
			mx+=mn;
			
			if(y==n-1&&x==n-1)
			{
				cout<<"Scenario #"<<cs+1<<":"<<endl<<mx-mn<<endl<<endl; break;
			}
			rep(d,4)
			{
				int ny=y+dy[d],nx=x+dx[d];
				if(ny<0||nx<0||ny>=n||nx>=n)continue;
				int nmx=max(mx,h[ny][nx]),nmn=min(mn,h[ny][nx]);
				if(opt[ny][nx][nmn]<=nmx)continue;
				
				opt[ny][nx][nmn]=nmx;
				Q.push(mp(mp(-nmx+nmn,-nmn),mp(ny,nx)));
			}
		}
	}
	return 0;
}