「AOJ1141～1150」の編集履歴（バックアップ）一覧はこちら

「AOJ1141～1150」(2012/07/27 (金) 18:25:20) の最新版変更点

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

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

*1145　The Genome Database of All Space Life
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1145&lang=jp
圧縮された宇宙生物DNAデータを展開しi文字目にあるDNA記号を返す問題。

まずは１００万文字と少ない文字数なので再帰下降構文解析をやって愚直に求めるコードを書いてみた。
高速に動くコードをテストするための自前採点用データ製作機としての役割としてつくっただけでコードは単なる踏み台。
それを改良してと考えたらほんの5行ほどコードを足しただけで高速化できた。
数行つけたしただけで高速化するなんてプログラムってちょっと面白い。


 #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入りをするかである。
おそらく配列と動的計画法を極めるのだとは思うけど？


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

*1145　The Genome Database of All Space Life
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1145&lang=jp
圧縮された宇宙生物DNAデータを展開しi文字目にあるDNA記号を返す問題。

まずは１００万文字と少ない文字数なので再帰下降構文解析をやって愚直に求めるコードを書いてみた。
高速に動くコードをテストするための自前採点用データ製作機としての役割としてつくっただけでコードは単なる踏み台。
それを改良してと考えたらほんの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入りをするかである。
おそらく配列と動的計画法を極めるのだとは思うけど？


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