プログラマ専用SNS ミクプラ


https://dixq.net/forum/

プログラムの練習問題が解けない

https://dixq.net/forum/viewtopic.php?f=3&t=7977

ページ 1 ／ 1

プログラムの練習問題が解けない

Posted: 2011年3月04日(金) 17:29
by h
http://rose.u-aizu.ac.jp/onlinejudge/Pr ... 30&lang=jp
リンク先問題。
できるだけ自分の実力で解きたかったのですが、何度もテストデータで不正解の判定をくらってしまいます。

何が悪かったのか、ポカミスがないか、それとも考え違いか。
どなたかアドバイスをお願いします。

コード: 

#include <stdio.h>
#include <algorithm>
void upDown(int *bill,int *moves,int n);
void solve(int n);
int moves1[105],moves2[105];
int b1[105],b2[105];
int myMax=1000000000;


int main(){
	int n;
	scanf("%d",&n);
	while(n!=0){
		solve(n);
		scanf("%d",&n);
	}
}

void solve(int n){
	//ビルデータの読み込み
	for(int i=0;i<n;i++){
		scanf("%d",&b1[i]);
	}
	for(int i=0;i<n;i++){
		scanf("%d",&b2[i]);
		moves1[i]=moves2[i]=myMax;
	}
	moves1[0]=moves2[0]=0;
	upDown(b1,moves1,n);
	upDown(b2,moves2,n);
	int myMaxCount=1;
//ダイクストラ法の応用で解く、一階を0とし一階に梯子があればそれを上る。未踏もしくは梯子の先頭以外、滑る壁はmyMaxに設定
	while(myMaxCount>0 || myMax>moves1[n-1] || myMax>moves2[n-1]){
		if(myMax>moves1[n-1] || myMax>moves2[n-1]){
			printf("%d\n",std::min(moves1[n-1],moves2[n-1]));
			return ;
		}
		myMaxCount=0;
		for(int i=0;i<n;i++){
			if(moves1[i]==myMax)myMaxCount++;
			if(moves2[i]==myMax)myMaxCount++;
		}
		
		
		
		for(int i=0;i<n;i++){
			if(myMax>moves1[i]){
				int t=moves1[i]+1;
				moves2[i  ]=std::min(t,moves2[i  ]);
				moves2[i+1]=std::min(t,moves2[i+1]);
				moves2[i+2]=std::min(t,moves2[i+2]);
			}
		}
		upDown(b2,moves2,n);

		for(int i=0;i<n;i++){
			if(myMax>moves2[i]){
				int t=moves2[i]+1;
				moves1[i  ]=std::min(t,moves1[i  ]);
				moves1[i+1]=std::min(t,moves1[i+1]);
				moves1[i+2]=std::min(t,moves1[i+2]);
			}
		}
		upDown(b1,moves1,n);
		
		
		
		for(int i=0;i<n;i++){
			if(moves1[i]==myMax)myMaxCount--;
			if(moves2[i]==myMax)myMaxCount--;
		}
	}
	printf("NA\n");
	return ;
}


void upDown(int *bill,int *moves,int n){
	bool upFlag=false;
	int upMin;
	//梯子を上る処理
	for(int i=0;i<n;i++){
		if(bill[i]==1 && myMax>moves[i] && upFlag==false){
			upMin=moves[i];
			moves[i]=myMax;
			upFlag=true;
		}else if(bill[i]!=1 && upFlag==true){
			upFlag=false;
			moves[i-1]=upMin;
		}else if(i==n-1 && upFlag==true){
			moves[i]=std::min(upMin,moves[i]);
			break ;
		}
		if(upFlag==true){
			upMin=std::min(upMin,moves[i]);
			moves[i]=myMax;
		}
	}
	bool downFlag=false;
	int downMin;
	//滑り降りる処理
	for(int i=n-1;i>=0;i--){
		if(bill[i]==2 && myMax>moves[i] && downFlag==false){
			downMin=moves[i];
			downFlag=true;
			moves[i]=myMax;
		}else if(bill[i]!=2 && downFlag==true){
			moves[i]=std::min(downMin,moves[i]);
			downFlag=false;
		}else if(i==0 && downFlag==true){
			moves[0]=0;
			break ;
		}
		if(downFlag==true){
			downMin=std::min(downMin,moves[i]);
			moves[i]=myMax;
		}
	}
}

Re: プログラムの練習問題が解けない

