※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「AOJ1141~1150」の編集履歴(バックアップ)一覧に戻る

AOJ1141~1150 - (2012/07/18 (水) 13:26:24) のソース

*1148 Analyzing Login/Logout Records
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1148&lang=jp
ログイン記録から各人のログイン合計時間を求める問題。

マップに放り込んでソートして状態遷移マシンに食わして集計するだけです。


 #include<stdio.h>
 #include<map>
 //あかん、夏バテでコードを検証する気力が欠片も起きない、、、
 struct Log{
	int no,time;
	bool operator<(const Log& l)const{
		if(no!=l.no)return no<l.no;//ナンバー順
		return time<l.time;//時刻順
	
	}
 };
 void setData(){
	Log l1;
	int n,s,r,q,last;
	std::map<Log,int> memo;
	std::map<Log,int>::iterator it;
	scanf("%d",&r);
	while(r--){
		scanf("%d %d %d %d",&l1.time,&n,&l1.no,&s);
		s=s==0?-1:1;
		if(memo.find(l1)!=memo.end()){
			memo[l1]+=s;
		}else{
			memo[l1]=s;
		}
	}
	n=-1;
	int count;
	for(it=memo.begin();it!=memo.end();it++){
		if((*it).first.no!=n){
			n=(*it).first.no;
			count=0;
		}
		count+=(*it).second;
		(*it).second=count;
	}
	int sTime,ans;
	scanf("%d",&q);
	while(q--){
		scanf("%d %d %d",&l1.time,&last,&l1.no);
		ans=0;
		it=memo.upper_bound(l1);
		if(it!=memo.begin())it--;
		if((*it).first.no!=l1.no&&it!=memo.end())it++;
		if(it==memo.end()||(*it).first.no!=l1.no){
			printf("0\n");
			continue;
		}
		bool isFirst;
		if((*it).second==0){
			isFirst=true;
		}else{
			isFirst=false;
			sTime=std::max(l1.time,(*it).first.time);
		}
		if(memo.end()!=it)it++;
		while(it!=memo.end()&&(*it).first.no==l1.no&&(*it).first.time<=last){
			
			if((*it).second!=0){
				if(isFirst==true){
					sTime=(*it).first.time;
					isFirst=false;
				}
			}else{
				if(isFirst==false){
					ans+=(*it).first.time-sTime;
					isFirst=true;
				}
			}
			it++;
		}
		if(isFirst==false){
			if(last>=sTime)ans+=last-sTime;
		}
		printf("%d\n",ans);
	}
 }
 int main(){
	int n,m;
	while(1){
		scanf("%d %d",&n,&m);
		if(n==0&&m==0)break;
		setData();
	}
 }

*1150 Cliff Climbing
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1150
崖登りミニゲームの最短クリア時間をシミュレートする問題。
盤面も小さいので油断していつも通りMapと優先順位付きキューによる幅優先探索で挑んだらまあまあの結果になった。
片足の位置情報と次どちらの足を使うかの情報以外いらないという点に気づけば平均的なコード実行速度を叩きだせる。
問題はどうやってTop10入りをするかである。
おそらく配列と動的計画法を極めるのだとは思うけど?


 #include<stdio.h>
 #include<map>
 #include<set>
 #include<queue>
 #include<algorithm>
 #include <stdlib.h>
 #include<vector>
 struct point{
	int x,y;
	bool operator<(const point& p)const{
		if(x!=p.x)return x<p.x;
		return y<p.y;
	}
 };
 struct state{
	int x,y,turn,LR;//-1なら左足、1なら右足を動かす
 };
 class turnSorter {
	public:
	bool operator()(const state& l, const state& r) const {
		return l.turn>r.turn;
  	}
 };
 class posSorter {
	public:
	bool operator()(const state& l, const state& r) const {
		if(l.x!=r.x)return l.x<r.x;
		if(l.y!=r.y)return l.y<r.y;
		return l.LR<r.LR;
  	}
 };
 void setData(int w,int h){
	std::map<state,int,posSorter> memo;
	std::priority_queue<state,std::vector<state>,turnSorter> pQ;
	char map[62][32],c,ts[2];
	state s,nextS;
	s.turn=0;
	std::set<point> goals;
	point p;
	for(int y=0;y<h;y++){
		for(int x=0;x<w;x++){
			scanf("%s",ts);
			map[y][x]=ts[0];
			if('0'<=map[y][x]&&map[y][x]<='9')map[y][x]-='0';
			if(map[y][x]=='X')map[y][x]=-1;//-1は進入不可
			if(map[y][x]=='S'){
				map[y][x]=0;
				s.x=x;
				s.y=y;
				s.LR=1;
				pQ.push(s);
				s.LR=-1;
				pQ.push(s);
			}
			if(map[y][x]=='T'){
				map[y][x]=0;
				p.x=x;
				p.y=y;
				goals.insert(p);
			}
		}
	}
	//スタートの設定
	int dxs[]={1,1,1, 1, 1,2,2, 2,3};//右足の移動、xに-1を掛けて左足に転用する
	int dys[]={2,1,0,-1,-2,1,0,-1,0};//9マス
	bool goalOK=false;
	//メモ化による枝刈つき幅優先探索
	while(!pQ.empty()){
		s=pQ.top();
		pQ.pop();
		p.x=s.x;
		p.y=s.y;
		if(goals.find(p)!=goals.end()){
			goalOK=true;
			break;
		}
		if(memo.find(s)!=memo.end()&&memo[s]<s.turn)continue;
		memo[s]=s.turn;
		nextS.LR=-s.LR;
		for(int i=0;i<9;i++){
			nextS.x=s.x+dxs[i]*s.LR;
			nextS.y=s.y+dys[i];
			if(nextS.x<0 || w<=nextS.x || nextS.y<0 || h<=nextS.y || map[nextS.y][nextS.x]==-1)continue;
			nextS.turn=s.turn+map[nextS.y][nextS.x];
			if(memo.find(nextS)!=memo.end()&&memo[nextS]<=nextS.turn)continue;
			memo[nextS]=nextS.turn;
			pQ.push(nextS);
		}
	}
	printf("%d\n",goalOK?s.turn:-1);
 }
 int main(){
	int h,w;
	while(1){
		scanf("%d %d",&w,&h);
		if(w==0&&h==0)break;
		setData(w,h);
	}
 }