AOJ221～230 の編集履歴一覧 - c21coterie @ ウィキ

AOJ221～230 - (2011/09/27 (火) 18:03:39) の編集履歴(バックアップ)

0221　FizzBuzz

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0221
フィジーバズというゲームをシミュレーションして結果を報告する問題。

解法
高速化する方法もあるようですが、そのまま解いてみました。
ルールどおりに実装するだけです。
この問題の引っ掛けは一人になったあと、残った入力データを読むのを忘れないことだけです。
それさえ忘れなければ簡単な問題です。

#include <stdio.h>
#include <string>
#include <list>
#include <iostream>
void solve(int m,int n);
int main()
{
int m,n;
scanf("%d %d",&m,&n);
while(m!=0 || n!=0){
	solve(m,n);
	scanf("%d %d",&m,&n);
}
}
void solve(int m,int n){
std::string t;
std::list<int> memo;
for(int i=m;i>0;i--){
	memo.push_front(i);
}
bool isDell,end=false;
std::list<int>::iterator it=memo.begin();
for(int i=1;i<n+1;i++){
	std::cin>>t;
	if(end==true)continue;
	isDell=false;
	if(i%15==0){
		if(t!="FizzBuzz"){
			isDell=true;
		}
	}else if(i%5==0){
		if(t!="Buzz"){
			isDell=true;
		}
	}else if(i%3==0){
		if(t!="Fizz"){
			isDell=true;
		}
	}else{
		int num;
		if(sscanf(t.c_str(),"%d",&num)==0 || num!=i){
			isDell=true;
		}
	}
	if(isDell==true){
		it=memo.erase(it);
		if(memo.size()==1) end=true;
	}else{
		it++;
	}
	if(memo.end()==it) it=memo.begin();
}
it=memo.begin();
printf("%d",*it);
it++;
while(it!=memo.end()){
	printf(" %d",*it);
	it++;
}
printf("\n");
}

0222　Prime Quadruplet

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0222
指定された値以下の４子素数の最大値を見つけるという問題。

解法
この問題,一風変わった解き方をしてみました。
下記コードを実行します。
コードを実行すると4つ後素数の中で一番大きな数字だけを書いたファイルが作られるので、これを問題を解くソースコードにマトリックスとして組み込むという方法があります。
他の正答者のコードサイズを見ると実行速度が早くメモリ使用量が小さいコードがあるので何か賢い実装があるのかもしれませんが私の場合はこう解いてみたという例です。

#include <stdio.h>
#include <math.h>
#include <vector>
bool primeCheck(int n){
for(int i=3;i<(int)sqrt((double)n)+1;i++){
	if(n%i==0){
		return false;
	}
}
return true;
}
bool quadrupletCheck(int n){
if(primeCheck(n) && primeCheck(n-2) && primeCheck(n-6) && primeCheck(n-8)){
	return true;
}else{
	return false;
}
}
int main(){
std::vector<int> datas;
std::vector<int>::iterator it;
for(int i=13;i<10000001;i+=2){
	if(quadrupletCheck(i)){
		datas.push_back(i);
	}
}
FILE *fp;
fp = fopen("mydata.txt", "w");
it=datas.begin();
while(it!=datas.end()){
	fprintf(fp, "%d,", (*it));
	it++;
}
fclose(fp);
}

0223　Stray Twins

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0223
正反対に動く双子がデパートでであえるまでのターン数を求める問題です。

解法
幅優先探索で実装してみました。
一度通った状態はメモ化して２度通らないようにしています。
このコードは幅優先探索の教科書みたいなコードで丁寧は丁寧ですが教科書通りで工夫が足りませんでした。
速度が出ず正答者の中では下位ランクのコードです。
他の方のコードを参考に後日書き直す予定です。

