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

「2361~2370」の編集履歴(バックアップ)一覧に戻る
2361~2370」を以下のとおり復元します。
*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");
 }




*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);
 }

復元してよろしいですか?