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

「aoj2261～2270」(2013/01/23 (水) 18:56:27) の最新版変更点

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

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

*2261　[[iwi]]
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2261
文字列から部分文字列を取得して左右対称な文字列を作るとき何文字まで作れるかを答える問題。
簡単に正答数を稼げる問題。
短いコードで合格している人がいるがどんなテクニックがあるのか？
左右対称という恣意的なルールを記述するのにどうしたってコード中にその部分の記述が必要でコードサイズが膨らむはずなのだけど？



 #include<stdio.h>
 #include<string.h>
 char text[20];
 int len,ans=0;
 char cpy[20];
 void saiki(int deep,int nowP){
	if(deep==len){
		//左右対称なら奇数になるはず
		char c1,c2;
		bool out=false;
		cpy[nowP]='\0';
		if(nowP%2==1&&nowP>2){
			for(int i=0;i<nowP/2;i++){
				c1=cpy[i];
				c2=cpy[nowP-i-1];
				if(c1=='i'&&c2!='i')out=true;
				if(c1=='w'&&c2!='w')out=true;
				if(c1=='('&&c2!=')')out=true;
				if(c1==')'&&c2!='(')out=true;
				if(c1=='{'&&c2!='}')out=true;
				if(c1=='}'&&c2!='{')out=true;
				if(c1=='['&&c2!=']')out=true;
				if(c1==']'&&c2!='[')out=true;
				if(out==true)return;
			}
			if(strstr(cpy,"iwi")==NULL)return;
			ans=ans>nowP?ans:nowP;
		}
	}else{
		cpy[nowP]=text[deep];//この文字を使う
		saiki(deep+1,nowP+1);
		saiki(deep+1,nowP);
	}
 }
 int main(){
	scanf("%s",text);
	len=strlen(text);
	saiki(0,0);
	printf("%d\n",ans);
 }






*2262　Stopping Problem
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2262
２次元で記述されたジョークコンパイラを実装する問題。

ジョークなので何とも言えない言語ですが一応サイズ制限をなくせばチューリング完全らしいです。
まあ一応理論上はそうなんでしょうね。
過去に同じ状態を通ってないかメモしながら幅優先探索するだけです。


 #include<stdio.h>
 #include<set>
 #include<queue>
 int dxs[]={1,0,-1,0};
 int dys[]={0,-1,0,1};//右、上、左、下の順
 int r,c;
 struct cur{
	int x,y,arrow;//位置と向き
	int num;//メモリの状態
	bool operator<(const cur& c)const{
		if(x!=c.x)return x<c.x;
		if(y!=c.y)return y<c.y;
		if(arrow!=c.arrow)return arrow<c.arrow;
		return num<c.num;
	}
	cur move(int arrow){
		cur re;
		re.x=(x+dxs[arrow]+c)%c;
		re.y=(y+dys[arrow]+r)%r;
		re.arrow=arrow;
		re.num=num;
		return re;
	}
 };
 int main(){
	scanf("%d %d",&r,&c);
	char map[22][22];
	int x,y;
	for(int i=0;i<r;i++){
		scanf("%s",map[i]);
	}
	cur c1,nextC;
	c1.x=c1.y=c1.num=c1.arrow=0;
	std::set<cur> memo;
	std::queue<cur> Q;
	memo.insert(c1);
	Q.push(c1);
	bool stop=false;
	while(Q.empty()==false){
		c1=Q.front();
		Q.pop();
		x=c1.x;
		y=c1.y;
		char com=map[y][x];
		if(com=='@'){
			stop=true;//停止
			break;
		}
		if(com=='?'){
			//4方向全て試す
			for(int i=0;i<4;i++){
				nextC=c1.move(i);
				if(memo.find(nextC)==memo.end()){
					memo.insert(nextC);
					Q.push(nextC);
				}
			}
			continue;
		}
		if(com=='<'){
			nextC=c1.move(2);//左
		}else if(com=='>'){
			nextC=c1.move(0);//右	
		}else if(com=='^'){
			nextC=c1.move(1);//上
		}else if(com=='v'){
			nextC=c1.move(3);//下
		}else if(com=='_'){
			if(c1.num==0)nextC=c1.move(0);//0なら右
			else nextC=c1.move(2);
		}else if(com=='|'){
			if(c1.num==0)nextC=c1.move(3);//0なら下
			else nextC=c1.move(1);
		}else if(com=='.'){
			nextC=c1.move(c1.arrow);//そのまま
		}else if('0'<=com&&com<='9'){
			nextC=c1.move(c1.arrow);
			nextC.num=com-'0';
		}else if(com=='+'){
			nextC=c1.move(c1.arrow);
			nextC.num=(c1.num+1)%16;
		}else if(com=='-'){
			nextC=c1.move(c1.arrow);
			nextC.num=(c1.num-1+16)%16;
		}
		if(memo.find(nextC)==memo.end()){
			memo.insert(nextC);
			Q.push(nextC);
		}
	}
	printf("%s\n",stop?"YES":"NO");
 }