#include<stdio.h>
#include<queue>
#include<set>
#include<algorithm>
#include<stdlib.h>
struct point{
char x1,y1,x2,y2;
int turn;
bool operator<(const point& p)const{
	if(x1!=p.x1) return x1<p.x1;
	if(y1!=p.y1) return y1<p.y1;
	if(x2!=p.x2) return x2<p.x2;
	return y2<p.y2;
}
};
int dxs[]={1,0,-1,0};
int dys[]={0,1,0,-1};
void setData(int X,int Y){
point p,nextP;
p.turn=0;
int map[54][54];
std::queue<point> qu;
std::set<point> memo;
scanf("%d %d %d %d",&p.x1,&p.y1,&p.x2,&p.y2);
for(int i=0;i<=Y+1;i++){
	for(int j=0;j<=X+1;j++){
		if(i==0 || i==Y+1 || j==0 || j==X+1){
			map[i][j]=1;
		}else{
			scanf(" %d",&map[i][j]);
		}
	}
}
qu.push(p);
memo.insert(p);
int nx1,ny1,nx2,ny2;
while(!qu.empty()){
	p=qu.front();
	qu.pop();
       if(p.turn==100){
       	break;
       }
       nextP.turn=p.turn +1;
	for(int i=0;i<4;i++){
		nx1=p.x1+dxs[i];
		ny1=p.y1+dys[i];
		nx2=p.x2-dxs[i];
		ny2=p.y2-dys[i];
		if(map[ny1][nx1]==1){
			nx1=p.x1;
			ny1=p.y1;
		}
		if(map[ny2][nx2]==1){
			nx2=p.x2;
			ny2=p.y2;
		}
		if((100-nextP.turn)*2<abs(nx2-nx1)+abs(ny2-ny1))continue;			
		nextP.x1=nx1;
		nextP.y1=ny1;
		nextP.x2=nx2;
		nextP.y2=ny2;
		if(nextP.x1==nextP.x2 && nextP.y1==nextP.y2){
			printf("%d\n",nextP.turn);
			return;
		}
		
		if(memo.find(nextP)==memo.end()){
			memo.insert(nextP);
			qu.push(nextP);
		}
	}
}
printf("NA\n");
}
int main(){
int X,Y;
while(scanf("%d %d",&X,&Y),X+Y>0){
	setData(X,Y);
}
}

上記コードをＢｉｔ演算にしてみました。
多少早くなりましたがＢｉｔ演算を使ってもＭａｐを使う限り高速化は無理のようで、一度通ったパターンの記憶に配列を使えば高速化できるようです。
とりあえずＭａｐを使ったままのコードです。

#include<stdio.h>
#include<queue>
#include<set>
#include<algorithm>
int dxs[]={1,0,-1,0};
int dys[]={0,1,0,-1};
void setData(int X,int Y){
int map[54][54];
std::queue<int> qu;//兄弟の位置を6bitずつ管理先頭8bitにターン数の保持
std::set<int> memo;
int x1,x2,y1,y2;
int state=0,nextState=0;
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
state=(1<<24)|(x1<<18)|(y1<<12)|(x2<<6)|(y2);	
for(int i=0;i<=Y+1;i++){
	for(int j=0;j<=X+1;j++){
		if(i==0 || i==Y+1 || j==0 || j==X+1){
			map[i][j]=1;
		}else{
			scanf(" %d",&map[i][j]);
		}
	}
}
qu.push(state);
memo.insert(state);
int nx1,ny1,nx2,ny2,turn,mask=63;	
while(!qu.empty()){
	state=qu.front();
	qu.pop();
	turn=(state>>24);
       if(turn==100){
       	break;
       }
       turn++;
       x1=(state>>18)&mask;
       y1=(state>>12)&mask;
       x2=(state>>6)&mask;
       y2=state&mask;
	for(int i=0;i<4;i++){
		nx1=x1+dxs[i];
		ny1=y1+dys[i];
		nx2=x2-dxs[i];
		ny2=y2-dys[i];
		if(map[ny1][nx1]==1){
			nx1=x1;
			ny1=y1;
		}
		if(map[ny2][nx2]==1){
			nx2=x2;
			ny2=y2;
		}
		if(nx1==nx2 && ny1==ny2){
			printf("%d\n",turn-1);
			return ;
		}
		nextState=0;
		nextState=(nx1<<18)|(ny1<<12)|(nx2<<6)|ny2;
		if(memo.find(nextState)==memo.end()){
			memo.insert(nextState);
			nextState|=(turn<<24);
			qu.push(nextState);
		}
	}
}
printf("NA\n");
}
int main(){
int X,Y;
while(scanf("%d %d",&X,&Y),X+Y>0){
	setData(X,Y);
}
}

0224　Bicycle Diet

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0224
地点ごとにあるケーキ屋でカロリー補給しながら役所へ向かうグラフの問題。

解法
この問題はケーキ屋の数が少ないことを利用して解きます。
まずワーシャルフロイド法を少し改変して間にケーキ屋を含まない全ての地点間の最短距離を求めます。
最短距離を求めたら後はこのグラフを使って家から直接役所へ。
次にケーキ屋を一つ挟んで役所へ。
２つ挟んで役所へ、、、
という探索を深さ優先探索で求めます。
この問題を解くのに３日かかりました。
問題を眺めては時折考えて、他のことしてる時も何となく無意識で考え、苦労してみつけた解法なので喜びは一入(ひとしお)でした。

