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

「AOJ1021～1030」(2011/12/21 (水) 18:26:28) の最新版変更点

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

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

----
*1021 Emacs-like Editor
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1021
Emacsエディタの簡易版をシミュレートする問題。

解法
テキストエディタって結構設計が大変なのですね。
簡単な問題とみて甘く見てました。
改行だけしかない空行、先頭行、末尾行などの取り扱いが意外と大変な問題でした。
一晩色々なパタンを考えてから提出、ポカミスを2度修正して合格となりました。
入力データの文章の最終行は\nがないようです。
後答えの最終行に\nをつけないと不正解になります。




 #include<stdio.h>
 #include<string>
 #include<iostream>
 #define ss std::string
 //グローバル変数まとめ
 unsigned int nowP;//カーソルの現在位置、nowP文字目
 ss text;//テキスト　効率悪いが実装が楽な方を選ぶ
 ss buffer;//カットコピーした文字を覚えておく
 //グローバル変数終わり
 void a(){
	//先頭文字に移動
	if(nowP==0)return;
	while(0<nowP){
		nowP--;
		if(text[nowP]=='\n') break;
	}
	if(text[nowP]=='\n')nowP++;
 }
 void e(){
	//行末へ移動する操作
	while(nowP<text.size()){
		if(text[nowP]=='\n')break;
		nowP++;
	}
 }
 void p(){
	//上の行の先頭文字へ移動
	a();
	if(nowP==0) return ;
	nowP--;
	if(nowP==0)return;
	a();
 }
 void n(){
	//下に行があればカーソルを下の行の先頭文字に
	e();
	if(nowP<text.size()){
		nowP++;
	}else{
		a();//次の行がないので先頭文字へ移動する
	}
 }
 void f(){
	//カーソルを一つ右に移動する
	if(nowP<text.size()){
		nowP++;
	}
 }
 void b(){
	//カーソルを一つ左に移動する
	if(nowP>0){
		nowP--;
	}
 }
 void d(){
	//一文字削除する
	if(nowP<text.size()){
		text.erase(nowP,1);
	}
 }
 void k(){
	//バッファに記録する、カーソルが行末を指してない場合末尾の改行はどうなるのだろうか,Bufferに保存する？
	if(nowP==text.size())return;
	if(text[nowP]=='\n'){
		d();
		buffer="\n";
	}else{
		int oldP=nowP;
		e();
		buffer=text.substr(oldP,nowP-oldP);
		text.erase(oldP,nowP-oldP);
		nowP=oldP;
	}
 }
 void y(){
	if(buffer.size()==0)return;
	text.insert(nowP,buffer);
	nowP+=buffer.size();
 }
 int main(){
	text="";
	nowP=0;
	ss line;
	while(1){
		std::getline(std::cin, line);
		if(line=="END_OF_TEXT")break;
		text+=line+"\n";
	}
	text.erase(text.size()-1,1);
	char com;
	while(1){
		std::cin>>com;
		switch(com){
			case 'a':
				a();
				break;
			case 'e':
				e();
				break;
			case 'p':
				p();
				break;
			case 'n':
				n();
				break;
			case 'f':
				f();
				break;
			case 'b':
				b();
				break;
			case 'd':
				d();
				break;
			case 'k':
				k();
				break;
			case 'y':
				y();
				break;
		}
		if(com=='-')break;
	}
	std::cout<<text<<"\n"; 
 }


