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

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

2361~2370 - (2012/07/10 (火) 09:46:48) のソース

*2362 Chicken or the Egg
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2362
鶏が先か卵が先かこれを解明できる古文書を読解する問題。
問題のルールを理解するのに少し時間がかかる問題でうs。
卵鶏卵鶏鶏卵 と並んでいる場合並んでいる鶏で区切って
(卵鶏卵鶏)と(鶏卵)で分割し、分割した内容を後ろから読んでより後ろがご先祖様になる。
この後ろから読むという部分を読解できるかどうかがこの問題最大の難関。
問題を解くコード自体は極めて簡素にできる。


 #include<stdio.h>
 int main(){
	char c,str[7],ans,old=' ';
	int count=0,ansCount=0;	
	while(scanf("%c",&c)!=EOF && c!='\n'){
		if(c=='e'){
			scanf("%2s",str);
		}else if(c=='c'){
			scanf("%6s",str);
		}
		if(c==old){
			if(ansCount<count){
				ans=c;
				ansCount=count;
			}
			count=0;
		}
		count++;
		old=c;
	}
	if(ansCount<count)ans=old;
	printf("%s\n",ans=='e'?"egg":"chicken");
 }




*2364 Lucky Dip
一度調べたところは二度と調べないようマップにチェックを入れて優先順位付きキューと幅優先探索による解法。
簡単な問題だが一回目はタイムリミッド、2回目はメモリオーバー、後は一か所の記述ミスに気づかず2連続WAを食らった。
あまりに恥ずかしい。


 #include<stdio.h>
 #include<queue>
 #include<set>
 #include<vector>
 char map[1002][1002];
 struct P{
	int x,y,time;
 };
 class timeSorter {
	public:
	bool operator()(const P& l, const P& r) const {
		return l.time>r.time;
  	}
 };
 class posSorter{
	public:
	bool operator()(const P& l,const P& r)const{
		if(l.x!=r.x)return l.x<r.x;
		return l.y<r.y;
	}
 };
 int main(){
	int w,h,gx,gy;
	scanf("%d %d",&w,&h);
	for(int r=0;r<h;r++){
		scanf("%s",map[r]);
	}
	std::priority_queue<P,std::vector<P>,timeSorter> points;
	std::set<P,posSorter> wMemo;//開く隔壁のメモ
	int wx,wy,time=0;
	P p,nextP;
	p.time=p.x=p.y=0;
	points.push(p);
	int dxs[]={1,0,-1,0};
	int dys[]={0,1,0,-1};
	int n;
	scanf("%d",&n);
	std::vector<int> wxs,wys;
	for(int i=0;i<n;i++){
		scanf("%d %d",&p.x,&p.y);
		wMemo.insert(p);//開く隔壁の場所をメモ
		wxs.push_back(p.x);
		wys.push_back(p.y);
	}
	while(!points.empty()){
		p=points.top();
		points.pop();
		//printf("<%d %d %d> ",p.x,p.y,p.time);
		if(map[p.y][p.x]=='t')break;//ゴールに到達
		if(time<p.time){
			if(time>=n)break;//理論上あり得ないが一応念のため
			map[wys[time]][wxs[time]]='.';
			time=p.time;
		}
		if(map[p.y][p.x]=='#'){
			p.time++;//隔壁が開いてないので待つ
			points.push(p);
			continue;
		}
		map[p.y][p.x]='*';//このフロアは調べたので進入禁止
		for(int i=0;i<4;i++){
			nextP.x=p.x+dxs[i];
			nextP.y=p.y+dys[i];
			nextP.time=p.time;
			if(nextP.x<0||w<=nextP.x||nextP.y<0||h<=nextP.y)continue;
			char c=map[nextP.y][nextP.x];
			if(c=='*')continue;//調済ずみフロアだった
			if(c=='.')map[nextP.y][nextP.x]='*';//このフロアは調べたので進入禁止に
			if(c=='#'&&wMemo.find(nextP)==wMemo.end())continue;//この壁は開かない
			if(c=='#')nextP.time++;
			points.push(nextP);
		}
	}	
	if(map[p.y][p.x]=='t')printf("%d\n",p.time);
	else printf("-1\n");
 }





*2366 Elevator
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2366
一基あるエレベータを使ってエレベータの移動距離が最短になるように建物から荷物をおろしていく問題。
この問題は一階ずつ解決していきます。
まず最上階にある荷物を下ろすために最上階に行きます。
そしてその下にある荷物のある階に荷物を全ておろしいったんエレベータから荷物をすべて出します。
後は、今いる階を最上階とみなして同じ操作を続ければ完了です。
忘れてはいけない点は速度を出すために隠し味として各階の移動に動的計画法を使います。
この問題は不正回を出しまくったうえ自力で正しい考え方に至るのに一週間もかかりました。

もしエレベータの数が複数になって、各エレベータの止まる階や重量制限がバラバラになった場合手も足も出ない問題です。




 #include<stdio.h>
 #include<vector>
 #include<map>
 #include <stdlib.h>
 struct goods{
	int w,floor;//重さと階と
 };
 int n,m,W,ans=0;
 int tempAns;
 std::vector<goods> datas;
 std::vector<int> floors;
 std::map<int,int> memo;
 void saiki(std::vector<int>& ws,int state,int w,int all,int count){
	if(tempAns<=count)return;
	if(state==all){
		tempAns=tempAns>count?count:tempAns;
	}else{
		int no=1;
		for(int i=0;i<ws.size();i++){
			if((state&no)!=0){
				//何もしない
			}else if(ws[i]+w>W){
				if(memo.find(state)==memo.end()){
					memo[state]=count;
				}else if(memo[state]>count){
					memo[state]=count;
				}else{
					no*=2;
					continue;
				}
				
				saiki(ws,state|no,ws[i] ,all,count+1);
			}else{
				saiki(ws,state|no,w+ws[i],all,count);
			}
			no*=2;
		}
	}
 }
 int main(){
	int k;
	goods g;
	scanf("%d %d %d",&n,&m,&W);
	m--;
	floors.push_back(0);
	for(int i=0;i<n;i++){
		scanf("%d",&k);
		g.floor=i;//1階をレベル0とする
		//一階の荷物は無視する
		if(k!=0&&i!=0){
			floors.push_back(i);	
		}
		while(k--){
			scanf("%d",&g.w);
			if(i==0) continue;
			datas.push_back(g);
		}
	}
	if(floors.size()>1)ans=abs(m-floors[floors.size()-1]);
	for(int i=floors.size()-1;i>0;i--){
		int now =floors[i];
		int next=floors[i-1];
		int move=now-next;
		int all=0;
		int no=1;
		std::vector<int> ws;
		ws.clear();
		for(unsigned int j=0;j<datas.size();j++){
			if(datas[j].floor>=now){
				ws.push_back(datas[j].w);
				all+=no;
				no*=2;
			}
		}
		tempAns=1000;
		memo.clear();
		saiki(ws,0,0,all,1);
		if(tempAns>=1){
			ans+=move+(tempAns-1)*move*2;
		}
	}
	printf("%d\n",ans);
 }