*2263 The First Acceptance
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2263
プログラミングコンテストを題材にした問題。

解法
とりあえず範囲が広いのでstd::mapを使って動的計画法を使ってみましたがなんか違う感じです。
皆メモリ使用量低で解いてますね。
私のコードはメモリを多めに使ってます。

 #include<stdio.h>
 #include<map>
 #include<vector>
 #include<algorithm>
 struct S{
 	int a,b;
 	bool operator<(const S& s)const{
 		return b<s.b;
 	}
 };
 
 int main(){
 	int n,a,b,ans=0;
 	std::map<int,int> memo,nextMemo;
 	memo[0]=0;
 	scanf("%d",&n);
 	S s;
 	std::vector<S> vec;
 	for(int i=0;i<n;i++){
 		scanf("%d %d",&s.a,&s.b);
 		vec.push_back(s);
 	}
 	std::sort(vec.begin(),vec.end());
 	for(int i=0;i<vec.size();i++){
 		a=vec[i].a;
 		b=vec[i].b;
 		for(std::map<int,int>::iterator it=memo.begin();it!=memo.end();it++){
 			int t=(*it).first+a;
 			int t2=(*it).second+1;
 			
 			int t3;
 			if(t>b)break;
 			if(memo.find(t)==memo.end()){
 				if(nextMemo.find(t)==nextMemo.end()||nextMemo[t]<t2)nextMemo[t]=t2;
 				t3=t2>nextMemo[t]?t2:nextMemo[t];
 			}else if(memo[t]<t2){
 				memo[t]=t2;
 				t3=t2;
 			}else{
 				t3=memo[t];
 			}
 			if(ans<t3)ans=t3;
 		}
 		memo.insert(nextMemo.begin(),nextMemo.end());
 		nextMemo.clear();
 	}
 	printf("%d\n",ans);
 }









*2264　Spanning Trees
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2264

解法
グラフを描いてみても時間をかけたら答えが見つかりそうな気もしつつ少しめんどくさかったので1分ほど他人のコードを知ら見してしまった。
ソースに解説はなかったので多分だけど用は正多角形としてグラフを描いたとき対角線を一番外側、一本内側、2本内側、、、ｎ/2本内側、、、1本内側、外側という順に結んでいく。
これを一点分回転すると重ならないグラフがｎ/２本描けるということらしい。
原理が分かるとなるほどな問題。

#include <cstdio>
using namespace std;

int n, k;

void solve(){
	for(int st=0; st<k; st++){
		int L=(n+st-1)%n;
		int R=st;
		for(int i=0;i<n-1;i++){
			if(i%2==0){
				printf("%d %d\n",R+1,L+1);
				R=(R+1)%n;
			}else{
				printf("%d %d\n",L+1,R+1);
				L=(L+n-1)%n;
			}
		}
		printf("\n");
	}
}

int main(){
	
	scanf("%d %d",&n,&k);
	if(k > n/2){
		printf("-1\n");
	}else{
		solve();
	}
}

