PKU演習問メモ(2010/3/28)

PKU

三月中に300問行くって目標立てたのに昨日サボリすぎた……
今日も全然集中できないなあ。とりあえず最低10問はやろう、うん。

3025 Rings
n個の円が与えられる。直接または間接的に接触してるリングをグループと見るとき円の個数が最大になるグループの、最大の個数を求める問題。How many islands?的にやればよい。
1928 The Peanuts
畑の格子点にピーナッツがある。個数の多い順に回収していくとき制限時間内で取れる最大のピーナッツの個数を求める問題。
2070 Filling Out the Team
身体能力値が各ポジションに適するか判定する問題。
2078 Matrix
NxN行列の各行について、任意の回数列をシフトさせる操作が可能である。このとき各行の和のうち最大のものの、可能な最小値を求めよという問題。N≦7と小さく組み合わせは7^6≒100万しかないので全探索でおｋ.
2902 Grandpa is Famous
与えられた表のうち出現回数が二番目に多い値を答える問題。値は1万まで。配列つくって数えてソートしてというナイーブな実装で通った。
2019 Cornfields
NxN行列の指定されたBxB小行列について、最大値と最小値の差を求める問題。昨日のCodeforces Round#6のEみたいにSegment tree（の二次元版かなここでは）使う問題なのかな？と思ったけど何かB^2の解法がギリギリ通ったぞ……なんだこれ。いいのか……？
2083 Fractal
いわゆるシェルピンスキーのカーペットを描く問題。n≦7までなので配列のなかに結果を格納して最後にまとめて描画することが可能。どうもIOのコストだけでTLEするようなので少し工夫がいる。
2021 Relative Relatives
Tedの子孫について、親の名前と、親が何歳の時に生まれたかが与えられるので全員の年齢を求めよという問題。名前が文字列なので少し面倒かも。
2181 Jumping Cows
説明めんどいや……鬱。n個目のポーションを偶数回、奇数回目に飲むときの表を作って動的計画法。
2291 Rotten Ropes
ロープをつかっておもりをつるす。ロープはそれぞれ限界重量が決まっているが、組み合わせることが出来て、n本のロープを束ねてwのおもりをつるしたとき各ロープにかかる重量はw/nとなる。与えられたロープでつるすことのできるおもりの重量の最大値を求めよという問題。greedyでおｋ.


とりあえず273問。


だめだ限界。意味不明なバグが出まくって最早コンパイルが通らないので寝る。
本当にもうあれだ。地頭的な能力が足りなさすぎで終わってる。

2078 Matrix

int n,m[7][7],ans;
void dfs(int cur)
{
	if(cur==n)
	{
		int mx=0;
		rep(i,n)
		{
			int s=0;
			rep(j,n)s+=m[j][i];
			mx=max(mx,s);
		}
		ans=min(ans,mx); return;
	}
	rep(i,n)
	{
		rotate(m[cur],m[cur]+1,m[cur]+n);
		dfs(cur+1);
	}
}

int main()
{
	
	while(cin>>n,~n)
	{
		rep(i,n)rep(j,n)cin>>m[i][j];
		
		ans=inf;
		dfs(1);
		cout<<ans<<endl;
	}
	return 0;
}

STLのrotateが便利。

2083 Fractal

int pw[7];
char img[729][730];

void draw(int y,int x,int d,bool f)
{
	if(d==0)
	{
		img[y][x]=f?'X':' '; return;
	}
	
	rep(i,3)rep(j,3)
		draw(y+i*pw[d-1],x+j*pw[d-1],d-1,f&(i^j^1));
}

int main()
{
	pw[0]=1;
	rep(i,6)pw[i+1]=pw[i]*3;
	
	draw(0,0,6,1);
	
	int d;
	while(cin>>d,~d--)
	{
		rep(i,pw[d])
		{
			char t=img[i][pw[d]]; img[i][pw[d]]='\0';
			printf("%s\n",img[i]);
			img[i][pw[d]]=t;
		}
		printf("-\n");
	}
	
	return 0;
}

こんな感じで。