0231 Dangerous Bridge
解法
わたる順番と橋を渡り終える順番を時系列順に並べて一からシミュレートするだけです。
こういう簡単な問題は気楽に解ける分楽しいです。
100マス計算宜しく、こういう簡単な問題を100問並べた100問プログラムとかあれば楽しいのですが。
#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
解法
直観的に考えついたコードをそのまま書いてみたら何故かジャッジを通りました。
実はコードがなぜ奇麗に動くのか説明できません。
発想としては-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
解法
一段ずつ動的計画法で解いてきます。
costMemoにy座標x座標、酸素量を基準に発掘費用が一番安いルートのコストだけ残します。
この問題は右に掘って左に戻って右に戻るという可能性を忘れなければ典型的な動的計画法、比較的簡単な問題です。
このパタンを忘れているために不正解を喰らってる人が多いのではと考えます。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int w,h,m,f;
int costMemo[11][11][51];//x座標y座標、酸素量の動的計画法
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でもOK
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
解法
まず末端の島は計算に必要ないので切ります。
後は木構造上での最短経路は同じ橋を2度以上通らないという性質を利用して深さ優先探索で計算します。
この問題、たった1か所のポカミスに気付かず短時間で連続投稿し連続不正解を喰らってしまいました。
コード中の
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]++;//同じ橋を2度以上通らないということを記録する
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
解法
一筆書きを真面目に深さ優先探索で求めます。
途中で線が盤面を分断してないか、スタートとゴールに到達できない線を引いてないかを調べることで枝がりします。
思考力より真面目な実装が試される問題です。
#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
#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
#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
#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);
}
}
最終更新:2012年07月11日 14:15