----
*1023 Amazing Graze
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1023&lang=jp
戦闘機とエネルギー球の配置から総戦闘力を求める問題。
戦闘機と玉の数が10万と大きな点が問題になり総当たりで計算すると計算量が100億になってしまいます。
この問題はどの戦闘機もどのエネルギー球も重なってないという点が重要です。
つまり密度に限界があるということです。
なのでマップを格子で区切って近辺だけ距離を計算すれば計算量が落ちます。




 #include<stdio.h>
 #include<vector>
 struct point{
 	int x,y;
 };
 std::vector<point> bPoints[202][202];
 point aPoints[100002]; 
 bool setData(){
	point aPoints[100002],p,bp,ap;
	int an,bn,r,size=50;
	scanf("%d %d %d",&an,&bn,&r);
	if(an==0 && bn==0) return false;
	for(int x=0;x<202;x++){
		for(int y=0;y<202;y++){
			bPoints[x][y].clear();
		}
	}	
	r=16*r*r;
	for(int i=0;i<an;i++){
		scanf("%d %d",&aPoints[i].x,&aPoints[i].y);
	}
	for(int i=0;i<bn;i++){
		scanf("%d %d",&p.x,&p.y);
		bPoints[p.x/size][p.y/size].push_back(p);
	}
	int lx,rx,uy,dy,len,ans=0;
	for(int i=0;i<an;i++){
		ap=aPoints[i];
		lx=ap.x/size-1;
		lx=lx<0?0:lx;
		rx=ap.x/size+1;
		dy=ap.y/size-1;
		dy=dy<0?0:dy;
		uy=ap.y/size+1;
		for(int y=dy;y<=uy;y++){
			for(int x=lx;x<=rx;x++){
				for(int no=0;no<bPoints[x][y].size();no++){
					bp=bPoints[x][y][no];
					len=(ap.x-bp.x)*(ap.x-bp.x)+(ap.y-bp.y)*(ap.y-bp.y);
					if(len<=r){
						ans++;
					}
				}
			}
		}
		
	}
	printf("%d\n",ans);
	return true;
 }
 int main(){
	while(setData()){
	}
 }


----
*1027 A Piece of Cake
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1027
いたずらされたケーキ屋さんの売上表から元の売上を求める問題。
同じ売り上げが何回足されるかに注目すれば何の問題もない問題です。



 #include<stdio.h>
 bool setData(){
	int n,sum=0,c;
	scanf("%d",&n);
	if(n==0)return false;
	
	for(int i=0;i<((n-1)*n)/2;i++){
		scanf("%d",&c);
		sum+=c;
	}
	printf("%d\n",sum/(n-1));
	return true;
 }
 int main(){
	while(setData()){
	}
 }


----
*1028　ICPC: Ideal Coin Payment and Change
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1028
円コイン6種類で品物を買うとき、支払うコインの枚数と釣銭で受け取るコインの枚数を最小化する問題。

解法
大きな金額のコインから使いできるだけPに近いP近辺の値段を深さ優先探索で求めて解きます。
WAが怖かったのでコインの使用枚数を表すupやdownを広めに取っていますが多分もう少し狭い範囲で計算しても大丈夫でしょう。
コインの枚数制限を忘れないように注意さえすれば簡単な問題です。


 #include<stdio.h>
 const int coins[]={500,100,50,10,5,1};
 const int type=6;
 int ans;
 int coinCounts[type];
 int turisen(int r){
	int re=0;
	for(int i=0;i<type;i++){
		re+=r/coins[i];
		r%=coins[i];
	}
	return re;
 }
 void saiki(int deep,int r,int cc){
	//ｒが金額残余。ccがコインカウント
	if(deep==type&&r<=0){
		int t=cc+turisen(-r);
		ans=(ans>t)?t:ans;
		return;
	}else if(deep==type){
		return;
	}
	if(cc>ans) return;
	int t=r/coins[deep];
	int up  =t+5;//大きなコインでできるだけPに近い金額を作ろうとする処理
	int down=t-4;
	up=  up<5?5:up;
	up=  up>coinCounts[deep]?coinCounts[deep]:up;
	down=down>coinCounts[deep]?coinCounts[deep]:down;
	down=down<0?0:down;	
	for(int i=down;i<=up;i++){
		saiki(deep+1,r-i*coins[deep],cc+i);//downからupの枚数のコインを試しに使ってみる
	}
 }
 void setData(int p){
	ans=1000000000;
	for(int i=type-1;i>=0;i--){
		scanf("%d",&coinCounts[i]);
	}
	saiki(0,p,0);
	printf("%d\n",ans);
 }
 int main(){
	int p;
	while(1){
		scanf("%d",&p);
		if(p==0) break;
		setData(p);
	}
 }


*1029　Traffic Analysis
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1029&lang=jp
車の通過を検知する装置のデータから車が通らなかった最も長い時間を求める問題。
どうみても出題側としてはマージソートの実装を期待していると思われる問題。
めんどくさかったので私はstd::sortで解いてます。



 #include<stdio.h>
 #include <algorithm>
 #include <vector>
 bool setData(){
	int n,m,t;
	std::vector<int> times;
	scanf("%d %d",&n,&m);
	if(n+m==0) return false;
	for(int i=0;i<n+m;i++){
		scanf("%d",&t);
		times.push_back(t);
	}
	std::sort(times.begin(),times.end());
	int old=0,ans=0,temp;
	for(int i=0;i<times.size();i++){
		temp=times[i]-old;
		ans=ans>temp?ans:temp;
		old=times[i];
	}
	printf("%d\n",ans);
	return true;
 }
 int main(){
	while(setData()){
	}
 }



