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

2361~2370 - (2012/03/26 (月) 11:48:55) の編集履歴(バックアップ)


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

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





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