AOJ511～520の編集履歴ソース - c21coterie @ ウィキ

AOJ511～520 - (2013/03/11 (月) 03:22:58) のソース

----
*0511 Who Are The Student Yet To Submit
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0511
出席名簿から欠席者の番号を出力する問題。
解法
簡単な肩慣らし問題なので特に解法はありません。


 #include<stdio.h>
 #include<string.h>
 int main(){
	bool nos[31];
	int no,i;
	memset(nos,true,31);
	for(i=0;i<28;i++){
		scanf("%d",&no);
		nos[no]=false;
	}
	for(i=1;i<31;i++){
		nos[i]?printf("%d\n",i):i;
	}
 }





----
*0512 Caesar Cipher
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0512
シーザー暗号を復号せよという問題。

解法
簡単なのでそのまま書くだけです。

 #include<stdio.h>
 int main(){
	char c[1001];
	scanf("%s",c);
	for(int i=0;c[i]!='\0';i++){
		c[i]=(c[i]-'A'+23)%26+'A';
	}
	printf("%s\n",c);
 }



----
*0513　Shuffle The Cards
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0513
カードのシャッフルをシミュレートする問題
解法
定義通りの操作をそのまま実装するだけです。


 #include<stdio.h>
 #include<string.h>
 int main(){
	int now[201],next[201],n,m,k,i;
	scanf("%d %d",&n,&m);	
	for(i=0;i<2*n;i++)now[i]=next[i]=i+1;
	for(i=0;i<m;i++){
		scanf("%d",&k);
		if(k==0){
			for(int i=0;i<2*n;i+=2){
				next[i]=now[i/2];
				next[i+1]=now[i/2+n];
			}
			memcpy(now,next,sizeof(next));
		}else{
			memcpy(next+(2*n-k),now,4*k);
			memcpy(next,now+k,4*(2*n-k));
			memcpy(now,next,2*4*n);
		}
	}
	for(int i=0;i<2*n;i++) printf("%d\n",now[i]);
 }




----
*0514　Quality Checking
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0514
機械の検査結果の組み合わせから良品と不良品を見分ける問題。


解法
合格した組の部品はすべて良品です。
後は良品２つ不良品一つで不合格となっているセットから不良品を見つけ出せばいいわけです。




 #include <stdio.h>
 #include <algorithm>
 bool search();
 int main()
 {
	while(search()){
	}
 }
 bool search()
 {
	int as[102],bs[102],cs[102];//部品が適正なら1、不適なら0、判断つかずなら2
	int a,b,c,sa,sb,sc;
	int dataA[1002],dataB[1002],dataC[1002],kekka[1002];//結果の保存
	scanf("%d %d %d",&a,&b,&c);
	if(a==0 && b==0 && c==0) return false;
	int n;
	sa=1;
	sb=a+1;
	sc=sb+b;
	scanf("%d",&n);
	int m=std::max(std::max(a,b),c);
	for(int i=0;i<m;i++){
		as[i]=bs[i]=cs[i]=2;//最初全製品を不明とする
	}	
	for(int i=0;i<n;i++)
	{
		scanf("%d %d %d %d",&dataA[i],&dataB[i],&dataC[i],&kekka[i]);
		dataA[i]-=sa;dataB[i]-=sb;dataC[i]-=sc;
		if(kekka[i]==1){
			//合格であった場合３つとも良品とする 
			as[dataA[i]]=bs[dataB[i]]=cs[dataC[i]]=1;
		}
	}	
	for(int i=0;i<n;i++)
	{
		//判別できるのは二つが良品で一つが不良品で不合格となっている場合のみ
		if(kekka[i]==0){
			if(as[dataA[i]]==1&&bs[dataB[i]]==1)cs[dataC[i]]=0;
			if(as[dataA[i]]==1&&cs[dataC[i]]==1)bs[dataB[i]]=0;
			if(bs[dataB[i]]==1&&cs[dataC[i]]==1)as[dataA[i]]=0;
		}
	}
	for(int i=0;i<a;i++) printf("%d\n",as[i]);
	for(int i=0;i<b;i++) printf("%d\n",bs[i]);
	for(int i=0;i<c;i++) printf("%d\n",cs[i]);
	return true;
 }


----
*0515　School Road
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0515
道路の移動ルートを計算する問題
解法
メモ化探索で楽勝です。



 #include<stdio.h>
 #include<string.h>
 int a,b;
 void calc(){
	int map[17][17];
	bool stops[17][17];
	memset(map,0,sizeof(map));
	memset(stops,false,sizeof(stops));
	int n,x,y;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d %d",&x,&y);
		stops[x][y]=true;
	}
	map[1][1]=1;
	for(int x=1;x<=a;x++){
		for(int y=1;y<=b;y++){
			if(stops[x][y])continue;
			map[x][y]+=map[x-1][y]+map[x][y-1];
		}
	}
	printf("%d\n",map[a][b]);
 }
 int main(){
	
	while(1){
		scanf("%d %d",&a,&b);
		if(a==0 && b==0) break;
		calc();
	}
 }