*1030　Cubes Without Holes
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1030
立方体に直方体の穴をどんどん開けていったとき、体積がどうなるかを求める問題。
穴のあいた部分のブロックは最大10万個にしかならないことを利用して穴のあいた部分だけメモして解く。
この問題計算量もメモリ使用量も抑える方法があるらしい。
もう一段レベルの高い解き方があるようなのだけど？




 #include<stdio.h>
 #include<set>
 struct hole{
	int xyz[3];
	bool operator<(const hole& h)const{
		if(xyz[0]!=h.xyz[0]) return xyz[0]<h.xyz[0];
		if(xyz[1]!=h.xyz[1]) return xyz[1]<h.xyz[1];
		if(xyz[2]!=h.xyz[2]) return xyz[2]<h.xyz[2];
		return false;
	}
 };
 bool setData(){
	int n,m;
	scanf("%d %d",&n,&m);
	if(n+m==0)return false;	
	std::set<hole> holes;
	hole h;
	char xyz[3];
	int p1,p2,p3;
	for(int i=0;i<m;i++){
		scanf("%s %d %d",xyz,&p1,&p2);
		if(xyz[0]=='x'&&xyz[1]=='y'){
			h.xyz[0]=p1;
			h.xyz[1]=p2;
			p3=2;
		}else if(xyz[0]=='x'&&xyz[1]=='z'){
			h.xyz[0]=p1;
			h.xyz[2]=p2;
			p3=1;
		}else{
			h.xyz[1]=p1;
			h.xyz[2]=p2;
			p3=0;
		}
		for(int i=1;i<=n;i++){
			h.xyz[p3]=i;
			holes.insert(h);
		}
	}
	printf("%d\n",n*n*n-holes.size());
	return true;
 }
 int main(){
	while(setData()){
	}
 }

----
*1021 Emacs-like Editor
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1021
Emacsエディタの簡易版をシミュレートする問題。

解法
テキストエディタって結構設計が大変なのですね。
簡単な問題とみて甘く見てました。
改行だけしかない空行、先頭行、末尾行などの取り扱いが意外と大変な問題でした。
一晩色々なパタンを考えてから提出、ポカミスを2度修正して合格となりました。
入力データの文章の最終行は\nがないようです。
後答えの最終行に\nをつけないと不正解になります。




 #include<stdio.h>
 #include<string>
 #include<iostream>
 #define ss std::string
 //グローバル変数まとめ
 unsigned int nowP;//カーソルの現在位置、nowP文字目
 ss text;//テキスト　効率悪いが実装が楽な方を選ぶ
 ss buffer;//カットコピーした文字を覚えておく
 //グローバル変数終わり
 void a(){
	//先頭文字に移動
	if(nowP==0)return;
	while(0<nowP){
		nowP--;
		if(text[nowP]=='\n') break;
	}
	if(text[nowP]=='\n')nowP++;
 }
 void e(){
	//行末へ移動する操作
	while(nowP<text.size()){
		if(text[nowP]=='\n')break;
		nowP++;
	}
 }
 void p(){
	//上の行の先頭文字へ移動
	a();
	if(nowP==0) return ;
	nowP--;
	if(nowP==0)return;
	a();
 }
 void n(){
	//下に行があればカーソルを下の行の先頭文字に
	e();
	if(nowP<text.size()){
		nowP++;
	}else{
		a();//次の行がないので先頭文字へ移動する
	}
 }
 void f(){
	//カーソルを一つ右に移動する
	if(nowP<text.size()){
		nowP++;
	}
 }
 void b(){
	//カーソルを一つ左に移動する
	if(nowP>0){
		nowP--;
	}
 }
 void d(){
	//一文字削除する
	if(nowP<text.size()){
		text.erase(nowP,1);
	}
 }
 void k(){
	//バッファに記録する、カーソルが行末を指してない場合末尾の改行はどうなるのだろうか,Bufferに保存する？
	if(nowP==text.size())return;
	if(text[nowP]=='\n'){
		d();
		buffer="\n";
	}else{
		int oldP=nowP;
		e();
		buffer=text.substr(oldP,nowP-oldP);
		text.erase(oldP,nowP-oldP);
		nowP=oldP;
	}
 }
 void y(){
	if(buffer.size()==0)return;
	text.insert(nowP,buffer);
	nowP+=buffer.size();
 }
 int main(){
	text="";
	nowP=0;
	ss line;
	while(1){
		std::getline(std::cin, line);
		if(line=="END_OF_TEXT")break;
		text+=line+"\n";
	}
	text.erase(text.size()-1,1);
	char com;
	while(1){
		std::cin>>com;
		switch(com){
			case 'a':
				a();
				break;
			case 'e':
				e();
				break;
			case 'p':
				p();
				break;
			case 'n':
				n();
				break;
			case 'f':
				f();
				break;
			case 'b':
				b();
				break;
			case 'd':
				d();
				break;
			case 'k':
				k();
				break;
			case 'y':
				y();
				break;
		}
		if(com=='-')break;
	}
	std::cout<<text<<"\n"; 
 }