#include<stdio.h>
#include<map>
#include<string>
std::map<std::string,int> points;
int graph[128][128];
int ansCalorie;
bool moveOKs[10];
int calorieMemo[10];
const int startPoint=0;
const int endPoint=1;
const int mymax=1000000000;
void  FloydWarshall(int size,int m){
int t;
for(int y=0;y<size;y++){
	for(int x=0;x<size;x++){
		if(graph[y][x]==mymax || (1<y && y<m+2)) continue;
		for(int i=0;i<size;i++){
			t=graph[x][y]+graph[y][i];
			if(t<graph[x][i]){
				graph[x][i]=t;
			}
		}
	}
}
}
void saiki(int all,int nowCalorie,int nowP){
if(nowP==endPoint){
	ansCalorie=nowCalorie>ansCalorie?ansCalorie:nowCalorie;
}else{
	for(int i=0;i<all;i++){
		if(i==nowP)continue;
		if(moveOKs[i]==true && graph[nowP][i]<mymax){
			moveOKs[i]=false;
			int nextCalorie=nowCalorie+graph[nowP][i]-calorieMemo[i];
			saiki(all,nextCalorie,i);
			moveOKs[i]=true;
		}
	}
}
}
bool setData(){
int m,n,k,d;
scanf("%d %d %d %d",&m,&n,&k,&d);
if(m==0 && n==0 && k==0 && d==0) return false;
points.clear();
for(int i=0;i<m+n+2;i++){
	for(int j=0;j<m+n+2;j++){
           graph[i][j]=(i==j)?0:mymax;
	}
}
ansCalorie=mymax;
for(int i=0;i<10;i++)moveOKs[i]=true;	
int calorie,p=2;
char cake[5],land[5];
calorieMemo[0]=calorieMemo[1]=0;
points["H"]=0;
   points["D"]=1;
   for(int i=0;i<m;i++){
	scanf("%d",&calorieMemo[p]);
	sprintf(cake,"C%d",i+1);
	points[cake]=p;
	p++;
}
for(int i=0;i<n;i++){
	sprintf(land,"L%d",i+1);
	points[land]=p;
	p++;
}
char name1[5],name2[5];
int len,p1,p2;
for(int i=0;i<d;i++){
	scanf("%s %s %d",name1,name2,&len);
	p1=points[name1];
	p2=points[name2];
	graph[p1][p2]=graph[p2][p1]=len*k;
}	
FloydWarshall(m+n+2,m);
saiki(m+2,0,0);
printf("%d\n",ansCalorie);
return true;
}
int main(){
while(setData()){
}
}

0225　Kobutanukitsuneko

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0225
しりとりで1万単語が与えられるので、すべてを一回ずつ使って最初の単語に戻ってくることができるか判別せよという問題。

解法
この問題はいろいろな解法がありますが一番計算量を抑えた解法を考え付いたので掲載します。
計算量が単語数Nですむ解法です。
まず、文字を点と考え、問題を単語の末尾文字と先頭文字を矢印でつなげたグラフとみなします。
すると全単語を使ったループを作るにはどの点でも入る矢印の数と出る矢印の数が同じにならないといけません。
最初にこれを確認します。
しかしこれだけでは、a→b→c→a d→e→f→d g→,,,
のようにばらばらのループの可能性を排除できません。
ここでできるループをA１、A2,,,Arとします。
A１、A2、、は別々のループなので、矢印がつながっていません。
もしA1から別のループ仮にA2としますが、これに矢印を一本移した場合を考えます。
するとA1では入る矢印が一本不足するのでほかのループから矢印をひっぱてこなくてはいけません。
A２では一本はいる矢印が増えるので、A2から外に出る矢印が増えます。
これによってA1から出た矢印はほかのループを巡回してA1に戻ってきます。
もしA１の点からほかのすべての点に到達できるなら、すべてのループは矢印でつながっているのであり、全単語を使ったループがそこに存在することになります。
これを素直にコード化したのが下記です。
自力で考え付いた方法なので何か穴があるかもしれません。