Posted: 2011年3月05日(土) 09:53
by たいちう
プログラムを丁寧に見てはいませんが、サンプルの２題は解けているようです。
それ以外の入力は入手できないのでしょうか？
誤判定する入力が判れば、デバッグはしやすくなりますが。
入手できない場合、自分で作るしかありません。
ビルの高さが最小・最大の場合など、極端な条件でバグは検出しやすいです。
様々な条件を考え、手で解く場合とプログラムで解く場合の違いを見つけて下さい。

その他、問題の解釈を勘違いしている可能性、
入出力のルールが間違っている可能性、等があります。
後者については、他の問題で正答しているならば多分問題ないでしょうが。
アルゴリズムが悪く一定以上の処理時間がかかるとエラーにされるとかいうことは
ないですか？レギュレーションも確認した方が良いでしょう。
問題公開後、あまり日が経っていないならば、
サイト側が誤判定している可能性もありますね。

> できるだけ自分の実力で解きたかったのですが、
> 何度もテストデータで不正解の判定をくらってしまいます。

人に頼ってまで正解を得るというのはサイトの趣旨に反するような気がします。
では、どうしたら自分で解けるようになるのか？というのも難しい問題ですが。
少なくとも間違いと言う事は教えてくれるので、もう少し自分でできることが
あるのではないでしょうか。

Re: プログラムの練習問題が解けない

Posted: 2011年3月05日(土) 10:48
by 五反田
以下に適当に作ったデータと正解するプログラムの出力を貼っておきます。
自分が書いたプログラムの出力と見比べてデバグしてみてください。

入力
► スポイラーを表示
出力
► スポイラーを表示

Re: プログラムの練習問題が解けない

Posted: 2011年3月05日(土) 12:46
by h
ありがとうございます。
問題解けました。

テストデータで試してみる物ですね。
多分、右左右左の順番でジャンプするのと左右左右の順番でジャンプする場合の一回のジャンプの違いを忘れていたのと
最上階が梯子だった場合への対処を忘れていたのが原因見たいです。

私のコード3ＫＢ越えで一番長いコードでした。

問題は解けたけど、最下位、自分のレベルの低さを実感します。
皆どうやってコードを短くしたのか。

追加質問をします。
今回の問題はこういうい考え方をすればコードが短くなる。
という点でアドバイスを頂けたらと思います。

Re: プログラムの練習問題が解けない

Posted: 2011年3月05日(土) 12:55
by 五反田
解けたようでなによりです。

短いコードということですが、「AOJ 問題番号」で検索をかけてみてください。
その問題を解いた方のソースコードや解答の方針が見つかる場合があります。
そのコードが短いようだったら、それを参考にすればよいかと思います。

Re: プログラムの練習問題が解けない

Posted: 2011年3月05日(土) 13:00
by xxx
コードの短さは関係ないと思いますがね
とりあえず変数名1文字にする、main関数のみで処理する、改行しないあたりがいいんじゃないでしょうか
私が書いたコードですが見やすいとは思えないでしょうね
長くても見やすいコードを書いたほうがいいと思います
コストの増え方は1づつなので素直に幅優先しました

コード: 

#include<iostream>
#include<queue>
#include<map>
#include<cstring>
#include<cstdio>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef pair<int,int> P;
typedef pair<P,int> PP;
int bfs(int n,int b[2][100])
{
  queue<PP> q;
  bool used[2][100];memset(used,0,sizeof(used));
  rep(i,2)q.push(PP(P(i,0),0));
  while(!q.empty()){
    PP p=q.front(); q.pop();
    int l=p.first.first;
    int f=p.first.second;
    int c=p.second;
    if(b[l][f]==1){
      while(f+1<n&&b[l][f+1]==1)f++;
    }
    while(f&&b[l][f]==2)f--;
    if(used[l][f])continue;
    used[l][f]=true;
    if(f==n-1)return c;
    rep(i,3)if(f+i<n){
      q.push(PP(P(l?0:1,f+i),c+1));
    }
  }
  return -1;
}
int main(void)
{
  int n;
  int b[2][100],res;
  for(;;){
    scanf("%d",&n); if(!n)break;
    rep(i,2) rep(j,n)
      scanf("%d",&b[i][j]);
    res=bfs(n,b);
    if(~res)printf("%d\n",res);
    else puts("NA");
  }
  return 0;
}

Re: プログラムの練習問題が解けない

Posted: 2011年3月05日(土) 16:23
by h
こんなにコード短くなるんですね。
うーんきっと僕の考え方には何か無駄が多いのかも。
長くても分かりやすいコード、理解です。
All times are UTC+09:00
ページ 1 ／ 1
Powered by phpBB® Forum Software © phpBB Limited
https://www.phpbb.com/