「AOJ231～240」の編集履歴（バックアップ）一覧に戻る
AOJ231～240 - (2012/07/11 (水) 14:15:30) のソース
*0231 Dangerous Bridge
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0231
橋の通行予定表から橋が壊れるほどの重量がかからないかを調べる問題。
解法
わたる順番と橋を渡り終える順番を時系列順に並べて一からシミュレートするだけです。
こういう簡単な問題は気楽に解ける分楽しいです。
１００マス計算宜しく、こういう簡単な問題を１００問並べた１００問プログラムとかあれば楽しいのですが。
#include<stdio.h>
#include<queue>
struct move{
int w,type,time;//wは重さ、0がわたり終わり1がわたり始め
bool operator<(const move m)const{
if(time!=m.time) return time>m.time;
return type>m.type;
}
};
void setData(int n){
std::priority_queue<move> qu;
move m;
int last;
for(int i=0;i<n;i++){
scanf("%d %d %d",&m.w,&m.time,&last);
m.type=1;
qu.push(m);
m.type=0;
m.time=last;
qu.push(m);
}
int allW=0;
bool allOK=true;
while(!qu.empty()){
m=qu.top();
qu.pop();
if(m.type==0){
allW-=m.w;
}else{
allW+=m.w;
}
if(allW>150){
allOK=false;
break;
}
}
printf("%s\n",allOK?"OK":"NG");
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0) break;
setData(n);
}
}
*0233 Book Arrangement
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0233
整数ｎに-10進数という写像を適用した結果を出力せよという問題。
解法
直観的に考えついたコードをそのまま書いてみたら何故かジャッジを通りました。
実はコードがなぜ奇麗に動くのか説明できません。
発想としては-10進数への変換過程を逆にシミュレートして10進数と一致するまで逆に計算しています。
実はt2=t2%tenがなぜ必要なのか上手く説明できないのです。
#include<stdio.h>
#include<stdlib.h>
void calc(long long int n){
long long int t1,t2,i=1,sum=0,ten=1,ten2=1,sig=1,ans=0;
if(n>0){
sig=-1;
i=0;
}
while(sum!=n){
ten*=10;
ten2*=10;
t1=n%ten;
i=(i+1)%2;
if(i==0){
t2=t1-sum+(t1==sum?0:ten2*sig);
}else{
t2=t1-sum;
}
t2=t2%ten;
ans+=abs(t2);
sum+=t2;
}
printf("%lld\n",ans);
}
int main(){
long long int n;
while(1){
scanf("%lld",&n);
if(n==0) break;
calc(n);
}
}
*0234 Aizu Buried Treasure
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0234
宝探しの掘削作業を模した簡素な問題です。
解法
一段ずつ動的計画法で解いてきます。
costMemoにｙ座標ｘ座標、酸素量を基準に発掘費用が一番安いルートのコストだけ残します。
この問題は右に掘って左に戻って右に戻るという可能性を忘れなければ典型的な動的計画法、比較的簡単な問題です。
このパタンを忘れているために不正解を喰らってる人が多いのではと考えます。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int w,h,m,f;
int costMemo[11][11][51];//x座標ｙ座標、酸素量の動的計画法
int map[10][10];
int mymax=100000000;
bool move(int nowH,bool *moveFirst,int& nowO2,int& cost,int s,int g,int mode){
//酸素量と今のコスト
int t,p,dw=g>s?1:g==s?0:-1;
int size=abs(g-s)+1;
p=s;
nowO2+=mode;//折り返す場合1を足す
for(int i=0;i<size;i++){
nowO2--;
if(nowO2<1) return false;
if(moveFirst[p]==true){
moveFirst[p]=false;
if(map[nowH][p]>=0){
t=(nowO2+map[nowH][p]);
nowO2=t>m?m:t;
}else{
cost-=map[nowH][p];
if(nowO2<2 || f<cost) return false;
}
}else{
if(nowO2<2) return false;
}
p+=dw;
}
p-=dw;
if(costMemo[nowH][p][nowO2]>cost){
costMemo[nowH][p][nowO2]=cost;
}
return true;
}
void catRoot(int y){
for(int x=0;x<w;x++){
int min=costMemo[y][x][m];
for(int o2=m-1;o2>=0;o2--){
if(costMemo[y][x][o2]>=min){
costMemo[y][x][o2]=mymax;
}else{
min=costMemo[y][x][o2];
}
}
}
}
void setData(){
int o;
scanf("%d %d %d",&f,&m,&o);
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
scanf("%d",&map[i][j]);
for(int o2=0;o2<=m;o2++){
costMemo[i][j][o2]=mymax;
}
}
}
bool moveFirst[11];//一度掘った部分をメモ
int nowO2;
int nowCost;
for(int y=0;y<h;y++){
for(int s=0;s<w;s++){
for(int o2=2;o2<=m;o2++){
if(y==0 && o2!=o) continue;
if(y!=0&&costMemo[y-1][s][o2]==mymax)continue;
for(int left=0;left<w;left++){
for(int right=0;right<w;right++){
for(int g=0;g<w;g++){
if(y==0){
nowCost=0;
nowO2=o;
}else{
nowCost=costMemo[y-1][s][o2];
nowO2=o2;
}
if(y==h-1)nowO2++;//最後の酸素量は0でもＯＫ
memset(moveFirst,true,11);//掘った部分を初期化
//掘り作業
if(!move(y,moveFirst,nowO2,nowCost,s,left,0))continue;
if(!move(y,moveFirst,nowO2,nowCost,left,right,1))continue;
if(!move(y,moveFirst,nowO2,nowCost,right,g,1))continue;
}
}
}
}
}
catRoot(y);
}
int ans=mymax;
for(int x=0;x<w;x++){
for(int o2=1;o2<=m;o2++){
ans=ans>costMemo[h-1][x][o2]?costMemo[h-1][x][o2]:ans;
}
}
printf(ans==mymax?"NA\n":"%d\n",ans);
}
int main(){
while(1){
scanf("%d %d",&w,&h);
if(w+h==0) break;
setData();
}
}
----
*0235 Sergeant Rian
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0235
島々でライアン軍層を助けるために橋を効率よく爆破する問題。
木構造で結ばれた島々の出発点から初めて、島から島へ橋で渡りながら最短の移動時間で全ての橋を爆破する時間を求める問題です。
解法
まず末端の島は計算に必要ないので切ります。
後は木構造上での最短経路は同じ橋を２度以上通らないという性質を利用して深さ優先探索で計算します。
この問題、たった１か所のポカミスに気付かず短時間で連続投稿し連続不正解を喰らってしまいました。
コード中の
ans=ans>sum?sum:ans;
moveOKs[now]=true;
return;
の部分のmoveOKs[now]=true;を書き忘れており、発想が正しいはずなのに不正解なので少し熱くなり4連続不正解を喰らってしまいました。
発想が正しいし正解まで後すこしの感じなのでジャッジデータでコードをテストするほうが楽かなという感じでもありましたが、やはり不正解は避けた方がいい。
手元でテストデータを作りしっかりテストすることの大切さを思い知りました。
反省です。
#include<stdio.h>
#include<string.h>
int g[21][21];
int bridgeMoveCount[21][21];//同じ橋を3度は通らないということを利用して全探索
bool moveOKs[21];
int allLand,ans;
int n;
int max=1000000000;
void saiki(int sum,int now,int moveCount){
bool tempMoveOK=false;
if(moveOKs[now]==true){
moveOKs[now]=false;
tempMoveOK=true;
moveCount++;
}
if(moveCount>=allLand){
ans=ans>sum?sum:ans;
moveOKs[now]=true;
return;
}
for(int i=1;i<=n;i++){
if(g[now][i]>0 && bridgeMoveCount[now][i]<2){
bridgeMoveCount[now][i]++;//同じ橋を２度以上通らないということを記録する
bridgeMoveCount[i][now]++;
saiki(sum+g[now][i],i,moveCount);
bridgeMoveCount[now][i]--;
bridgeMoveCount[i][now]--;
}
}
if(tempMoveOK==true){
moveOKs[now]=true;
}
}
void setMap(int n){
int start,goal,time;
memset(g,0,21*21*4);
memset(bridgeMoveCount,0,21*21*4);
memset(moveOKs,true,21);
ans=max;
for(int i=1;i<n;i++){
scanf("%d %d %d",&start,&goal,&time);
g[start][goal]=g[goal][start]=time;
}
int tempSum,p=0,dell[21],temp;
for(int i=2;i<=n;i++){
//計算量を抑えるために末端の島への橋は無視し消去します。橋が一本しかない＝末端の端になります
tempSum=0;
for(int j=1;j<=n;j++){
if(g[i][j]>0){
tempSum++;
}
}
if(tempSum==1){
dell[p]=i;
p++;
}
}
for(int i=0;i<p;i++){
temp=dell[i];
for(int j=1;j<=n;j++){
g[temp][j]=g[j][temp]=0;
}
}
allLand=n-p;
saiki(0,1,0);
printf("%d\n",ans);
}
int main(){
while(1){
scanf("%d",&n);
if(n==0) break;
setMap(n);
}
}
----
*0236 Alien Messages
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0236
与えられた盤面で一筆書きが可能かどうか調べる問題。
解法
一筆書きを真面目に深さ優先探索で求めます。
途中で線が盤面を分断してないか、スタートとゴールに到達できない線を引いてないかを調べることで枝がりします。
思考力より真面目な実装が試される問題です。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int map[10][10];
int checkMap[10][10];
int sx,sy,nowX,nowY;
int w,h,size;
int dxs[]={1,0,-1,0};
int dys[]={0,1,0,-1};
bool checkOK;
bool goalRootOK;
int check(int x,int y){
int nx,ny;
int count=0,sum=1;
checkMap[y][x]=-1;
for(int i=0;i<4;i++){
nx=x+dxs[i];
ny=y+dys[i];
if(checkMap[ny][nx]==0){
sum+=check(nx,ny);
if(checkOK==false) return sum;
}
if(checkMap[ny][nx]<1){
count++;
}
}
if(sx==x && sy==y){
goalRootOK=true;
}
if((nowX==x && nowY==y) || (sx==x && sy==y)){
}else{
if(count<2) checkOK=false;
}
return sum;
}
void putMap(){
printf("\n");
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++)printf("%2d",map[i][j]);
printf("\n");
}
printf("\n");
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++)printf("%2d",checkMap[i][j]);
printf("\n");
}
}
bool setCheck(int nX,int nY,int deep){
if(abs(sx-nX)+abs(sy-nY)>size-deep+1) return false;
if(3>deep || deep>=size-2) return true;
memcpy(checkMap,map,400);
checkMap[nY][nX]=checkMap[sy][sx]=0;
nowX=nX;
nowY=nY;
checkOK=true;
goalRootOK=false;
int tt=check(nX,nY);
if(tt==size-deep+1 && goalRootOK==true && checkOK==true){
return true;
}else{
return false;
}
}
bool goalOK;
void saiki(int x,int y,int deep){
if(setCheck(x,y,deep)==false){
return ;
}
if(deep!=size && deep!=0 && sx==x && sy==y){
return;
}
if(deep==size && sx==x && y==sy){
goalOK=true;
return;
}
int nx,ny;
for(int i=0;i<4;i++){
nx=x+dxs[i];
ny=y+dys[i];
if(map[ny][nx]==0){
map[ny][nx]=1;
saiki(nx,ny,deep+1);
if(goalOK==true) return;
map[ny][nx]=0;
}
}
}
void setData(){
size=0;
for(int i=0;i<=h+1;i++){
for(int j=0;j<=w+1;j++){
if(i==0 || j==0 || i==h+1 || j==w+1){
map[i][j]=1;
}else{
scanf("%d",&map[i][j]);
if(map[i][j]==0){
sy=i;
sx=j;
size++;
}
}
}
}
goalOK=false;
if(size<4 || size%2==1){
goalOK=false;
}else{
saiki(sx,sy,0);
}
if(goalOK==true){
printf("Yes\n");
}else{
printf("No\n");
}
}
int main(){
scanf("%d %d",&w,&h);
while(w!=0 || h!=0){
setData();
scanf("%d %d",&w,&h);
}
}
*0238 Time to Study
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0238
勉強時間を合計していくだけの問題。
さわりの問題なので５分で解けますね。
#include<stdio.h>
int main(){
int n,m,s,a,b;
while(1){
scanf("%d",&n);
if(n==0)break;
s=0;
scanf("%d",&m);
while(m--){
scanf("%d %d",&a,&b);
s+=b-a;
}
if(s<n)printf("%d\n",n-s);
else printf("OK\n");
}
}
*0239 Calorie Counting
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0239
カロリー摂取制限が与えられるので条件を満たす食べ物を出力する問題。
250制限なら250もOKということらしいです。
#include<stdio.h>
void calc(int n){
int no[1001],p[1001],q[1001],r[1001],c[1001];
for(int i=0;i<n;i++){
scanf("%d %d %d %d",&no[i],&p[i],&q[i],&r[i]);
c[i]=p[i]*4+q[i]*9+r[i]*4;
}
int u=0;
scanf("%d %d %d %d",&p[n],&q[n],&r[n],&c[n]);
for(int i=0;i<n;i++){
if(p[i]<=p[n]&&q[i]<=q[n]&&r[i]<=r[n]&&c[i]<=c[n]){
printf("%d\n",no[i]);
u++;
}
}
if(u==0)printf("NA\n");
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0)break;
calc(n);
}
}
*0240 Interest Rates
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0240
一位を取る気がないのにコードの短さで暫定一位を取ってしまった。
ショートコードなんて何もやってないのだが、、、
ショートコーダの方がこの問題に気づけばコードの長さは半分くらいになると思う。
#include<stdio.h>
#include<math.h>
void calc(int n){
int y,b,t,ansNo;
double r,maxR=0.0;
scanf("%d",&y);
while(n--){
scanf("%d %lf %d",&b,&r,&t);
r=t==1?(1.0+y*(r/100.0)):pow(1.0+r/100.0,y);
if(r>maxR){
maxR=r;
ansNo=b;
}
}
printf("%d\n",ansNo);
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0)break;
calc(n);
}
}
