「AOJ221～230」の編集履歴（バックアップ）一覧に戻る
AOJ221～230 - (2011/09/07 (水) 17:17:00) のソース
----
*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()){
}
}
----
*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;
}
}
}
