「AOJ231～240」の編集履歴（バックアップ）一覧に戻る
AOJ231～240 - (2011/09/21 (水) 23:53:46) のソース
*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
宝探しの掘削作業を模した簡素な問題。
解法
書きかけのコードです。
問題そのものは簡単な方なのでポカミスのみが気になる問題です。
横に掘り進む時右に行って左に行って右に戻ってから下に掘る場合を考えないといけないだけのはずです。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int w,h,m,f;
int costMemo[11][11][51];//x座標ｙ座標、酸素量の動的計画法
int map[10][10];
bool move(int nowH,bool moveFirst[11],int& nowO2,int& cost,int s,int g){
//酸素量と今のコスト
int t,p,dw=g>s?1:g==s?0:-1;
int size=abs(g-s)+1;
p=s;
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;
}
}
p+=dw;
}
p-=dw;
if(costMemo[nowH][p][nowO2]==0 || costMemo[nowH+1][p][nowO2]>cost){
costMemo[nowH][p][nowO2]=cost;
}
return true;
}
void setData(){
int o;
scanf("%d %d %d",&f,&m,&o);
memset(costMemo,0,4*11*11*51);
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
scanf("%d",&map[i][j]);
}
}
bool moveFirst[11];
int nowO2;
int nowCost;
for(int y=0;y<h;y++){
for(int s=0;s<w;s++){
for(int o2=0;o2<=50;o2++){
if(y==0 && o2!=o) continue;
if(y!=0&&costMemo[y][s][o2]==0)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][s][o2];
nowO2=o2;
}
memset(moveFirst,true,11);
if(!move(y,moveFirst,nowO2,nowCost,s,left))continue;
if(!move(y,moveFirst,nowO2,nowCost,left,right))continue;
if(!move(y,moveFirst,nowO2,nowCost,right,g))continue;
}
}
}
}
}
}
}
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);
}
}
