PKU演習問メモ

3083 Children of the Candy Corn
迷路を左手で壁に触りながら抜けたとき、右手で壁を触りながら抜けたとき、最短距離で抜けたときのそれぞれの移動回数を答える問題。実装+実装+BFSで。
3173 Parkside's Triangle
次の二つの三角形から数字の並びの規則性を見つけ、段数と左上の数字が与えられた時に同じ規則の三角形を出力せよという問題。IQテストみたいだwヒント:縦書き←ドラッグで反転
3 4 6 9 4                1 2 4 7 2 7    

  5 7 1 5                  3 5 8 3 8    

    8 2 6                    6 9 4 9    

      3 7                      1 5 1   

        8                        6 2  

                                   3
3125 Printer Queue
次のようなプリンタの待ち行列を再現する問題。各ジョブは1-9の優先度を持つ(9:最大)。待ち行列の先頭のジョブの優先度が、行列の中で最大ならばそのジョブを印刷する。そうでなければそのジョブを行列のなかの最後にまわす。待ち行列の各ジョブの優先度と、自分のジョブの番号を与えられたとき自分のジョブは何番目に処理されるかを求める。
3194 Equidivisions
nxnマスのボードに1-nの数字がn個ずつ書かれている。これらの数字が次の条件を満たすときgood divisionという:同じ数字のマス同士は必ず上下左右で一つにつながっている。与えられたボードがgoodかwrongか判定せよという問題。
3136 Treats for the Cows
treatの意味がよくわからない。ごちそう?両端からだけものを取り出せる両端キュー的な入れ物に価値v[i]のtreatがn個並んでおいてある。一日に一つtreatを取り出す。取り出したtreatの価値はv[i]*tである。(tは日数)treatの価値の合計が最も高くなるような取り出し方をしたときの合計を求めよ、という問題。O(n^2)の動的計画法がすぐに思い浮かぶがn≦2000だから少し不安だなー、とか思ってたんだけど書いてみたら通った。添え字が複雑すぎて死ぬ(ソース参照)
3187 Backward Digit Sums
逆三角形の形に数字を並べて、三角形上の数はその左上と右上の数になっているようなものを考える。この三角形の一番下の数sumと一番上に並んでいる数の数nが与えられたとき、一番上に並んでいる数を復元せよという問題。ただし一番上に並んでいる数は1からnまでの相違なる整数である。深さ優先でおk.配列の確保まちがって2回WAだしたorz.
3372 Candy Distribution
輪になって座っているN人の子供にキャンディを次のように配りたい。最初は1人目に配る。次に2人目に配る。次に1人飛ばして4人目に配る。次に2人飛ばして……このとき全ての子供にキャンディが配られるかを判定せよという問題。解けたけどどうしてこの答えになるのかよく解らない。


↓ソースなど

3125 Printer Queue

int main()
{
	int cs; cin>>cs;
	while(cs--)
	{
		int n,m; cin>>n>>m;
		
		pi q[n];
		rep(i,n)
		{
			int p; cin>>p;
			q[i]=mp(-p,i);
		}
		
		int ans=1;
		while(1)
		{
			int mn=min_element(q,q+n)->first;
			if(mn==q[0].first)
			{
				if(q[0].second==m)break;
				rotate(q,q+1,q+n);
				
				ans++,n--; continue;
			}
			rotate(q,q+1,q+n);
		}
		cout<<ans<<endl;
	}
	return 0;
}

キューとid番号をセットにしてソートしてやればよい。

3194 Equidivisions

int r[100][100],n;
bool finish[101];

int dy[]={-1,0,1,0},dx[]={0,1,0,-1};

int dfs(int y,int x)
{
	int prev=r[y][x],ret=1;
	r[y][x]=0;
	rep(d,4)
	{
		int ny=y+dy[d],nx=x+dx[d];
		if(ny<0||nx<0||ny>=n||nx>=n)continue;
		if(r[ny][nx]==prev)ret+=dfs(ny,nx);
	}
	return ret;
}

int main()
{
	while(cin>>n,n)
	{
		rep(i,n)fill(r[i],r[i]+n,n);
		rep(i,n-1)rep(j,n)
		{
			int a,b; cin>>a>>b;
			r[a-1][b-1]=i+1;
		}
		
		bool ok=1;
		fill(finish,finish+n+1,0);
		rep(i,n)rep(j,n)if(r[i][j])
		{
			if(finish[r[i][j]])
			{
				ok=0; goto END;
			}
			finish[r[i][j]]=1;
			if(dfs(i,j)!=n)
			{
				ok=0; goto END;
			}
		}
		END:cout<<(ok?"good":"wrong")<<endl;
	}
	return 0;
}

深さ優先探索で数字のかかれたボードを塗りつぶす。
塗りつぶした後で同じ数字のボードが出てきたら連結してない数字なのでwrong.

3136 Treats for the Cows

int n,v[2000];
int dp[2002][2002],ans;

int main()
{
	cin>>n;
	rep(i,n)cin>>v[i];
	
	for(int len=n;len>0;len--)
	for(int l=0;l<n-len+2;l++)
	{
		int t=n-len+1;
		int a=l+len<=n?dp[l][l+len+1]+t*v[l+len-1]:0;
		int b=l>0?dp[l-1][l+len]+t*v[l-1]:0;
		dp[l][l+len]=max(a,b);
		ans=max(ans,dp[l][l+len]);
	}
	
	cout<<ans<<endl;
	return 0;
}

添え字がややこしすぎてデバッグがキツい。どうしたもんかなあ。