----
*1023 Amazing Graze
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1023&lang=jp
戦闘機とエネルギー球の配置から総戦闘力を求める問題。
戦闘機と玉の数が10万と大きな点が問題になり総当たりで計算すると計算量が100億になってしまいます。
この問題はどの戦闘機もどのエネルギー球も重なってないという点が重要です。
つまり密度に限界があるということです。
なのでマップを格子で区切って近辺だけ距離を計算すれば計算量が落ちます。




 #include<stdio.h>
 #include<vector>
 struct point{
 	int x,y;
 };
 std::vector<point> bPoints[202][202];
 point aPoints[100002]; 
 bool setData(){
	point p,bp,ap;
	int an,bn,r,size=50;
	scanf("%d %d %d",&an,&bn,&r);
	if(an==0 && bn==0) return false;
	for(int x=0;x<202;x++){
		for(int y=0;y<202;y++){
			bPoints[x][y].clear();
		}
	}	
	r=16*r*r;
	for(int i=0;i<an;i++){
		scanf("%d %d",&aPoints[i].x,&aPoints[i].y);
	}
	for(int i=0;i<bn;i++){
		scanf("%d %d",&p.x,&p.y);
		bPoints[p.x/size][p.y/size].push_back(p);
	}
	int lx,rx,uy,dy,len,ans=0;
	for(int i=0;i<an;i++){
		ap=aPoints[i];
		lx=ap.x/size-1;
		lx=lx<0?0:lx;
		rx=ap.x/size+1;
		dy=ap.y/size-1;
		dy=dy<0?0:dy;
		uy=ap.y/size+1;
		for(int y=dy;y<=uy;y++){
			for(int x=lx;x<=rx;x++){
				for(int no=0;no<bPoints[x][y].size();no++){
					bp=bPoints[x][y][no];
					len=(ap.x-bp.x)*(ap.x-bp.x)+(ap.y-bp.y)*(ap.y-bp.y);
					if(len<=r){
						ans++;
					}
				}
			}
		}
		
	}
	printf("%d\n",ans);
	return true;
 }
 int main(){
	while(setData()){
	}
 }


----
*1027 A Piece of Cake
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1027
いたずらされたケーキ屋さんの売上表から元の売上を求める問題。
同じ売り上げが何回足されるかに注目すれば何の問題もない問題です。



 #include<stdio.h>
 bool setData(){
	int n,sum=0,c;
	scanf("%d",&n);
	if(n==0)return false;
	
	for(int i=0;i<((n-1)*n)/2;i++){
		scanf("%d",&c);
		sum+=c;
	}
	printf("%d\n",sum/(n-1));
	return true;
 }
 int main(){
	while(setData()){
	}
 }


----
*1028　ICPC: Ideal Coin Payment and Change
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1028
円コイン6種類で品物を買うとき、支払うコインの枚数と釣銭で受け取るコインの枚数を最小化する問題。