*2261　[[iwi]]
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2261
文字列から部分文字列を取得して左右対称な文字列を作るとき何文字まで作れるかを答える問題。
簡単に正答数を稼げる問題。
短いコードで合格している人がいるがどんなテクニックがあるのか？
左右対称という恣意的なルールを記述するのにどうしたってコード中にその部分の記述が必要でコードサイズが膨らむはずなのだけど？



 #include<stdio.h>
 #include<string.h>
 char text[20];
 int len,ans=0;
 char cpy[20];
 void saiki(int deep,int nowP){
	if(deep==len){
		//左右対称なら奇数になるはず
		char c1,c2;
		bool out=false;
		cpy[nowP]='\0';
		if(nowP%2==1&&nowP>2){
			for(int i=0;i<nowP/2;i++){
				c1=cpy[i];
				c2=cpy[nowP-i-1];
				if(c1=='i'&&c2!='i')out=true;
				if(c1=='w'&&c2!='w')out=true;
				if(c1=='('&&c2!=')')out=true;
				if(c1==')'&&c2!='(')out=true;
				if(c1=='{'&&c2!='}')out=true;
				if(c1=='}'&&c2!='{')out=true;
				if(c1=='['&&c2!=']')out=true;
				if(c1==']'&&c2!='[')out=true;
				if(out==true)return;
			}
			if(strstr(cpy,"iwi")==NULL)return;
			ans=ans>nowP?ans:nowP;
		}
	}else{
		cpy[nowP]=text[deep];//この文字を使う
		saiki(deep+1,nowP+1);
		saiki(deep+1,nowP);
	}
 }
 int main(){
	scanf("%s",text);
	len=strlen(text);
	saiki(0,0);
	printf("%d\n",ans);
 }






*2262　Stopping Problem
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2262
２次元で記述されたジョークコンパイラを実装する問題。

ジョークなので何とも言えない言語ですが一応サイズ制限をなくせばチューリング完全らしいです。
まあ一応理論上はそうなんでしょうね。
過去に同じ状態を通ってないかメモしながら幅優先探索するだけです。


 #include<stdio.h>
 #include<set>
 #include<queue>
 int dxs[]={1,0,-1,0};
 int dys[]={0,-1,0,1};//右、上、左、下の順
 int r,c;
 struct cur{
	int x,y,arrow;//位置と向き
	int num;//メモリの状態
	bool operator<(const cur& c)const{
		if(x!=c.x)return x<c.x;
		if(y!=c.y)return y<c.y;
		if(arrow!=c.arrow)return arrow<c.arrow;
		return num<c.num;
	}
	cur move(int arrow){
		cur re;
		re.x=(x+dxs[arrow]+c)%c;
		re.y=(y+dys[arrow]+r)%r;
		re.arrow=arrow;
		re.num=num;
		return re;
	}
 };
 int main(){
	scanf("%d %d",&r,&c);
	char map[22][22];
	int x,y;
	for(int i=0;i<r;i++){
		scanf("%s",map[i]);
	}
	cur c1,nextC;
	c1.x=c1.y=c1.num=c1.arrow=0;
	std::set<cur> memo;
	std::queue<cur> Q;
	memo.insert(c1);
	Q.push(c1);
	bool stop=false;
	while(Q.empty()==false){
		c1=Q.front();
		Q.pop();
		x=c1.x;
		y=c1.y;
		char com=map[y][x];
		if(com=='@'){
			stop=true;//停止
			break;
		}
		if(com=='?'){
			//4方向全て試す
			for(int i=0;i<4;i++){
				nextC=c1.move(i);
				if(memo.find(nextC)==memo.end()){
					memo.insert(nextC);
					Q.push(nextC);
				}
			}
			continue;
		}
		if(com=='<'){
			nextC=c1.move(2);//左
		}else if(com=='>'){
			nextC=c1.move(0);//右	
		}else if(com=='^'){
			nextC=c1.move(1);//上
		}else if(com=='v'){
			nextC=c1.move(3);//下
		}else if(com=='_'){
			if(c1.num==0)nextC=c1.move(0);//0なら右
			else nextC=c1.move(2);
		}else if(com=='|'){
			if(c1.num==0)nextC=c1.move(3);//0なら下
			else nextC=c1.move(1);
		}else if(com=='.'){
			nextC=c1.move(c1.arrow);//そのまま
		}else if('0'<=com&&com<='9'){
			nextC=c1.move(c1.arrow);
			nextC.num=com-'0';
		}else if(com=='+'){
			nextC=c1.move(c1.arrow);
			nextC.num=(c1.num+1)%16;
		}else if(com=='-'){
			nextC=c1.move(c1.arrow);
			nextC.num=(c1.num-1+16)%16;
		}
		if(memo.find(nextC)==memo.end()){
			memo.insert(nextC);
			Q.push(nextC);
		}
	}
	printf("%s\n",stop?"YES":"NO");
 }






