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

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

AOJ1141~1150 - (2012/07/17 (火) 11:29:08) の最新版との変更点

追加された行は青色になります。

削除された行は赤色になります。

+*1145 The Genome Database of All Space Life
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1145&lang=jp
+圧縮された宇宙生物DNAデータを展開しi文字目にあるDNA記号を返す問題。
+
+まずは100万文字と少ない文字数なので再帰下降構文解析をやって愚直に求めるコードを書いてみた。
+高速に動くコードをテストするための自前採点用データ製作機としての役割としてつくっただけでコードは単なる踏み台。
+それを改良してと考えたらほんの6行コードを足しただけで高速化できた。
+数行つけたしただけで高速化するなんてプログラムってちょっと面白い。
+
+
+ #include<stdio.h>
+ int p,i,count;
+ char s[101];
+ bool last;
+ void saiki(int re,int p1){
+	int nextCount=count;
+	for(int j=0;j<re;j++){
+		if(j==1)nextCount=count-nextCount;
+		if(j>0&&count+nextCount<=i){
+			count+=nextCount;
+			continue;
+		}		
+		p=p1;
+		while(s[p]!='\0'){
+			char t=s[p];
+			if(t=='('){
+				if(last==true)return ;
+				saiki(re,p1+1);
+				break ;
+			}else if('0'<=t&&t<='9'){
+				int num=0;
+				while('0'<=s[p]&&s[p]<='9'){
+					num=num*10+s[p]-'0';
+					p++;
+				}
+				if(last==true)return;
+				if('A'<=s[p]&&s[p]<='Z'){
+					while(num--){
+						//printf("%c",s[p]);
+						if(count==i&&last==false){
+							last=true;
+							printf("%c\n",s[p]);
+							return ;
+						}
+						count++;
+					}
+				}else{
+					saiki(num,p);
+				}
+			}else if(t==')'){
+				//閉じかっこなので上の関数に戻る
+				return ;
+			}else{
+				//英文字
+				while('A'<=s[p]&&s[p]<='Z'){
+					//printf("%c",s[p]);
+					if(count==i&&last==false){
+						printf("%c\n",s[p]);
+						last=true;
+						return;
+					}
+					count++;
+					p++;
+				}
+				p--;
+			}
+			if(last==true)return ;
+			p++;
+		}
+	}
+ }
+ int main(){
+	
+	while(1){
+		scanf("%s %d",s,&i);
+		if(s[0]=='0'&&s[1]=='\0'&&i==0)break;
+		count=p=0;
+		last=false;
+		saiki(1,0);
+		if(last==false)printf("0\n");
+	}
+ }
+
+
+
+
+*1147 ICPC Score Totalizer Software
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1147&lang=jp
+審査員の得点結果から最大値と最小値を引いて平均得点を算出する問題。
+
+一番簡単な部類の問題なので何も考える必要がありません。
+
+
+ #include<stdio.h>
+ #include<algorithm>
+ int main(){
+	int n,nMin,nMax,a,sum;
+	while(1){
+		scanf("%d",&n);
+		if(n==0)break;
+		scanf("%d",&sum);
+		nMax=nMin=sum;
+		for(int i=1;i<n;i++){
+			scanf("%d",&a);
+			sum+=a;
+			nMin=std::min(a,nMin);
+			nMax=std::max(a,nMax);
+		}
+		printf("%d\n",(sum-nMin-nMax)/(n-2));
+	}
+ }
+
+
+*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である。
-とりあえず考えるのは探索を止めてもっと動的計画法の側面を強くしてメモ化による枝刈も配列になおすとか?
+崖登りミニゲームの最短クリア時間をシミュレートする問題。
+盤面も小さいので油断していつも通り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 rx,ry,lx,ly,turn,LR;//-1なら左足、1なら右足を動かす
+	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.rx!=r.rx)return l.rx<r.rx;
-		if(l.ry!=r.ry)return l.ry<r.ry;
-		if(l.lx!=r.lx)return l.lx<r.lx;
-		if(l.ly!=r.ly)return l.ly<r.ly;
+		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;
-	std::vector<int> startXs,startYs;
+	s.turn=0;
 	std::set<point> goals;
-	point p,p2;
+	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;
-				startXs.push_back(x);
-				startYs.push_back(y);
+				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);
 			}
 		}
 	}
 	//スタートの設定
-	s.turn=0;
-	int x1,y1,x2,y2;
-	for(int i=0;i<startXs.size();i++){
-		s.lx=startXs[i];
-		s.ly=startYs[i];
-		s.rx=startXs[i];
-		s.ry=startYs[i];
-		s.LR=-1;//次が右足を動かす
-		pQ.push(s);
-		s.LR=1;//次は左足を動かす
-		pQ.push(s);
-	}
 	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.rx;
-		p.y =s.ry;
-		p2.x=s.lx;
-		p2.y=s.ly;
-		//printf("<lx=%d ly=%d rx=%d ry=%d lr=%d> ",s.lx,s.ly,s.rx,s.ry,s.turn);
-		if(goals.find(p)!=goals.end()||goals.find(p2)!=goals.end()){
+		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;
-		s.LR=-s.LR;
+		nextS.LR=-s.LR;
 		for(int i=0;i<9;i++){
-			nextS=s;
-			//ここ綺麗な記述じゃないとは思いつつ書いてしまった。
-			if(s.LR==-1){
-				nextS.lx=s.rx-dxs[i];
-				nextS.ly=s.ry+dys[i];
-				if(nextS.ly<0|| h<=nextS.ly || nextS.lx<0 || w<=nextS.lx ||map[nextS.ly][nextS.lx]==-1)continue;
-				nextS.turn+=map[nextS.ly][nextS.lx];
-			}else{
-				nextS.rx=s.lx+dxs[i];
-				nextS.ry=s.ly+dys[i];
-				if(nextS.ry<0|| h<=nextS.ry || nextS.rx<0 || w<=nextS.rx ||map[nextS.ry][nextS.rx]==-1)continue;
-				nextS.turn+=map[nextS.ry][nextS.rx];
-			}
+			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);
 	}
  }