----
*0516　Maximum Sum
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0516
数列の部分を足しこんだとき、和の最大値を答える問題。
解法
K個の数列のしっぽを減らして新しく来た分を足すだけです。



 #include<stdio.h>
 int n,k;
 void calc(){
	int sum=0,as[100001],a,max,p=0;	
	for(int i=0;i<k;i++){
		scanf("%d",&a);
		sum+=a;
		as[i]=a;
	}
	max=sum;
	for(int i=k;i<n;i++){
		sum-=as[p];
		scanf("%d",&as[p]);
		sum+=as[p];
		p=(p+1)%k;
		if(max<sum)max=sum;
	}
	printf("%d\n",max);
 }
 int main(){
	while(1){
		scanf("%d %d",&n,&k);
		if(n==0 && k==0) break;
		calc();
	}
 }




----
*0517 Longest Steps
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0517
数列から数字が連続して並んでいる部分のうちで最も長い部分の長さを出力する問題。
ただし数列には一つだけ好きな数字を挿入できる。

解法
ソートして手前から集計していくだけです。
 
 #include<stdio.h>
 #include<vector>
 #include <algorithm>
 int n,k;
 void calc(){
	std::vector<int> nos;
	int a,old=0,now=1,mode=0,ans=1,sum;
	for(int i=0;i<k;i++){
		scanf("%d",&a);
		if(a==0){
			mode=1;
		}else{
			nos.push_back(a);
		}
	}
	std::sort(nos.begin(),nos.end());	
	for(int i=0;i<nos.size()-1;i++){
		if(nos[i]+1==nos[i+1]){
			now++;
		}else if(nos[i]+2==nos[i+1] && mode==1){
			sum=now+old+1;
			ans=sum>ans?sum:ans;
			old=now;
			now=1;
		}else if(nos[i]+2<nos[i+1] && mode==1){
			sum=now+old+1;
			ans=sum>ans?sum:ans;
			now=1;
			old=0;
		}else{
			ans=now>ans?now:ans;
			now=1;
			old=0;
		}
	}
	printf("%d\n",ans);
 }
 int main(){
	while(1){
		scanf("%d %d",&n,&k);
		if(n==0 && k==0)break;
		calc();
	}
 }


----
*0518　The Oldest Site
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0518
平面上に散らばった点の中から点をつなげて出来る最大の正方形を探す問題。

解法
2点を結ぶ線分ＡＢをＡ、Ｂを中心にそれぞれ90度、-90度回した先に点があればそれは正方形をなす。
ということを利用して解きます。
私の場合高速化とかあまりまじめにやらないほうなのでわかりやすさ重視で実装しています。


 #include<stdio.h>
 #include<set>
 #include <algorithm>
 void solve(int n);
 int menseki(int x1,int y1,int x2,int y2);
 class point{
	public:
	int x,y;
	bool operator<(const point& p) const
	{
		if(x!=p.x) return x<p.x;
		return y<p.y;
	}
 };
 std::set<point> points;
 std::set<point>::iterator it;
 int xs[3001],ys[3001];
 int main()
 {
	int n;
	scanf("%d",&n);
	while(n!=0){
		solve(n);
		scanf("%d",&n);
	}
 }
 void solve(int n)
 {
	points.clear();
	point p;
	for(int i=0;i<n;i++){
		scanf("%d %d",&xs[i],&ys[i]);
		p.x=xs[i];
		p.y=ys[i];
		points.insert(p);
	}	
	//2点が決まれば残りの2点が決まることを利用してループで解く
	int mensekiMax=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<i;j++){
			mensekiMax=std::max(mensekiMax,menseki(xs[i],ys[i],xs[j],ys[j]));
		}
	}
	printf("%d\n",mensekiMax);
 }
 int menseki(int x1,int y1,int x2,int y2){
	int vx=x1-x2;
	int vy=y1-y2;
	//90度回転
	int rx=-vy;
	int ry=vx;
	point p1,p2;
	p1.x=rx+x1;
	p1.y=ry+y1;
	p2.x=rx+x2;
	p2.y=ry+y2;
	if(points.find(p1)!=points.end() && points.find(p2)!=points.end()){
		return vx*vx+vy*vy;
	}
	//-90度回転
	rx=vy;
	ry=-vx;
	p1.x=rx+x1;
	p1.y=ry+y1;
	p2.x=rx+x2;
	p2.y=ry+y2;	
	if(points.find(p1)!=points.end() && points.find(p2)!=points.end()){
		return vx*vx+vy*vy;
	}
	return 0;
 }





----
*0519　
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0519
５０００チームの総当たり戦の試合結果が一部データ不明で与えられるので、勝敗表と矛盾しない順位表を一つ出力し、他の順位表があり得るかも出力せよという問題。