*2263 The First Acceptance
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2263
プログラミングコンテストを題材にした問題。

解法
とりあえず範囲が広いのでstd::mapを使って動的計画法を使ってみましたがなんか違う感じです。
皆メモリ使用量低で解いてますね。
私のコードはメモリを多めに使ってます。

 #include<stdio.h>
 #include<map>
 #include<vector>
 #include<algorithm>
 struct S{
 	int a,b;
 	bool operator<(const S& s)const{
 		return b<s.b;
 	}
 };
 
 int main(){
 	int n,a,b,ans=0;
 	std::map<int,int> memo,nextMemo;
 	memo[0]=0;
 	scanf("%d",&n);
 	S s;
 	std::vector<S> vec;
 	for(int i=0;i<n;i++){
 		scanf("%d %d",&s.a,&s.b);
 		vec.push_back(s);
 	}
 	std::sort(vec.begin(),vec.end());
 	for(int i=0;i<vec.size();i++){
 		a=vec[i].a;
 		b=vec[i].b;
 		for(std::map<int,int>::iterator it=memo.begin();it!=memo.end();it++){
 			int t=(*it).first+a;
 			int t2=(*it).second+1;
 			
 			int t3;
 			if(t>b)break;
 			if(memo.find(t)==memo.end()){
 				if(nextMemo.find(t)==nextMemo.end()||nextMemo[t]<t2)nextMemo[t]=t2;
 				t3=t2>nextMemo[t]?t2:nextMemo[t];
 			}else if(memo[t]<t2){
 				memo[t]=t2;
 				t3=t2;
 			}else{
 				t3=memo[t];
 			}
 			if(ans<t3)ans=t3;
 		}
 		memo.insert(nextMemo.begin(),nextMemo.end());
 		nextMemo.clear();
 	}
 	printf("%d\n",ans);
 }









*2264　Spanning Trees
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2264

解法
グラフを描いてみても時間をかけたら答えが見つかりそうな気もしつつ少しめんどくさかったので1分ほど他人のコードを知ら見してしまった。
ソースに解説はなかったので多分だけど用は正多角形としてグラフを描いたとき対角線を一番外側、一本内側、2本内側、、、ｎ/2本内側、、、1本内側、外側という順に結んでいく。
これを一点分回転すると重ならないグラフがｎ/２本描けるということらしい。
原理が分かるとなるほどな問題。

 #include <cstdio>
 using namespace std;
 int n, k;
 
 void solve(){
 	for(int st=0; st<k; st++){
 		int L=(n+st-1)%n;
 		int R=st;
 		for(int i=0;i<n-1;i++){
 			if(i%2==0){
 				printf("%d %d\n",R+1,L+1);
 				R=(R+1)%n;
 			}else{
 				printf("%d %d\n",L+1,R+1);
 				L=(L+n-1)%n;
 			}
 		}
 		printf("\n");
 	}
 } 
 
 int main(){
 	
 	scanf("%d %d",&n,&k);
 	if(k > n/2){
 		printf("-1\n");
 	}else{
 		solve();
 	}
 }