「AOJ141～150」の編集履歴（バックアップ）一覧に戻る
AOJ141～150 - (2013/10/12 (土) 09:06:43) のソース
----
*0141 Spiral Pattern
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0141
指定されたサイズの升目にスパイラルパタンを画くという問題。
升目で描きます。
解法
この問題は、曲がるまでに進むマス数を数列化することができれば非常に簡単になるそうです。
私の場合は盤面のパタンを順番に生成するという方法をとりました。
盤面を生成する方法は非常に多くの人がはまるよくない方法だそうです。
#include <stdio.h>
void solve(int);
char map[101][101];
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int move;
int main()
{
int d,n;
scanf("%d",&d);
for(int i=0;i<d;i++)
{
scanf("%d",&n);
solve(n);
if(i!=d-1){
printf("\n");
}
}
}
void solve(int n)
{
int x=1,y=n,nx,ny;
if(n==1){printf("#\n");return;}
int r=0;
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
map[i][j]=' ';
}
}
map[x][y]='#';
int count;
int count2=0;
while(count2<2){
nx=x+dx[r];
ny=y+dy[r];
if(n>=nx && nx>0 && n>=ny && ny>0){
count=0;
for(int i=0;i<4;i++){
if(map[nx+dx[i]][ny+dy[i]]=='#') count++;
}
if(count<2){
map[nx][ny]='#';
x=nx;
y=ny;
count2=0;
}else{
r=(r+1)%4;
count2++;
}
}else{
r=(r+1)%4;
count2++;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
printf("%c",map[j][i]);
}
printf("\n");
}
}
----
*0142 Nature of Prime Numbers
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0142
4で割ると3あまる素数nの性質を確認するための問題。
解法
問題の方で実装を指定しているのでそのまま実装します。
途中結果を配列に確保することで少し高速化しました。
#include<stdio.h>
#include<set>
#include<string.h>
void calc(int n){
int t,data[5001],p=0,up,ans[5001];
std::set<int> c1;
memset(ans,0,5001*4);
for(int i=1;i<n;i++){
t=(i*i)%n;
if(c1.find(t)==c1.end()){
c1.insert(t);
data[p]=t;
p++;
}
}
up=(n-1)/2;
for(int i=0;i<p;i++){
for(int j=0;j<p;j++){
if(i==j) continue;
t=data[i]-data[j];
t+=t<0?n:0;
t=t>up?n-t:t;
ans[t]++;
}
}
for(int i=1;i<=up;i++){
printf("%d\n",ans[i]);
}
}
int main(){
int n;
scanf("%d",&n);
while(n!=0){
calc(n);
scanf("%d",&n);
}
}
----
*0143Altair and Vega
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0143
平面上に三角形と点二つの座標が与えられるので、片方が三角形の中で片方が三角形の外にあるならＯＫ，でないならＮＧと表示するという問題。
解法
三角形の高さが0の場合があるのでそれだけに注意すれば後は、高校数学の教科書通りに解きます。
三角形ＡＢＣと点Ｐ、Ｑとするなら
→AP=s→ＡＢ+ｔ→ＡＣが 0<ｓ+ｔ<1 0<s<1 0<t<1なら三角形の中にあるという公式を使います。
#include<stdio.h>
bool inDelta(double xs[3],double ys[3],double x,double y){
double x1,x2,x3,y1,y2,y3,k,s,t,u;
x1=xs[1]-xs[0];
y1=ys[1]-ys[0];
x2=xs[2]-xs[0];
y2=ys[2]-ys[0];
x3=x-xs[0];
y3=y-ys[0];
k=(x1*y2-x2*y1);
if(k==0){
return false;
}
s=(y2*x3-x2*y3)/k;
t=(x1*y3-y1*x3)/k;
u=s+t;
if(s<=0.0 || 1.0<=s || t<=0.0 || 1.0<=t || u<=0.0 || 1.0<=u){
return false;
}else{
return true;
}
}
int main(){
double xp[3],yp[3],xk,yk,xs,ys;
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%lf %lf %lf %lf %lf %lf %lf %lf %lf %lf",&xp[0],&yp[0],&xp[1],&yp[1],&xp[2],&yp[2],&xk,&yk,&xs,&ys);
if(inDelta(xp,yp,xs,ys)==inDelta(xp,yp,xk,yk)){
printf("NG\n");
}else{
printf("OK\n");
}
}
}
----
*0144 Packet Transportation
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0144
インターネットのデータパケット通信を簡素化したモデルが与えられるので、そのモデルでデータパケットが送信先まで届くか判断する問題。
解法
典型的なグラフの問題なのでワーシャルフロイド法を使って解きます。
#include<stdio.h>
#include<string.h>
int map[101][101];
void calc(int n){
int t;
for(int y=1;y<=n;y++){
for(int x=1;x<=n;x++){
if(map[x][y]==0) continue;
for(int i=1;i<=n;i++){
if(map[y][i]==0 || i==x) continue;
t=map[x][y]+map[y][i];
if(map[x][i]==0 || t<map[x][i]){
map[x][i]=t;
}
}
}
}
}
void setMap(int n){
int no,connect,next;
memset(map,0,101*101*4);
for(int i=0;i<n;i++){
scanf("%d %d",&no,&connect);
for(int j=0;j<connect;j++){
scanf("%d",&next);
map[no][next]=1;
}
}
calc(n);
int m;
scanf("%d",&m);
int s,g,tern;
for(int i=0;i<m;i++){
scanf("%d %d %d",&s,&g,&tern);
if(map[s][g]<tern && map[s][g]>0){
printf("%d\n",map[s][g]+1);
}else{
printf("NA\n");
}
}
}
int main(){
int n;
scanf("%d",&n);
setMap(n);
}
*0145 Cards
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0145
カードの山を統合していく問題。
この問題、数か月に一度思い出しては３０分ほど挑戦して良くわからないなと思って諦めてたのだけど今日丁寧に整理したら解けた。
とりあえず動的計画法で解いてみて多分私のコードは普通に考えられる理論値。
他の回答者も計算量は理論値行ってるはず。
これより高速化するならよっぽど凄い発想がいると思う。
#include<stdio.h>
#include<vector>
#include<stdlib.h>
#include <string.h>
struct Yama{
int a,b;
};
std::vector<Yama> yamas;
int ans[101][101];
int calc(int n){
memset(ans,-1,sizeof(ans));
for(int i=0;i<n;i++)ans[i][i]=0;
for(int i=1;i<=n;i++){
for(int j=0;j<n-1;j++){
for(int k=j;k<n-1;k++){
int l=i+j;
if(l<1 || n<=l)continue;
if(ans[j][k]==-1)continue;
if(ans[k+1][l]==-1)continue;
int temp=ans[j][k]+yamas[j].a*yamas[k].b*yamas[k+1].a*yamas[l].b+ans[k+1][l];
if(ans[j][l]==-1 || temp<ans[j][l])ans[j][l]=temp;
}
}
}
return ans[0][n-1];
}
int main(){
int n;
Yama yama;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d %d",&yama.a,&yama.b);
yamas.push_back(yama);
}
printf("%d\n",calc(n));
}
----
*0146 Lupin The 4th
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0146
怪盗「ルパン四世」が仲間とともに複数の蔵を破って盗みをするのですがその時最も早く全ての蔵を破るルートを探すという問題。
蔵を破るたびに蔵から盗み出した千両箱の重さぶんだけ移動速度が低下した状態で次の蔵へ行かなくてはいけないのでそこそこ難しい問題です。
解法
この問題を探索でやると最悪15！通りとなります。
枝がりでは計算量が不安になるので、メモ化探索を使います。
ある蔵にいる時、今まで破ってきた蔵のリストが同じで順番が違うだけの経路は一つにまとめることができます。
破ってきた蔵のリストが同じなので持っている千両箱の重さは同じで残りの破らなけらばいけない蔵も同じになります。
となると一番タイムの早い経路以外残す必要はありません。
この性質を利用して不要な計算を抑えます。
解いたときは知りませんでしたがこの方法を世間では動的計画法と呼ぶそうです。
知りませんでした。
#include<stdio.h>
#include<queue>
#include<math.h>
#include<map>
struct timeMemo{
double time,w;
char root[15],count;
};
struct rootMemo{
char nowPoint;
int memo;
bool operator<(const rootMemo r)const{
if(nowPoint!=r.nowPoint) return nowPoint<r.nowPoint;
return memo<r.memo;
}
};
void calc(int n){
int nos[15];
double ws[15],lens[15],len,time,w,speed;
std::queue<rootMemo> qu;
std::map<rootMemo,timeMemo> memo;
rootMemo rm,nextRoot;
timeMemo tm,nextTime;
for(int i=0;i<n;i++){
scanf("%d %lf %lf",&nos[i],&lens[i],&ws[i]);
ws[i]*=20.0;
tm.time=0;
tm.w=ws[i];
tm.root[0]=i;
tm.count=0;
rm.nowPoint=i;
rm.memo=(1<<i);
memo[rm]=tm;
qu.push(rm);
}
int state;
while(qu.empty()==false){
rm=qu.front();
nextRoot=qu.front();
tm=memo[rm];
nextTime=memo[rm];
state=rm.memo;
qu.pop();
speed=2000.0/(70.0+tm.w);
nextTime.count=tm.count+1;
for(int j=0;j<n;j++){
if((state&(1<<j))!=0) continue;
len=fabs(lens[j]-lens[rm.nowPoint]);
time=len/speed+tm.time;
w=tm.w+ws[j];
nextRoot.memo=state|(1<<j);
nextRoot.nowPoint=j;
nextTime.time=time;
nextTime.w=w;
nextTime.root[tm.count+1]=j;
if(memo.find(nextRoot)==memo.end()){
qu.push(nextRoot);
memo[nextRoot]=nextTime;
}else if(memo[nextRoot].time>time){
memo[nextRoot]=nextTime;
}
}
}
int max=(1<<n)-1;
double ansTime;
rm.memo=max;
rm.nowPoint=0;
nextTime=memo[rm];
ansTime=nextTime.time;
for(int i=1;i<n;i++){
rm.nowPoint=i;
tm=memo[rm];
if(ansTime>tm.time){
ansTime=tm.time;
nextTime=tm;
}
}
printf("%d",nos[nextTime.root[0]]);
for(int i=1;i<n;i++){
printf(" %d",nos[nextTime.root[i]]);
}
printf("\n");
}
int main(){
int n;
scanf("%d",&n);
calc(n);
}
----
上記コードではコード実行速度が低速だったので
http://d.hatena.ne.jp/shioshiota/20100708/1278593446
http://d.hatena.ne.jp/Respect2D/20101128/1290917225
リンク先を参考に高速化したコードを掲載します。
高速化した代わりにメモリ使用量が増えています。
#include<stdio.h>
#include<math.h>
struct timeMemo{
double time,w;
char root[15],count;
timeMemo(){
time=-1;
}
};
timeMemo memo[1<<15][15];
void calc(int n){
int nos[15];
double ws[15],lens[15],len,speed;
timeMemo tm,nextTime;
for(int i=0;i<n;i++){
scanf("%d %lf %lf",&nos[i],&lens[i],&ws[i]);
ws[i]*=20.0;
tm.time=0;
tm.w=ws[i];
tm.root[0]=i;
tm.count=0;
memo[1<<i][i]=tm;
}
int max=(1<<n)-1,nextState;
for(int state=1;state<max;state++){
for(int j=0;j<n;j++){
if((state&(1<<j))==0) continue;
tm=memo[state][j];
nextTime=tm;
speed=2000.0/(70.0+tm.w);
nextTime.count=tm.count+1;
for(int k=0;k<n;k++){
if((state&(1<<k))!=0) continue;
len=fabs(lens[j]-lens[k]);
nextTime.time=len/speed+tm.time;
nextTime.w=tm.w+ws[k];
nextTime.root[nextTime.count]=k;
nextState=state|(1<<k);
if(memo[nextState][k].time>nextTime.time || memo[nextState][k].time<0){
memo[nextState][k]=nextTime;
}
}
}
}
double ansTime=memo[max][0].time;
nextTime=memo[max][0];
for(int i=1;i<n;i++){
tm=memo[max][i];
if(ansTime>tm.time){
nextTime=tm;
ansTime=tm.time;
}
//printf("%lf\n",tm.time);
}
printf("%d",nos[nextTime.root[0]]);
for(int i=1;i<n;i++){
printf(" %d",nos[nextTime.root[i]]);
}
printf("\n");
}
int main(){
int n;
scanf("%d",&n);
calc(n);
}
----
----
*0147 Fukushimaken
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0147
解法
賢い方法を思いつかなかったのでコードサイズが膨らみました。
特に参考にならないと思いますので読み飛ばしてください。
順番に試しているだけです。
#include <stdio.h>
void seatDell(int dellTime,int *seats);
bool searchSheat(int *sheats,int man,int stayTime);
int seatCount=17;
int myMax=1000000000;
struct guest{
int arrivalTime;//到着時刻
int heads;//人数
int stayTime;//座ってる時間
int seatInTime;//座れた時間
};
int main()
{
int time=0,seats[17];
struct guest guests[100];
for(int i=0;i<seatCount;i++) seats[i]=0;
for(int i=0;i<100;i++){
guests[i].arrivalTime=i*5;
if(i%5==1){
guests[i].heads=5;
}else{
guests[i].heads=2;
}
guests[i].stayTime=17*(i%2)+3*(i%3)+19;
}
int p=0;
int dellTime=0;
while(p<100)
{
while(1)
{
if(guests[p].arrivalTime<=time)
{
if(searchSheat(seats,guests[p].heads,guests[p].stayTime)==true)
{
guests[p].seatInTime=time;
p++;
}else
{
break;
}
}else
{
break;
}
}
if(p>99) break;
for(int i=0;i<seatCount;i++){
if(dellTime>seats[i] && seats[i]>0) dellTime=seats[i];
}
if(time<guests[p].arrivalTime){
if(dellTime>guests[p].arrivalTime-time) dellTime=guests[p].arrivalTime-time;
}
if(dellTime==0){
dellTime=1;
}
time+=dellTime;
seatDell(dellTime,seats);
}
int t;
while(scanf("%d",&t)!=EOF){
printf("%d\n",guests[t].seatInTime-guests[t].arrivalTime);
}
}
bool searchSheat(int *seats,int man,int stayTime){
bool seatInFlag=false;
for(int i=0;i<seatCount-man+1;i++){
seatInFlag=true;
for(int j=0;j<man;j++){
if(seats[i+j]!=0){
seatInFlag=false;
}
}
if(seatInFlag==true){
for(int j=0;j<man;j++){
seats[i+j]=stayTime;
}
return true;
}
}
return false;
}
void seatDell(int dellTime,int *seats){
int t;
for(int i=0;i<seatCount;i++){
t=seats[i]-dellTime;
if(t>=0){
seats[i]=t;
}else{
seats[i]=0;
}
}
}
----
*0148 Candy and Class Flag
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0148
学校のクラスで「クラス旗」を保管する生徒を決める問題。
解法
非常に簡単な問題なので書くだけです。
#include<stdio.h>
int main(){
int n;
while(scanf("%d",&n)>0){
printf("3C%02d\n",(n-1)%39+1);
}
}
----
*0149 Eye Test
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0149
視力検査の結果をランクに分けて集計せよという問題。
解法
簡単な問題なのでＭａｐを使って集計するだけです。
#include<stdio.h>
#include<map>
int main(){
std::map<double,int> Rank;
double r,l;
int Lsum[4]={0,0,0,0},Rsum[4]={0,0,0,0};
Rank[2.1]=0;
Rank[1.1]=1;
Rank[0.6]=2;
Rank[0.2]=3;
while(scanf("%lf %lf",&l,&r)>0){
Lsum[(*Rank.upper_bound(l)).second]++;
Rsum[(*Rank.upper_bound(r)).second]++;
}
for(int i=0;i<4;i++){
printf("%d %d\n",Lsum[i],Rsum[i]);
}
}
----
*0150 Twin Prime
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0150&lang=jp
ｎ以下の最も大きな双子素数を表示せよという問題。
解法
双子素数は6ｎ-1と6ｎ+1になるという性質を使って気持ち高速化しました。
素数の世界は奥が深いので素数を求めるテクニックは無数にありますが、練習問題程度なら大体素朴な手法で解けます。
#include <stdio.h>
int main()
{
bool map[5005];
for(int i=0;i<5005;i++){
map[i]=true;
}
for(int i=3;i<103;i+=2){
for(int j=3*i;j<10001;j+=i*2){
map[j/2-1]=false;
}
}
int n;
scanf("%d",&n);
while(n!=0){
if(n<7){
printf("3 5\n");
}else{
n-=n%6==0?6:n%6;
for(int i=n;i>=0;i-=6){
if(map[(i-1)/2-1]==true && map[(i+1)/2-1]==true){
printf("%d %d\n",i-1,i+1);
break;
}
}
}
scanf("%d",&n);
}
}
