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

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
2次元で記述されたジョークコンパイラを実装する問題。

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


#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


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

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