「AOJ191～200」の編集履歴（バックアップ）一覧に戻る
AOJ191～200 - (2012/07/16 (月) 18:30:18) のソース
*0191 Baby Tree
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0191
植物に色々な種類の肥料をやって、一番成長する肥料のやり方を探しその時できる植物のサイズをこたえる問題。
解法
動的計画法で各ターンごとに計算していくだけです。
#include<stdio.h>
#include<string.h>
double fertilizer[102][102];
void calc(int n,int m){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%lf",&fertilizer[i][j]);
}
}
double memo[2][101];
for(int i=0;i<n;i++){
memo[0][i]=1.0;
}
int now,next=0;
double size,nextSize;
for(int i=0;i<m-1;i++){
now=i%2;
next=(i+1)%2;
for(int j=0;j<n;j++){
memo[next][j]=0;
}
for(int j=0;j<n;j++){
size=memo[now][j];
for(int k=0;k<n;k++){
nextSize=size*fertilizer[j][k];
if(memo[next][k]<nextSize){
memo[next][k]=nextSize;
}
}
}
}
double ans=0;
for(int i=0;i<n;i++){
ans=memo[next][i]>ans?memo[next][i]:ans;
}
printf("%.2lf\n",ans);
}
int main(){
int n,m;
while(1){
scanf("%d %d",&n,&m);
if(n==0 && m==0) break;
calc(n,m);
}
}
----
*0192 Tsuruga Parking
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0192
駐車場にやってくる車が出入りします。
各車の駐車時間が与えられるので車の出た順番を答えよという問題。
ただし駐車場は2段式が連なった運営であり、下の車が出ない限り上の車が出られない構造になっています。
解法
一つの駐車場をstack構造のクラスで表現します。
後は車のはいる時刻出る時刻でマージソートしながら整理するだけです。
#include<stdio.h>
#include<stdlib.h>
#include<stack>
#include<vector>
struct Perk{
int carCount;//2台までしか入らない
std::stack<int> time;//2台まで
std::stack<int> carNo;
void carAdd(int CarNo,int carTime){
if(carCount==2) return ;
carCount++;
time.push(carTime);
carNo.push(CarNo);
}
int carPop(){
if(carCount==0) return -1;
int t=carNo.top();
carNo.pop();
time.pop();
carCount--;
return t;
}
};
void Simulation(int m,int n){
int nowCarNo=1,inCarCount,outPerk;
int nowTime=0,minTime,tempTime;
int maxTime=1000000000;
Perk perks[11];
std::vector<int> ans;
std::stack<int> carNoStack;
std::stack<int> carTime;
for(int i=0;i<m;i++)perks[i].carCount=0;
while(nowCarNo<=n || inCarCount>0){
inCarCount=0;
minTime=maxTime;
for(int i=0;i<m;i++)
{
//まず入ってる車の中で最短時間を探す
if(perks[i].carCount==0) continue;
tempTime=perks[i].time.top();
inCarCount+=perks[i].carCount;
if(tempTime<minTime){
minTime=tempTime;
outPerk=i;
}
}
int inCarTime=nowCarNo>n?maxTime:nowCarNo*10;
inCarTime=nowTime>inCarTime?nowTime:inCarTime;
//入る車と出る車でマージソートを行う
if(inCarCount>0 && (inCarCount==m*2 || minTime<=inCarTime)){
//出庫を先にする
nowTime=nowTime>minTime?nowTime:minTime;
ans.push_back(perks[outPerk].carPop());
inCarCount--;
}else if(nowCarNo<=n){
scanf("%d",&tempTime);
bool addOK=false,addOK2=false;
nowTime=nowTime>inCarTime?nowTime:inCarTime;
int inPerk,dTime=maxTime,outTime=nowTime+tempTime,tempD;
for(int i=0;i<m;i++){
if(perks[i].time.empty()==true){
perks[i].carAdd(nowCarNo,tempTime+nowTime);
addOK=true;
nowCarNo++;
inCarCount++;
break;
}
tempD=perks[i].time.top()-outTime;
if(tempD<dTime && tempD>=0 && perks[i].carCount==1){
dTime=tempD;
inPerk=i;
addOK2=true;
}
}
if(addOK==true) continue;
if(addOK2==true){
perks[inPerk].carAdd(nowCarNo,outTime);
nowCarNo++;
inCarCount++;
}else{
for(int i=0;i<m;i++){
if(perks[i].carCount==1){
tempD=outTime-perks[i].time.top();
if(tempD<dTime){
inPerk=i;
dTime=tempD;
}
}
}
perks[inPerk].carAdd(nowCarNo,outTime);
nowCarNo++;
inCarCount++;
}
}
}
printf("%d",ans[0]);
for(int i=1;i<n;i++)printf(" %d",ans[i]);
printf("\n");
}
int main(){
int m,n;
while(1){
scanf("%d %d",&m,&n);
if(m==0 && n==0) break;
Simulation(m,n);
}
}
----
*0193 Deven-Eleven
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0193
ヘクスで表現されたマップでマップ上に新しく置くコンビニ店の支配領域が最大となる場合の数を求める問題。
あるHexは一番近いコンビニの支配領域となり、同じ距離に二つコンビニがある場合はそのヘクスはどのコンビニの支配領域にも属さない。
解法
升目の情報を表すHexクラスを用意します
まず各店舗を出発点に全ての店舗の初期位置をHex変数で表し優先順位付きキューに入れていきます。
まずは幅優先探索で各店舗に近いHexを優先してどのマスがどの店舗に属するかを決定します。
決定が終わればsaiki関数(最初深さ優先探索で実装しようとしたな残り)の中で優先順位付きキューを利用した幅優先探索をして、候補地からどのマスまで帰属できるかを計算します。
point変数に座標を保持させ、memoで同じ升目を重複して探索しないようにして支配領域の数を数えます。
６角形であることを除けば四角形の問題と問題的には同質な簡単な問題です。
簡単な問題なのですが、一か所だけのポカミスを見落として数度不正回やタイムリミットを食らった問題でした。
#include<stdio.h>
#include <queue>
#include<set>
int guDxs[]={1,1,0,-1,0,1};
int guDys[]={0,-1,-1,0,1,1};
int kiDxs[]={1,0,-1,-1,-1,0};
int kiDys[]={0,-1,-1,0,1,1};
int m,n;
struct hex{
int shop,len,x,y;//shopはデバック用で本当は計算に必要ないデータ
bool operator<(const hex h)const{
return len>h.len;
}
};
struct point{
int x,y;
bool operator<(const point p)const{
if(x!=p.x)return x<p.x;
return y<p.y;
}
};
hex map[102][102];
int saiki(int x,int y,int shopNo){
int ans=1;
hex h,next;
h.x=x;
h.y=y;
h.len=0;
h.shop=shopNo;
std::priority_queue<hex> qu;
std::set<point> memo;
point pNow;
qu.push(h);
pNow.x=x;
pNow.y=y;
memo.insert(pNow);
int nowX,nowY,nx,ny;
int *dxs,*dys;
while(qu.empty()==false){
h=qu.top();
qu.pop();
nowX=h.x;
nowY=h.y;
if((nowY)%2==1){
dxs=kiDxs;
dys=kiDys;
}else{
dxs=guDxs;
dys=guDys;
}
h.len++;
for(int i=0;i<6;i++){
nx=nowX+*(dxs+i);
ny=nowY+*(dys+i);
if(nx<1 || m<nx || ny<1 || n<ny || map[ny][nx].len<=h.len) continue;
pNow.x=nx;
pNow.y=ny;
if(memo.find(pNow)!=memo.end())continue;
memo.insert(pNow);
next.x=nx;
next.y=ny;
next.len=h.len;
ans++;
qu.push(next);
}
}
return ans;
}
void myprint(){
printf("\n");
for(int i=1;i<=n;i++){
if(i%2==0){
printf("\n ");
}else{
printf("\n ");
}
for(int j=1;j<=m;j++){
printf("%2d",map[i][j]);
}
}
printf("/");
}
void setData(){
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
map[i][j].shop=-1;
map[i][j].len=1000000;
map[i][j].x=j;
map[i][j].y=i;
}
}
int s;
scanf("%d",&s);
std::priority_queue<hex> qu;
hex h;
h.len=0;
for(int i=0;i<s;i++){
scanf("%d %d",&h.x,&h.y);
h.shop=i;
map[h.y][h.x].shop=i;
map[h.y][h.x].len=0;
qu.push(h);
}
int *dxs,*dys,nx,ny,nowX,nowY;
while(qu.empty()==false){
h=qu.top();
qu.pop();
nowX=h.x;
nowY=h.y;
h.len++;
if((nowY)%2==1){
dxs=kiDxs;
dys=kiDys;
}else{
dxs=guDxs;
dys=guDys;
}
for(int i=0;i<6;i++){
nx=nowX+*(dxs+i);
ny=nowY+*(dys+i);
if(nx<1 || m<nx || ny<1 || n<ny || map[ny][nx].len<h.len) continue;
if(map[ny][nx].len==h.len && h.shop!=map[ny][nx].shop){
map[ny][nx].shop=-1;
continue;
}else if(map[ny][nx].len==h.len){
continue;
}else{
map[ny][nx].shop=h.shop;
map[ny][nx].len=h.len;
h.x=nx;
h.y=ny;
qu.push(h);
}
}
}
int tt,t,x,y,ans=0;
int temp;
//myprint();
scanf("%d",&t);
for(int i=0;i<t;i++){
scanf("%d %d",&x,&y);
if(map[y][x].len!=0){
temp=saiki(x,y,s);
ans=temp>ans?temp:ans;
}
}
printf("%d\n",ans);
}
int main(){
while(scanf("%d",&m)!=EOF){
if(m==0) break;
scanf("%d",&n);
setData();
}
}
----
*0194 Byakko Delivery Company
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0194&lang=jp
超シンプルにしたカーナビシステムの実装問題。
解法
渋滞、信号、工事の座標をそれぞれMapやSetに入れていきます。
後はこれと照合しながらmemoにより同じ状態を枝刈しながら幅優先探索で片が付きます。
これ問題を簡単にするために無限ループがないとしているあたり出題者のほうで手心を加えてるようです。
#include<stdio.h>
#include<map>
#include<queue>
#include<set>
#include<algorithm>
#include<string.h>
int arrows[4][3]={{0,1,3},
{0,1,2},
{1,2,3},
{0,2,3}};//右0、上1、左2、下3
int dxs[]={1,0,-1,0};
int dys[]={0,-1,0,1};
struct stop{
//信号,周期はmapのvalに放り込む
int x,y;
bool operator<(const stop& s)const{
if(x!=s.x)return x<s.x;
return y<s.y;
}
};
struct evePos{
int r1,c1,r2,c2;
//渋滞か工事中の表現
bool operator<(const evePos& j)const{
if(r1!=j.r1)return r1<j.r1;
if(c1!=j.c1)return c1<j.c1;
if(r2!=j.r2)return r2<j.r2;
return c2<j.c2;
}
};
struct car{
int time,arrow;
evePos pos;//手抜きをして構造体を流用、トラックが前にいたポジションと今のポジション
bool operator<(const car& c)const{
return time>c.time;//優先順位付きキュー用
}
car move(int nextArrow){
car re;
re.pos.r2=pos.r1;//今いるポジションを過去にする
re.pos.c2=pos.c1;
re.pos.r1=pos.r1+dys[nextArrow];
re.pos.c1=pos.c1+dxs[nextArrow];
re.time=time;
re.arrow=nextArrow;
return re;//タイム計算は後でする
}
};
bool memo[101][21][21][4];//タイム、座標、向きで同じ状態を探索してないか
void calc(int h,int w){
std::map<stop,int> stops;//信号
std::priority_queue<car> pQ;
std::set<evePos> stops2;//工事
std::map<evePos,int> jams;//渋滞
memset(memo,false,sizeof(memo));
int d,ns,v1,v2,k,nc,nj;
char h1,h2,t1;
stop s1;
scanf("%d %d",&d,&ns);
for(int i=0;i<ns;i++){
scanf("%c%c-%d %d",&t1,&h1,&v1,&k);
s1.y=h1-'a';//0ベースで読み込み
s1.x=v1-1;
stops[s1]=k;
//printf("<%c %d>",h1,v1);
}
scanf("%d",&nc);
evePos e1;
for(int i=0;i<nc;i++){
scanf("%c%c-%d%c%c-%d",&t1,&h1,&v1,&t1,&h2,&v2);
e1.r1=h1-'a';
e1.c1=v1-1;
e1.r2=h2-'a';
e1.c2=v2-1;
stops2.insert(e1);
std::swap(e1.r1,e1.r2);//逆向きも登録する
std::swap(e1.c1,e1.c2);
stops2.insert(e1);
//printf("<%c %d %c %d>",h1,v1,h2,v2);
}
scanf("%d",&nj);
for(int i=0;i<nj;i++){
scanf("%c%c-%d%c%c-%d %d",&t1,&h1,&v1,&t1,&h2,&v2,&k);
e1.r1=h1-'a';
e1.c1=v1-1;
e1.r2=h2-'a';
e1.c2=v2-1;
jams[e1]=k;;
std::swap(e1.r1,e1.r2);//逆向きも登録する
std::swap(e1.c1,e1.c2);
jams[e1]=k;
//printf("<%c %d %c %d>",h1,v1,h2,v2);
}
car myCar,nextCar;
myCar.time=myCar.arrow=0;
int gx,gy;
scanf("%c%c-%d%c%c-%d",&t1,&h1,&v1,&t1,&h2,&v2);
gx=v2-1;
gy=h2-'a';
myCar.pos.r1=h1-'a';
myCar.pos.c1=v1-1;//0ベース
pQ.push(myCar);
while(!pQ.empty()){
myCar=pQ.top();
pQ.pop();
if(myCar.pos.r1==gy&&myCar.pos.c1==gx)break;//ゴールに到達
//printf("<x=%d y=%d a=%d t=%d>",myCar.pos.c1,myCar.pos.r1,myCar.arrow,myCar.time);
//scanf("%c",&t1);
myCar.time+=d;
for(int i=0;i<3;i++){
nextCar=myCar.move(arrows[myCar.arrow][i]);
s1.y=nextCar.pos.r1;//信号で止まらないかのチェック
s1.x=nextCar.pos.c1;
if(s1.x<0 || w<=s1.x || s1.y<0 || h<=s1.y)continue;//マップ外に飛び出した
if(stops2.find(nextCar.pos)!=stops2.end())continue;//工事に引っかかった
if(jams.find(nextCar.pos)!=jams.end()){
nextCar.time+=jams[nextCar.pos];//渋滞に引っかかった
}
if(stops.find(s1)!=stops.end()){
int t1=(nextCar.time/stops[s1])%2;//0なら東西停止、1なら南北停止
int t2=nextCar.arrow%2;//東西なら0、1なら南北移動中
if(t1==t2)continue;//信号に引っかかった
}
if(nextCar.time>100)continue;//100分以内という条件を満たしてない
if(memo[nextCar.time][s1.x][s1.y][nextCar.arrow]==true)continue;//過去にこの状態を通った
memo[nextCar.time][s1.x][s1.y][nextCar.arrow]=true;//この状態はもう終わってる
pQ.push(nextCar);
}
}
printf("%d\n",myCar.time);
}
int main(){
int h,w;
while(1){
scanf("%d %d",&h,&w);
if(h==0&&w==0)break;
calc(h,w);
}
}
----
*0195 What is the Most Popular Shop in Tokaichi?
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0195
売上げ記録から一番売り上げのいい店を求める問題です。
解法
計算して最高値を保存するだけです。
#include<stdio.h>
int main(){
int s1,s2,ans,no,i;
while(1){
scanf("%d %d",&s1,&s2);
ans=s1+s2;
if(ans==0)break;
no=0;
for(i=1;i<5;i++){
scanf("%d %d",&s1,&s2);
if(ans<s1+s2){
ans=s1+s2;
no=i;
}
}
printf("%c %d\n",no+'A',ans);
}
}
----
*0196 Baseball Championship
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0196
ベースボールの戦績表を元に上位のチームから出力する問題。
解法
チーム構造体を定義してソート基準を指定するだけです。
これくらい簡単な問題ならＥｘｃelで十分な気もします。
#include<stdio.h>
#include <algorithm>
struct team{
int v,l,no;
char name;
bool operator<(const team t)const{
if(v!=t.v) return v>t.v;
if(l!=t.l) return l<t.l;
return no<t.no;
}
};
void setTeam(int n){
team teams[11];
int t;
for(int i=0;i<n;i++){
scanf(" %c",&teams[i].name);
teams[i].v=teams[i].l=0;
teams[i].no=i;
for(int j=1;j<n;j++){
scanf("%d",&t);
if(t==0)teams[i].v++;
if(t==1)teams[i].l++;
}
}
std::sort(teams,teams+n);
for(int i=0;i<n;i++){
printf("%c\n",teams[i].name);
}
}
int main(){
int n;
while(scanf("%d",&n),n>0){
setTeam(n);
}
}
----
*0197 Greatest Common Divisor: Euclidean Algorithm
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0197
最大公約数を求める手法が指定されるのでそれを実装する問題。
解法
指定通りに実装するだけです。
#include<stdio.h>
#include<algorithm>
void gcd(int x,int y){
if(y>x) std::swap(x,y);
int count=0;
while(y>0){
x=x%y;
std::swap(x,y);
count++;
}
printf("%d %d\n",x,count);
}
int main(){
int x,y;
while(1){
scanf("%d %d",&x,&y);
if(x==0 && y==0) break;
gcd(x,y);
}
}
----
*0198 Trouble in Artist Shinagawa's Artifact
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0198
色塗りされた複数のキューブのなかから同じ塗り方をされているものを探す問題。
解法
高速なほうと分かりやすい方どちらを掲載するか悩みました。
データ量が小さいことを加味して分かりやすい方を掲載します。
キューブを一つずつ確認して、回した場合の全パタンをメモしていきます。
そして新しいキューブが来るたびに記憶した内容と照合し見つからなければメモに追加、あれば重複分として数えます。
この方法で十分速度が出ます。
もしデータ量が増えた場合は別の手法を使います。
回転して同じになるものでグループ分けをして、与えられたキューブがどのグループに属するか分類して数えることで高速化できます。
群論でいうところの同値条件の概念を使い色塗りされたキューブという集合を分割するわけです。
#include<stdio.h>
#include<set>
#include<string>
using namespace std;
set<string> memo;
void flatRound(string& xai){
char t=xai[2];
xai[2]=xai[1];
xai[1]=xai[3];
xai[3]=xai[4];
xai[4]=t;
memo.insert(xai);
}
void northRound(string& xai){
char t=xai[0];
xai[0]=xai[1];
xai[1]=xai[5];
xai[5]=xai[4];
xai[4]=t;
}
void eastRound(string& xai){
char t=xai[0];
xai[0]=xai[3];
xai[3]=xai[5];
xai[5]=xai[2];
xai[2]=t;
}
void allRoundIn(string xai){
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
flatRound(xai);
}
eastRound(xai);
}
northRound(xai);
for(int i=0;i<4;i++){
flatRound(xai);
}
northRound(xai);
northRound(xai);
for(int i=0;i<4;i++){
flatRound(xai);
}
}
void setData(int n){
char text[8];
string xai="123456";
int redundancy=0;
memo.clear();
for(int i=0;i<n;i++){
for(int j=0;j<6;j++){
scanf("%s",text);
xai[j]=text[0];
}
if(memo.find(xai)==memo.end()){
allRoundIn(xai);
}else{
redundancy++;
}
}
printf("%d\n",redundancy);
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0) break;
setData(n);
}
}
----
*0199 Chairs Where Demanding People Sit
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0199
並んだ椅子に座る時、座る場所を決定するルールがそれぞれ違う4つの国の人が椅子にやってきます。
それぞれの国の人が椅子に座るルールと来た順序が与えられるので、最終的にどのように全員が座っているかを求める問題。
解法
Ａ、Ｂ，Ｃ，Ｄ4タイプごとの椅子の座り方を素直に実装してみました。
Ｄ国人の場合、もう少し奇麗な処理があるかもしれません。
#include<stdio.h>
#include<string.h>
char sheets[104];//両端は番兵
int n,m;
void addA(char type){
for(int i=1;i<=n;i++){
if(sheets[i]=='#'){
sheets[i]=type;
return;
}
}
}
void addB(){
for(int i=n;i>0;i--){
if(sheets[i-1]!='A' && sheets[i+1]!='A' && sheets[i]=='#'){
sheets[i]='B';
return ;
}
}
addA('B');
}
void addC(bool first){
if(first==true){
int center=n%2==1?(n+1)/2:n/2+1;
sheets[center]='C';
return;
}
for(int i=1;i<=n;i++){
if(sheets[i]!='#' && sheets[i+1]=='#' && i<n){
sheets[i+1]='C';
return;
}
if(sheets[i]!='#' && sheets[i-1]=='#' && i>1){
sheets[i-1]='C';
return ;
}
}
}
void addD(bool first){
if(first==true){
sheets[1]='D';
return ;
}
int maxLen=-1,nowLen=0,leftLen=-1;
int left=0,ansCenter;
for(int i=1;i<=n;i++){
if(sheets[i]=='#'){
if(i==n){
if(nowLen>(maxLen-1)/2 && nowLen>leftLen){
ansCenter=n;
}
break;
}
if(nowLen==0){
left=i;
}
nowLen++;
}else{
if(nowLen==0) continue;
if(left==1){
leftLen=nowLen-1;
ansCenter=left;
}else if((nowLen-1)/2>(maxLen-1)/2 && (nowLen-1)/2>leftLen){
maxLen=nowLen;
ansCenter=(left+i-1)/2;
//printf("(%d %d)",left,i);
}
nowLen=0;
}
}
sheets[ansCenter]='D';
}
void setData(){
char t;
bool first=true;
for(int i=0;i<m;i++){
scanf(" %c",&t);
if(t=='A'){
addA('A');
}else if(t=='B'){
addB();
}else if(t=='C'){
addC(first);
}else{
addD(first);
}
first=false;
}
sheets[n+1]='\0';
printf("%s\n",&sheets[1]);
}
int main(){
while(scanf("%d %d",&n,&m),n+m>0){
memset(sheets,'#',104);
setData();
}
}
----
*0200 Traveling Alone: One-way Ticket of Youth
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0200
鉄道旅行の最短タイム、最小コストを求める問題。
解法
ワーシャルフロイド法を適用するだけです。
#include<stdio.h>
int max=1000000000;
void calc(int map[101][101],int m){
int t;
for(int y=1;y<=m;y++){
for(int x=1;x<=m;x++){
if(map[x][y]==max)continue;
for(int i=1;i<=m;i++){
t=map[x][y]+map[y][i];
if(t<map[x][i]){
map[x][i]=t;
}
}
}
}
}
void setMap(int n,int m){
int timeMap[101][101];
int costMap[101][101];
for(int i=1;i<=m;i++){
for(int j=1;j<=m;j++){
timeMap[i][j]=costMap[i][j]=max;
}
}
int a,b,cost,time;
for(int i=0;i<n;i++){
scanf("%d %d %d %d",&a,&b,&cost,&time);
timeMap[a][b]=timeMap[b][a]=time;
costMap[a][b]=costMap[b][a]=cost;
}
calc(timeMap,m);
calc(costMap,m);
int k,p,q,r;
scanf("%d",&k);
while(k--){
scanf("%d %d %d",&p,&q,&r);
if(r==0){
printf("%d\n",costMap[p][q]);
}else{
printf("%d\n",timeMap[p][q]);
}
}
}
int main(){
int n,m;
while(scanf("%d %d",&n,&m),n+m>0){
setMap(n,m);
}
}
