AOJ221～230

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からｚと名前をつけ、単語の末尾文字から先頭文字へ矢印をつなげたグラフとみなします。
すると全単語を使ったループを作るには
１　すべての点で入る矢印の数と出る矢印の数が同じにならないといけません。
最初にこれを確認します。
ここで１を満たすグラフの集合をGとし、要素をｇ1,ｇ2,,,ｇuとします。

Gの中には全単語を使ってスタートに戻ってくるループもあれば
グラフ２
a→b→c→a
d→e→f→d
g→,,,
,,,
のようにグラフ内に孤立したループが複数あるｇiもありえます。
ここであるgiに存在する孤立したループをA１、A2,,,Arとし仮に島と呼びます。

A１、A2、、は別々のループなので、矢印がつながっていません。
ここで一つの思考実験をします。
Gの要素である適当なgiを考えます。
Gの要素であるという条件を保ったまま矢印を付け替えていく操作を考えます。
ある島A1内にある矢印を別のループ仮にA2としますが、これに矢印の向きを一本移した場合を考えます。

島と島をつなぐ矢印になるのでこれを仮に橋と呼ぶことにします。

グラフ２でたとえれば
a→bをa→dに付け替えるなどの操作です。
点ｂでは入る矢印が1本減るので、ｂにはいる矢印を島の中か別の島から持ってこなくてはいけません。
島の中から矢印を持ってくる場合、その点がｂと同じ状態になるので、いつかは島の外から矢印を持ってくる必要があります。

A1からA２に橋がつながった場合、A2ではA2の島の中のすべての矢印を通り橋のある点に戻ってくる経路が存在します。
そしてA2では、橋が架かったために、橋がかかったポイントからでる矢印を一本増やさなくてはならなくなります。
これはGの要素であるという条件を満たすために必要です。

この矢印はA2の島内かA2の島の外になります。
島内では、矢印が追加された点から外に出る矢印を一本増やす必要があります。
最終的にA2では橋がかかったポイントかどこか島内の別のポイントから別の島へ橋を延ばさなくてはいけません。これはGの要素であるという必要からこうなります。

次の島でもその次の島でも同様でこの橋をかける操作は橋がA1に架かるまで続きます。
点ｂの件があるためにA１へ橋を架けなくてはいけないという制約があるために橋は必ずA1へ戻ってきます。

これを簡単に言うと島から島へ橋で渡り、渡った島では島内全部の→を移動し、最後に最初の島に戻ってくることができるルートを作ることができる。
ということになります。

これを逆に考えれば、もしGの要素であるグラフ。
このグラフにおいてある点から初めて矢印をたどりほかのすべての点に到達できるなら、すべての島は橋でつながっているのであり、全単語を使ったループがそこに存在することになります。これを素直にコード化したのが下記です。
一応AOJでは正当となりましたが、自力で考え付いた方法なので何か穴があるかもしれません。
非常に特殊なデータでウマくいかない可能性は残っています。

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

0226 Hit and Blow

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0226
HitAndBlowの判定せよという問題。
解法
数字の各桁に重複した数が出ないということを利用して2重ループでときます。

#include<stdio.h>
#include<string.h>
int main(){
char r[5],a[5];

while(1){
	scanf("%s %s",r,a);
	if(strlen(a)==1) break;
	int hit=0,blow=0;
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++){
			if(r[i]==a[j])i==j?hit++:blow++;
		}
	}
	printf("%d %d\n",hit,blow);
}
}

0227　Thanksgiving

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0227
野菜の割引サービスを利用して全野菜を一番安く買う方法を見つけるという問題。

解法
値段の高い順に袋にｍ個ずつにわけて入れていきます。
それだけでこの問題は解けます。

#include<stdio.h>
#include<algorithm>
#include <functional>
void setData(int n,int m){
int ans=0,vs[1001];
for(int i=0;i<n;i++){
	scanf("%d",&vs[i]);
}
std::sort(vs,vs+n,std::greater<int>());
for(int i=1;i<=n;i++){
	ans+=i%m==0?0:vs[i-1];
}
printf("%d\n",ans);
}
int main(){
int n,m;
while(1){
	scanf("%d %d",&n,&m);
	if(n+m==0)break;
	setData(n,m);
}
}

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

0229　BigHit

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0229
スロットゲームのゲーム結果が与えられるので、最終的に何枚のメダルが残ったかを計算する問題。

解法
使用どおり一つずつ計算していくだけです。

#include<stdio.h>
int main(){
int b,r,g,c,s,t;
while(1){
	scanf("%d %d %d %d %d %d",&b,&r,&g,&c,&s,&t);
	if(b+r+g+c+s+t==0)break;
	int ans=b*12+13*5*b+100;//ビックボーナス
	ans+=r*12+13*3*r;//レギュラーボーナス
	ans+=4*g-c;//ブドウとチェリー
	ans+=-3*(t-b*6-r*4-g-c-s);//そろわなかったゲーム
	printf("%d\n",ans);
}
}

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

タグ：

+ タグ編集

「AOJ221～230」をウィキ内検索

最終更新：2011年09月29日 16:46

c21coterie @ ウィキ

更新履歴

メニュー

リンク

他のサービス

0221　FizzBuzz

0222　Prime Quadruplet

0223　Stray Twins

0224　Bicycle Diet

0225　Kobutanukitsuneko

0226 Hit and Blow

0227　Thanksgiving

0228　Seven Segments

0229　BigHit

230 Ninja Climbing

c21coterie @ ウィキ

AOJ221～230

更新履歴

メニュー

リンク

他のサービス

0221 FizzBuzz

0222 Prime Quadruplet

0223 Stray Twins

0224 Bicycle Diet

0225 Kobutanukitsuneko

0226 Hit and Blow

0227 Thanksgiving

0228 Seven Segments

0229 BigHit

230 Ninja Climbing

0221　FizzBuzz

0222　Prime Quadruplet

0223　Stray Twins

0224　Bicycle Diet

0225　Kobutanukitsuneko

0227　Thanksgiving

0228　Seven Segments

0229　BigHit