解法
大きな金額のコインから使いできるだけPに近いP近辺の値段を深さ優先探索で求めて解きます。
WAが怖かったのでコインの使用枚数を表すupやdownを広めに取っていますが多分もう少し狭い範囲で計算しても大丈夫でしょう。
コインの枚数制限を忘れないように注意さえすれば簡単な問題です。


 #include<stdio.h>
 const int coins[]={500,100,50,10,5,1};
 const int type=6;
 int ans;
 int coinCounts[type];
 int turisen(int r){
	int re=0;
	for(int i=0;i<type;i++){
		re+=r/coins[i];
		r%=coins[i];
	}
	return re;
 }
 void saiki(int deep,int r,int cc){
	//ｒが金額残余。ccがコインカウント
	if(deep==type&&r<=0){
		int t=cc+turisen(-r);
		ans=(ans>t)?t:ans;
		return;
	}else if(deep==type){
		return;
	}
	if(cc>ans) return;
	int t=r/coins[deep];
	int up  =t+5;//大きなコインでできるだけPに近い金額を作ろうとする処理
	int down=t-4;
	up=  up<5?5:up;
	up=  up>coinCounts[deep]?coinCounts[deep]:up;
	down=down>coinCounts[deep]?coinCounts[deep]:down;
	down=down<0?0:down;	
	for(int i=down;i<=up;i++){
		saiki(deep+1,r-i*coins[deep],cc+i);//downからupの枚数のコインを試しに使ってみる
	}
 }
 void setData(int p){
	ans=1000000000;
	for(int i=type-1;i>=0;i--){
		scanf("%d",&coinCounts[i]);
	}
	saiki(0,p,0);
	printf("%d\n",ans);
 }
 int main(){
	int p;
	while(1){
		scanf("%d",&p);
		if(p==0) break;
		setData(p);
	}
 }


*1029　Traffic Analysis
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1029&lang=jp
車の通過を検知する装置のデータから車が通らなかった最も長い時間を求める問題。
どうみても出題側としてはマージソートの実装を期待していると思われる問題。
めんどくさかったので私はstd::sortで解いてます。



 #include<stdio.h>
 #include <algorithm>
 #include <vector>
 bool setData(){
	int n,m,t;
	std::vector<int> times;
	scanf("%d %d",&n,&m);
	if(n+m==0) return false;
	for(int i=0;i<n+m;i++){
		scanf("%d",&t);
		times.push_back(t);
	}
	std::sort(times.begin(),times.end());
	int old=0,ans=0,temp;
	for(int i=0;i<times.size();i++){
		temp=times[i]-old;
		ans=ans>temp?ans:temp;
		old=times[i];
	}
	printf("%d\n",ans);
	return true;
 }
 int main(){
	while(setData()){
	}
 }



*1030　Cubes Without Holes
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1030
立方体に直方体の穴をどんどん開けていったとき、体積がどうなるかを求める問題。
穴のあいた部分のブロックは最大10万個にしかならないことを利用して穴のあいた部分だけメモして解く。
この問題計算量もメモリ使用量も抑える方法があるらしい。
もう一段レベルの高い解き方があるようなのだけど？




 #include<stdio.h>
 #include<set>
 struct hole{
	int xyz[3];
	bool operator<(const hole& h)const{
		if(xyz[0]!=h.xyz[0]) return xyz[0]<h.xyz[0];
		if(xyz[1]!=h.xyz[1]) return xyz[1]<h.xyz[1];
		if(xyz[2]!=h.xyz[2]) return xyz[2]<h.xyz[2];
		return false;
	}
 };
 bool setData(){
	int n,m;
	scanf("%d %d",&n,&m);
	if(n+m==0)return false;	
	std::set<hole> holes;
	hole h;
	char xyz[3];
	int p1,p2,p3;
	for(int i=0;i<m;i++){
		scanf("%s %d %d",xyz,&p1,&p2);
		if(xyz[0]=='x'&&xyz[1]=='y'){
			h.xyz[0]=p1;
			h.xyz[1]=p2;
			p3=2;
		}else if(xyz[0]=='x'&&xyz[1]=='z'){
			h.xyz[0]=p1;
			h.xyz[2]=p2;
			p3=1;
		}else{
			h.xyz[1]=p1;
			h.xyz[2]=p2;
			p3=0;
		}
		for(int i=1;i<=n;i++){
			h.xyz[p3]=i;
			holes.insert(h);
		}
	}
	printf("%d\n",n*n*n-holes.size());
	return true;
 }
 int main(){
	while(setData()){
	}
 }