解法
問題をグラフに翻訳すると半順序集合の順番をつける問題だと判明します。
一位のチームに勝ったチームはいないのでまずはそのチームを探す。
一位のチームに入る↑と点を削除すると２位のチームに勝ったチームが存在しなくるので２位のチームが確定します。
後はこれを繰り返します。
ある順位を決めるとき複数のチームが３位候補や４位候補になるならそれは他の順位表の可能性を示唆するので他の順位表もありとなります。
ループをやめて優先順位付きキューを使えばもっと速度は出るけれど、実装の容易さを優先して記述した。



 #include<stdio.h>
 #include<set>
 #include<vector>
 int main(){
 	int n,m,a,b;
 	scanf("%d %d",&n,&m);
 	std::set<int> G[5001];
 	std::vector<int> dellList[5001];
 	for(int i=0;i<m;i++){
 		scanf("%d %d",&a,&b);
 		G[b].insert(a);
 		dellList[a].push_back(b);
 	}
 	int count=0;
 	int spents[5001]={0},ans=0;
 	while(count<n){
 		int perm=0;
 		std::vector<int> dells;
 		for(int i=1;i<=n;i++){
 			if(G[i].empty()&&spents[i]==0){
 				count++;
 				perm++;
 				spents[i]=1;
 				printf("%d\n",i);
 				dells.push_back(i);
 			}
 		}
 		for(int i=0;i<dells.size();i++){
 			int dellNo=dells[i];
 			for(int j=0;j<dellList[dellNo].size();j++)G[dellList[dellNo][j]].erase(dellNo);
 		}
 		if(perm>1)ans=1;
 	}
 	printf("%d\n",ans);
 }





----
*0520　Lightest Mobile
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0520
モービルの比が与えられるのでバランスをとれる最小の重さの合計を求める問題。

解法
saiki1関数では
モービルを上から下へ見ていきます。
一番下にたどり着いたら辺の比で最小の重りをつるします。
その重さの合計を上に返します。
上ではかえってきた重さと辺の比から、左右かえってきた重さを何倍の比にすればよいかを計算して上に返します。
最後にsaiki2で上から下へ辿り各重りを何倍にしていけばいいかを計算します。
少しコードサイズが膨らんでいますが変数名を省略しなかったから膨らんだと考えています。



 #include<stdio.h>
 #include<vector>
 struct mobile{
	int 	rightLen,rightNo,rightWeight,
		leftLen,leftNo,leftWeight;
 };
 std::vector<mobile> mobiles;
 int gcd(int a, int b)
 {
   int c;
   while (b > 0)
   {
       c = a % b;
       a = b;
       b = c;
   }
   return a;
 }
 int weightAns;
 void saiki2(int now,int bai){
	if(mobiles[now].rightNo==0){
		weightAns+=bai*mobiles[now].rightWeight;
	}else{
		saiki2(mobiles[now].rightNo,bai*mobiles[now].rightWeight);
	}
	if(mobiles[now].leftNo==0){
		weightAns+=bai*mobiles[now].leftWeight;
	}else{
		saiki2(mobiles[now].leftNo,bai*mobiles[now].leftWeight);
	}
 }
 int saiki1(int now){
	int leftNo=mobiles[now].leftNo,rightNo=mobiles[now].rightNo;
	int leftWeight,rightWeight,leftWeight2,rightWeight2;
	if(leftNo==0 && rightNo==0){
		leftWeight =1;
		rightWeight=1;
	}else if(leftNo==0 && rightNo!=0){
		leftWeight =1;
		rightWeight=saiki1(rightNo);
	}else if(leftNo!=0 && rightNo==0){
		rightWeight=1;
		leftWeight =saiki1(leftNo);
	}else{
		rightWeight=saiki1(rightNo);
		leftWeight =saiki1(leftNo);
	}
	leftWeight2 =leftWeight *mobiles[now].leftLen;
	rightWeight2=rightWeight*mobiles[now].rightLen;
	int t=gcd(rightWeight2,leftWeight2);
	mobiles[now].rightWeight=leftWeight2/t;
	mobiles[now].leftWeight =rightWeight2/t;
	int ans=mobiles[now].leftWeight*leftWeight+mobiles[now].rightWeight*rightWeight;
	return ans;
 }
 void setData(int n){
	mobiles.clear();
	mobile m;
	mobiles.push_back(m);
	int topMobile=1;
	std::vector<int> upMemo;
	upMemo.resize(102);
	for(int i=0;i<102;i++)upMemo[i]=-1;
	for(int i=0;i<n;i++){
		scanf("%d %d %d %d",&m.leftLen,&m.rightLen,&m.leftNo,&m.rightNo);
		mobiles.push_back(m);
		upMemo[m.leftNo]=upMemo[m.rightNo]=i+1;
	}
	while(upMemo[topMobile]!=-1){
		topMobile=upMemo[topMobile];
	}	
	weightAns=0;
	saiki1(topMobile);
	saiki2(topMobile,1);
	printf("%d\n",weightAns);
 }
 int main(){
	int n;
	while(1){
		scanf("%d",&n);
		if(n==0) break;
		setData(n);
	}
 }
c21coterie @ ウィキ

AOJ511～520

更新履歴

メニュー

リンク

他のサービス

AOJ511～520 - (2013/03/11 (月) 03:22:58) のソース
