AOJ再挑戦116～120 - c21coterie @ ウィキ

問116　Rectangular Searching

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0116
図の中に描ける最大の面積を持つ長方形を探す問題

解法
私はBigO(n^3)のコードしか考え付きませんでした。
osa_kさんのコードがシンプルながらBigO(n^2)なのでAOJで見ておいてください。
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=496648&tab=2#

私もstackの代わりにmapをつかった解法であと一歩のところまで到達していたのであと一歩という感じでした。
mapから消すのは遅いけどstackは早い、その差が出ました。

問117　A reward for a Carpenter

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0117
大工が柱を買い付けて戻ってくるまでのコストを最小にする問題。
解法
点の数が少ないグラフなので計算量の多い手抜きコードでも何の問題もありません。
点の数が増えたらダイクストラ法などを使います。

#include<stdio.h>
#include<string.h>

int G[21][21];

int calc(int s,int e,int n){
	int cost[21];
	memset(cost,-1,sizeof(cost));
	cost[s]=0;
	while(1){
		bool isUpDate=false;
		for(int i=1;i<=n;i++){
			if(cost[i]==-1)continue;
			for(int j=1;j<=n;j++){
 				if(G[i][j]==-1)continue;
				if(cost[j]==-1 || cost[j]>cost[i]+G[i][j]){
					cost[j]=cost[i]+G[i][j];
					isUpDate=true;
				}
			}
 		}
		if(isUpDate==false)break;
	}
	return cost[e];
}

int main(){
 	int n,m,a,b,c,d;
scanf("%d %d",&n,&m);
 	memset(G,-1,sizeof(G));
	while(m--){
		scanf("%d,%d,%d,%d",&a,&b,&c,&d);
		G[a][b]=c;
		G[b][a]=d;
	}
 	int x1,x2,y1,y2;
	scanf("%d,%d,%d,%d",&x1,&x2,&y1,&y2);
	printf("%d\n",y1-y2-calc(x1,x2,n)-calc(x2,x1,n));
}

問118　Property Distribution

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0118
この問題、数十万行*数十万列のデータになってもコードが動くように書いてみました。

• BigO(行数*列数*log(列数,2))の定数倍。
• 列数の定数倍のメモリ使用量で動く。
• sizeを列数の最大に合わせれば数十万列でも安定して動きます。

#include<stdio.h>
#include<string.h>
#include<set>
#include<algorithm>
#include<queue>
#include<map>
#include<iostream>


const int SIZE=101;
void calc(int h,int w){
	char row[2][SIZE];
	long long int memo[SIZE],next[SIZE];
	long long int ansAdd=0;
	std::map<long long int,long long int> noUnion;
	std::map<long long int,long long int>::iterator mIt;
	std::set<long long int>::iterator it;
	long long int maxNo=1;
	
	//何十万行*何十万列でも動くアルゴリズムを模索中。

	for(int y=0;y<h;y++){
		int now=y%2;
		int old=(y+1)%2;
		scanf("%s",row[now]);
		std::set<long long int> pNos,dNos;
		for(int x=0;x<w;x++){
			if(x>0 && row[now][x-1]==row[now][x]){
				next[x]=next[x-1];
			}else{
				next[x]=maxNo;
				noUnion[maxNo]=maxNo;
				maxNo++;
			}
			if(y>0 && row[old][x]==row[now][x]){
				long long int no1=noUnion[memo[x]];
				long long int no2=noUnion[next[x]];
				if(no1<no2){
					noUnion[memo[x]]=no1;
					noUnion[next[x]]=no1;
				}else{
				noUnion[memo[x]]=no2;
 					noUnion[next[x]]=no2;
			}
				
				pNos.insert(memo[x]);
			}
			if(y>0&& row[old][x]!=row[now][x]){
				dNos.insert(memo[x]);
			}
		}
		for(int x=w-1;x>=0;x--){
			if(y>0 && row[old][x]==row[now][x]){
				long long int no1=noUnion[memo[x]];
				long long int no2=noUnion[next[x]];
				if(no1<no2){
					noUnion[memo[x]]=no1;
					noUnion[next[x]]=no1;
				}else{
					noUnion[memo[x]]=no2;
					noUnion[next[x]]=no2;
				}
			}
		}
		std::set<long long int> dNos2,dNos3;
		
		for(int x=0;x<w;x++){
			if(pNos.find(memo[x])==pNos.end() && dNos.find(memo[x])!=dNos.end()){
				dNos3.insert(noUnion[memo[x]]);
		}
		}
		//std::cout<<"\n<";
		//for(it=dNos2.begin();it!=dNos2.end();it++){
		//	std::cout<<(*it)<<" ";
		//}
		//std::cout<<">\n";
		ansAdd+=dNos3.size();
		std::set<long long int> pNos2;
		
		for(int x=0;x<w;x++){
			next[x]=noUnion[next[x]];
			pNos2.insert(next[x]);
		}
		noUnion.clear();
		for(it=pNos2.begin();it!=pNos2.end();it++){
			noUnion[(*it)]=(*it);
		}
 		memcpy(memo,next,sizeof(memo));
		//std::cout<<noUnion.size()<<" "<<ansAdd<<"\n";
	}
	std::cout<<(ansAdd+noUnion.size())<<"\n";
}

int main(){
	int h,w;
	while(scanf("%d %d",&h,&w)!=EOF){
		if(w==0&&h==0)break;
		calc(h,w);
	}
}

問119　Taro's Obsession

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0119
証言から誰がどの順番で部屋に入ったかあり得る組み合わせを一つ答える問題。

解法
人数が数万人証言が数十万個程度になっても安定して動くコードで書いてみました。
BigO（証言数）です。
証言数が数千万とかになったらどんなコードを書けばいいのだろうか？

#include<stdio.h>
#include<vector>
#include<string.h>
#include<queue>

const int SIZE=21;
const int NIL=-1;
int main(){
	int m,n,count[SIZE]={0},a,b;
	std::vector<int> con[SIZE];
	std::queue<int> qu;
	scanf("%d %d",&m,&n);
	while(n--){
		scanf("%d %d",&a,&b);
		count[b]++;
		con[a].push_back(b);
	}
	int next[SIZE]={0};
	memcpy(next,count,sizeof(next));
	for(int a=1;a<=m;a++){
 		if(count[a]==0)qu.push(a);
	}
	while(qu.empty()==false){
		int a=qu.front();
		qu.pop();
		printf("%d\n",a);
		for(int i=0;i<con[a].size();i++){
			int b=con[a][i];
			if(next[b]<=0)continue;
			next[b]--;
			if(next[b]==0)qu.push(b);
 		}
		memcpy(count,next,sizeof(count));
	}
}