#include<stdio.h>
#include <string.h>
const int cSize=26;
bool moveOKs[cSize];
int map[cSize][cSize];
int moveCount;
void saiki(int nowP){
moveCount--;
moveOKs[nowP]=false;
for(int i=0;i<cSize;i++){
	if(moveOKs[i]==true && map[nowP][i]>0){
		saiki(i);
	}
}
}
void setMap(int n){
char word[33],we;
int first;
int in[cSize],out[cSize];
memset(map,0,cSize*cSize*4);
memset(in,0,cSize*4);
memset(out,0,cSize*4);
memset(moveOKs,true,cSize);
for(int i=0;i<n;i++){
	scanf("%s",word);
	we=word[strlen(word)-1]-'a';
	map[word[0]-'a'][we]++;
	in[word[0]-'a']++;
	out[we]++;
}	
bool roopOK=true;
moveCount=0;
for(int i=0;i<cSize;i++){
	if(in[i]!=out[i])roopOK=false;
	if(in[i]>0){
		first=i;
		moveCount++;
	}
}
if(roopOK==true){
	saiki(first);
}
if(roopOK==true && moveCount==0){
	printf("OK\n");
}else{
	printf("NG\n");
}
}
int main(void)
{
int n;
scanf("%d",&n);
while(n>0){
	setMap(n);
	scanf("%d",&n);
}
}

0228　Seven Segments

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0228
デジタル数字の表示入れ替えの命令セットを答える問題。
解法
数字を２進数で表して変更する領域をＸＯＲで取得するだけです。

#include<stdio.h>
int main(){
int de[]={0,63,6,91,79,102,109,125,39,127,111};
int num,next,ans,n;
while(1){
	scanf("%d",&n);
	if(n==-1)break;
	num=-1;
	while(n--){
		scanf("%d",&next);
		ans=de[num+1]^de[next+1];
		for(int i=0;i<7;i++){
			printf("%d",(ans&64)==0?0:1);
			ans=ans<<1;
		}
		printf("\n");
		num=next;
	}
}
}

230 Ninja Climbing

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0230
忍者が２つのビルの間でジャンプして屋上までたどり着けるかという問題。
ビルは滑る壁と梯子があり一定のルールで忍者は移動する。

解法
ジャンプしては滑る壁と梯子の処理を繰り返すだけの簡単な問題で動的計画法で解けます。

#include<stdio.h>
#include<string.h>
#include <algorithm>
int mymax=1000000000;
void moveCheck(int moves[101],int bill[101],int n){
for(int i=0;i<n-1;i++){
	//梯子を登る処理
	if(bill[i]==1 && bill[i+1]==1){
		moves[i+1]=std::min(moves[i],moves[i+1]);
		moves[i]=mymax;
	}
}
for(int i=n-1;i>=1;i--){
	//滑る壁を降りる処理
	if(bill[i]==2){
		moves[i-1]=std::min(moves[i],moves[i-1]);
		moves[i]=mymax;
	}
}
}
void jumpMove(int moves[2][101],int n,int now){
int next=(now+1)%2;
for(int i=0;i<n-1;i++){
	for(int k=0;k<3;k++){
		if(i+k>=n) continue;
		moves[next][i+k]=std::min(moves[next][i+k],moves[now][i]+1);
	}
}
}
void setData(int n){
int bills[2][101];
int moves[2][101];
for(int i=0;i<2*n;i++){
	scanf("%d",&bills[i/n][i%n]);
	moves[i/n][i%n]=mymax;
}
moves[0][0]=moves[1][0]=0;    
   int ans=mymax;
moveCheck(moves[0],bills[0],n);//いきなりはしごで到達できる可能性を考慮
moveCheck(moves[1],bills[1],n);	
for(int i=0;i<2*n+3;i++){
	ans=std::min(moves[0][n-1],moves[1][n-1]);
	jumpMove(moves,n,0);//0番目のビルから１番目のビルへの移動
	moveCheck(moves[1],bills[1],n);
	jumpMove(moves,n,1);//1番目同上
	moveCheck(moves[0],bills[0],n);
}
if(ans==mymax){
	printf("NA\n");
}else{
	printf("%d\n",ans);
}
}
int main(){
int n;
while(1){
	scanf("%d",&n);
	if(n==0) break;
	setData(n);
}
}

c21coterie @ ウィキ

AOJ221～230

更新履歴

メニュー

リンク

他のサービス

AOJ221～230 - (2011/09/27 (火) 18:03:39) の編集履歴(バックアップ)

0221　FizzBuzz

0222　Prime Quadruplet

0223　Stray Twins

0224　Bicycle Diet

0225　Kobutanukitsuneko

0228　Seven Segments

230 Ninja Climbing

c21coterie @ ウィキ

AOJ221～230

更新履歴

メニュー

リンク

他のサービス

AOJ221～230 - (2011/09/27 (火) 18:03:39) の編集履歴(バックアップ)

0221 FizzBuzz

0222 Prime Quadruplet

0223 Stray Twins

0224 Bicycle Diet

0225 Kobutanukitsuneko

0228 Seven Segments

230 Ninja Climbing

0221　FizzBuzz

0222　Prime Quadruplet

0223　Stray Twins

0224　Bicycle Diet

0225　Kobutanukitsuneko

0228　Seven Segments