第８回日本情報オリンピック予選 第五問

[みけCAT]

第８回日本情報オリンピック予選　第五問のプログラムを書いています。
コンパイルエラーは出ないのですが、アクセス違反が起こるなどうまく動きません。
標準入力から入力し、標準出力に出力するようにしています。
どこが悪いか教えていただけるとありがたいです。
お願いします。

コード:

#include <stdio.h>
#include <stdlib.h>

typedef struct _cards {
	struct _cards *prev;
	int start;
	int end;
	struct _cards *next;
} cards;

int main(void) {
	/*情報変数*/
	int syafflenum;
	int howmanycards;
	int p,q,r;
	/*シャッフル用変数*/
	int i;
	cards* first;		/*カードの最初*/
	cards* points[6];	/*シャッフルするポイント*/
	int s1,s2;			/*シャッフルする位置*/
	int currentnum;		/*今何枚目のカードか*/
	int nownum;			/*今の束に何枚のカードがあるか*/
	cards* currentcard;	/*現在操作中のカード*/
	/*シャッフルの境目*/
	cards* s1last;
	cards* s2first;
	cards* s2last;
	cards* s3first;
	/*カードを数える*/
	int count;
	int flag;
	int start;
	int end;
	/*情報の読み込み*/
	scanf("%d",&howmanycards);
	scanf("%d",&syafflenum);
	scanf("%d %d %d",&p,&q,&r);
	/*カードの準備*/
	first=malloc(sizeof(cards));
	first->prev=NULL;
	first->start=1;
	first->end=howmanycards;
	first->next=NULL;
	/*シャッフル*/
	for(i=0;i<syafflenum;i++) {
		/*どこをシャッフルするか*/
		scanf("%d %d",&s1,&s2);
		/*シャッフル位置の特定*/
		currentnum=0;
		currentcard=first;
		/*シャッフルの一段目*/
		while(currentcard!=NULL) {
			nownum=currentcard->end-currentcard->start+1;
			/*printf("d1-%d %d %d\n",currentnum,currentcard->end,currentcard->start);*/
			if(currentnum+nownum>s1) {
				s1last=malloc(sizeof(cards));
				s1last->prev=currentcard->prev;
				s1last->start=currentcard->start;
				s1last->end=currentcard->start+(currentnum+nownum-s1-2);
				s2first=malloc(sizeof(cards));
				s2first->prev=s1last;
				s2first->start=currentcard->start+(currentnum+nownum-s1-1);
				s2first->end=currentcard->end;
				s2first->next=currentcard->next;
				s1last->next=s2first;
				if(s2first!=NULL)currentcard=s2first;
				currentnum+=nownum-s1;
				break;
			} else if(currentnum+nownum==s1) {
				/*printf("a1-%d %d\n",currentnum,nownum);*/
				s1last=currentcard;
				s2first=currentcard->next;
				currentnum+=nownum;
				if(s2first!=NULL)currentcard=s2first;
				break;
			}
			currentnum+=nownum;
			if(currentcard->next!=NULL)currentcard=currentcard->next;
			else break;
		}
		/*シャッフルの二段目*/
		while(currentcard!=NULL) {
			nownum=currentcard->end-currentcard->start+1;
			/*printf("d2-%d %d %d\n",currentnum,currentcard->end,currentcard->start);*/
			if(currentnum+nownum>s2) {
				s2last=malloc(sizeof(cards));
				s2last->prev=currentcard->prev;
				s2last->start=currentcard->start;
				s2last->end=currentcard->start+(currentnum+nownum-s2-2);
				s3first=malloc(sizeof(cards));
				s3first->prev=s1last;
				s3first->start=currentcard->start+(currentnum+nownum-s2-1);
				s3first->end=currentcard->end;
				s3first->next=currentcard->next;
				s2last->next=s3first;
				if(s3first!=NULL)currentcard=s3first;
				currentnum+=nownum-s2;
				break;
			} else if(currentnum+nownum==s2) {
				/*printf("a2-%d %d\n",currentnum,nownum);*/
				s2last=currentcard;
				s3first=currentcard->next;
				currentnum+=nownum;
				if(s3first!=NULL)currentcard=s3first;
				break;
			}
			currentnum+=nownum;
			if(currentcard->next!=NULL)currentcard=currentcard->next;
			else break;
		}
		/*最後を特定する*/
		while(currentcard!=NULL && currentcard->next!=NULL) {
			currentcard=currentcard->next;
		}
		/*シャッフル*/
		points[0]=first;
		points[1]=s1last;
		points[2]=s2first;
		points[3]=s2last;
		points[4]=s3first;
		points[5]=currentcard;
		/*for(count=0;count<6;count++)printf("%p\n",points[count]);*/
		first=points[4];
		s1last=points[5];
		/*s2first=points[2];
		s2last=points[3];*/
		s3first=points[0];
		currentcard=points[1];
		first->prev=NULL;
		s1last->next=s2first;
		s2first->prev=s1last;
		s2last->next=s3first;
		s3first->prev=s2last;
		currentcard->next=NULL;
	}
	/*条件に合うカードを数える*/
	count=0;
	flag=0;
	currentnum=0;
	currentcard=first;
	/*printf("a%p\n",currentcard);*/
	while(currentcard!=NULL) {
		/*printf("c:%d %d\n",currentcard->start,currentcard->end);*/
		/*for(i=currentcard->start;i<=currentcard->end;i++)printf("card:%d\n",i);*/
		nownum=currentcard->end-currentcard->start+1;
		if(flag==0) {/*最初～p*/
			if(currentnum+nownum>=p) {
				start=currentcard->start+p-currentnum-1;
				if(currentcard->end<=r)count+=currentcard->end-start+1;
				else if(start<=r)count+=r-start+1;
				flag=1;
			}
		} else if(flag==1) {/*p～q*/
			if(currentnum+nownum>q) {
				end=currentcard->end-(currentnum+nownum-q);
				if(end<=r)count+=end-currentcard->start+1;
				else if(currentcard->start<=r)
					count+=r-currentcard->start+1;
				flag=2;
			} else {
				if(currentcard->end<=r)
					count+=currentcard->end-currentcard->start+1;
				else if(currentcard->start<=r)
					count+=r-currentcard->start+1;
			}
		}
		currentnum+=nownum;
		currentcard=currentcard->next;
	}
	/*結果の出力*/
	printf("%d\n",count);
	/*メモリ解放*/
	while(first!=NULL) {
		currentcard=first->next;
		free(first);
		first=currentcard;
	}
	return 0;
}

デバッグ用のprintfをコメントアウトしています。

[たいちう]

直接の回答ではありません。

このような問題の場合、基本的には、
何度実行しても同じ結果になるはずです。
正解を出すにしても、誤答を出すにしても、実行時エラーになるにしても。

現状では実行時エラーになるようですが、
必ず同じタイミングでエラーになるはずです。
比較的易しいデバッグだと思います。
以下の方針で挑戦してみてはいかがでしょうか。

まずはprintf等を使って、いつどのように実行時エラーが起きるのか、
付きとめましょう。起きる場所が分かるのが第一歩です。
次は何故起きるのかを調べます。
その次は、どうしたら良いかを考えます。

[ゆーずぃ]

ちょっと動きを追ってみたら、シャッフルの際にXiがYiを超える時があるみたいです。それも何か悪さしてるかも？
全然質問とは関係ないですけど、面白そうだったので私もやってみました。
何か参考になる部分があればいいのですが・・・。

コード:

#include <stdio.h>
#include <stdlib.h>
 
/*****************************************************************************
  minからmaxの間の数値だけを入力として受け付ける(値制限10桁)
******************************************************************************/
int Input(int Min, int Max){
 
    char Input[10], InputFlag = 0;
    int ChangeInput, IsNewLine;
    /*  入力受付。ただしMinからMaxの間でなければ再入力 */
    do{
        scanf(" %10[0123456789]",Input);
        ChangeInput = atoi(Input);
 
        //バッファに残っているのが改行じゃなければ戻す
        if((IsNewLine = getchar()) != '\n')
            ungetc(IsNewLine, stdin);
 
        /* 入力チェック */
        if(Min <= ChangeInput && Max >= ChangeInput)
            InputFlag = 1;
    }while(InputFlag != 1);
 
    return ChangeInput;
}
 
/******************************************************************************
	シャッフル。
*******************************************************************************/
int Shuffle(int MountB, int MountC, int Cards[]){
    
    int *ShuffleTmp, i, j;
    int CardsSize = sizeof(Cards)/sizeof(int);
 
    /*　一時配列割り当て　*/
    if((ShuffleTmp = malloc(sizeof(Cards))) == NULL){
        puts("一時配列の割り当てに失敗しました。");
        return -1;
    }
    
    /* 元のカード配列の並び変え（一時配列内にて）*/
      // 一番下の山を一時配列の一番上にコピー
    for(i=0; i < (CardsSize-MountB) ; i++)
        ShuffleTmp[i] = Cards[MountC+i];
      // 真ん中の山を一時配列に続けてコピー
    for(j=0; j < (MountC-MountB) ; j++)
        ShuffleTmp[i] = Cards[MountB+j];
      // 一番上の山を一時配列に続けてコピー
    for(j=0; j < MountB ; j++)
        ShuffleTmp[i] = Cards[j];
 
    /* 並べ替えた配列を全コピー */
    for(i=0; i < CardsSize ; i++)
        Cards[i] = ShuffleTmp[i];
 
    free(ShuffleTmp);
    return 0;
}
/*************************************************************************
  StartPosとEndPosの間にObj以下の数値がいくつあるかを返す
**************************************************************************/
int SearchResultObject(int StartPos, int EndPos, int Obj, int Cards[]){
 
    int Result = 0;
    for(; StartPos <= EndPos ; StartPos++)
        if(Cards[StartPos-1] <= Obj)
            Result++;
    return Result;
}
/************************************************************************/
/**************************  main関数  **********************************/
/************************************************************************/
void main(void){
 
    int CardsNum, ShuffleNum, StartPos, EndPos, SearchObj, Result;
    int MountB, MountC;
    int i, j;
    int *Cards;
 
    CardsNum    = Input(3, 1000000000);         //カード総数を決定
    ShuffleNum  = Input(1, 5000);               //シャッフル総数を決定
    StartPos    = Input(1, CardsNum);           //検索開始ポジションの決定
    EndPos      = Input(StartPos,  CardsNum);   //検索終了ポジションの決定
    SearchObj   = Input(1, CardsNum);           //検索対象の数値を決定
 
    /*　カード作成　*/
    if((Cards = malloc((CardsNum * sizeof(int)))) == NULL){
        puts("カード配列の割り当てに失敗しました。");
        exit(EXIT_FAILURE); //割り当てに失敗すれば即終了
    }
    for(i=0, j=1; i < CardsNum ; i++)
        Cards[i] = j++;
 
    /* シャッフル総数分シャッフルを行う */
    for(i=0; i < ShuffleNum ; i++){
        MountB = Input(1, CardsNum);
        MountC = Input(MountB, CardsNum);
        if(Shuffle(MountB, MountC, Cards) == -1)
			exit(EXIT_FAILURE); //割り当てに失敗すれば即終了
    }
 
    /*  結果 */
    Result = SearchResultObject(StartPos, EndPos, SearchObj, Cards);
    printf("%d\n",Result);
    free(Cards);
    getchar();  //終了待ち
}

ユーザーの入力を信頼したものっすっごい適当な範囲チェック＆エラーチェックですけどｗ
完全に入力エラーチェックを省けば15行くらいは削れる…か？制作時間は1時間ちょいでした。
ちなみに私の場合、入力３からメモリ不足で割り当てられませんでしたｗ
こーゆーのも楽しいですね＾＾

[non]

みけCAT さんのプログラムはどのような考え方で解こうとしているのかを説明してもらわないと、さっぱりわかりません。
双方向リストでどうしたいのか説明を加えてください。そうでないと、自分で作る以上の、負担です。
たとえば　
9
1
3 7 4
3 5
と入力した場合。
最初にできたノードでは　start=1 end=9 みたいですね。
次に　作られたリスト（シャッフルの1段目)は
start=1 end=5 と　start=6　end=9ですが、ここの最初のノードの5はなんでしょうか？

ゆーずぃさんのプログラムなら、細かいところは全く見ていませんが、何をやろうとしているのかすぐに理解できます。

[ideyan]

眺めてみましたが、考え方はあってそうですね。
Nが大きいのでこのアルゴリズムで良いと思います。

・問題点その１
currentcard->start+(currentnum+nownum-s1-2);
↑ここの計算間違ってます。正確には↓
currentcard->start+(s1-currentnum-1);
デバッグ関数で表示される数字を眺めていれば分かります。
似たような場所が何カ所かあるのでそこも書き変えましょう。

・問題点その２
境目がある度にノードを２個増やしていますが、
もともとcurrentcardが指していたノードがどっかに行っちゃってます。
加えて、要素の繋ぎ換えが不完全なのでリストが物凄いことになっています。
(ついでに、増やすノードは１個で充分です。１個は元々のを書き換えて使います)

・問題点その３
currentcardが指していたノードがfirstやs1last、
その他の重要なノードだった場合の付け替えを行っていない。
(例えば、最初に1個のノード(1-10)があったとして、
最初の分割で新たに２個作ってデッキを分割しました(1-4,5-10)、
でもfirstは最初のノード(1-10)を指し続けています、みたいな問題が発生しています)

全体的に「双方向リストの任意の場所への要素の挿入」ができていないようですので、
処理を追いながら紙に書いてみておかしいところを探してみるといいと思います。

--------------------------------
問題のある場所を「修正」しようとしましたが
修正するのが難しい上にあまりよろしくない
実装だったので該当部位を丸ごと差し替えました。
一応参考までに、多分動作すると思うけれど、
全部は試してないので間違っているかもしれないソースを貼っておきます。。

コード:

#include <stdio.h>
#include <stdlib.h>
 
typedef struct _cards {
	struct _cards *prev;
	int start;
	int end;
	struct _cards *next;
} cards;

void print(cards *p){
	while(p!=NULL){
		printf("[%p]%d-%d[%d] ",p,p->start,p->end,p->end-p->start+1);
		p=p->next;
	}
	printf("\n");
}

int main(void) {
	/*情報変数*/
	int syafflenum;
	int howmanycards;
	int p,q,r;
	/*シャッフル用変数*/
	int i;
	cards* first;		/*カードの最初*/
	cards* points[6];	/*シャッフルするポイント*/
	int s1,s2;			/*シャッフルする位置*/
	int currentnum;		/*今何枚目のカードか*/
	int nownum;			/*今の束に何枚のカードがあるか*/
	cards* currentcard; /*現在操作中のカード*/

	cards *tmp;
	/*カードを数える*/
	int count;
	int flag;
	int start;
	int end;
	/*情報の読み込み*/
	scanf("%d",&howmanycards);
	scanf("%d",&syafflenum);
	scanf("%d %d %d",&p,&q,&r);
	/*カードの準備*/
	first=malloc(sizeof(cards));
	first->prev=NULL;
	first->start=1;
	first->end=howmanycards;
	first->next=NULL;
	
	/*シャッフル*/
	for(i=0;i<syafflenum;i++) {
		/*どこをシャッフルするか*/
		scanf("%d %d",&s1,&s2);
	//	printf("%d %d\n",s1,s2);
		/*シャッフル位置の特定*/
		currentnum=0;
		currentcard=first;
		/*シャッフルの一段目*/
		while(currentcard!=NULL) {
			nownum=currentcard->end-currentcard->start+1;
		  //  printf("d1-%d %d %d\n",currentnum,currentcard->end,currentcard->start);
			if(currentnum+nownum>s1) {
				
				tmp=malloc(sizeof(cards));
				tmp->prev=currentcard;
				tmp->next=currentcard->next;
				if(currentcard->next)currentcard->next->prev=tmp;
				currentcard->next=tmp;
				tmp->end=currentcard->end;
				currentcard->end=currentcard->start+(s1-currentnum-1);
				tmp->start=currentcard->end+1;
				currentcard=tmp;
				currentnum+=(s1-currentnum);
				break;
			} else if(currentnum+nownum==s1) {
				currentcard=currentcard->next;
				currentnum+=nownum;
				break;
			}
			currentnum+=nownum;
			if(currentcard->next!=NULL)currentcard=currentcard->next;
			else break;
		}
		/*シャッフルの二段目*/
		while(currentcard!=NULL) {
			nownum=currentcard->end-currentcard->start+1;
		//	  printf("d2-%d %d %d\n",currentnum,currentcard->end,currentcard->start);
			if(currentnum+nownum>s2) {
				
				tmp=malloc(sizeof(cards));
				tmp->prev=currentcard;
				tmp->next=currentcard->next;
				if(currentcard->next)currentcard->next->prev=tmp;
				currentcard->next=tmp;
				tmp->end=currentcard->end;
				currentcard->end=currentcard->start+(s2-currentnum-1);
				tmp->start=currentcard->end+1;
				currentcard=tmp;
				currentnum+=(s2-currentnum);
				break;
			} else if(currentnum+nownum==s2) {
		  //	  printf("a2-%d %d\n",currentnum,nownum);
				break;
			}
			currentnum+=nownum;
			if(currentcard->next!=NULL)currentcard=currentcard->next;
			else break;
		}
		
		/*位置決定*/
		{
			int sum=0;
			tmp=first;
			points[0]=tmp;
			while(tmp){
				sum+=tmp->end - tmp->start+1;
				if(sum==s1){
					points[1]=tmp;
					points[2]=tmp->next;
				}else if(sum==s2){
					points[3]=tmp;
					points[4]=tmp->next;
				}
				if(tmp->next==NULL)points[5]=tmp;
				tmp=tmp->next;
			}
		}
	//	print(first);
		first=points[4];
		first->prev=NULL;
		points[5]->next=points[2];
		points[2]->prev=points[5];
		points[3]->next=points[0];
		points[0]->prev=points[3];
		points[1]->next=NULL;
	//	print(first);
	//	printf("[%d]end.\n",i);
	}
	/*条件に合うカードを数える*/
	count=0;
	flag=0;
	currentnum=0;
	currentcard=first;
	/*printf("a%p\n",currentcard);*/
	while(currentcard!=NULL) {
		/*printf("c:%d %d\n",currentcard->start,currentcard->end);*/
		/*for(i=currentcard->start;i<=currentcard->end;i++)printf("card:%d\n",i);*/
		nownum=currentcard->end-currentcard->start+1;
		if(flag==0) {/*最初～p*/
			if(currentnum+nownum>=p) {
				start=currentcard->start+p-currentnum-1;
				if(currentcard->end<=r)count+=currentcard->end-start+1;
				else if(start<=r)count+=r-start+1;
				flag=1;
			}
		} else if(flag==1) {/*p～q*/
			if(currentnum+nownum>q) {
				end=currentcard->end-(currentnum+nownum-q);
				if(end<=r)count+=end-currentcard->start+1;
				else if(currentcard->start<=r)
					count+=r-currentcard->start+1;
				flag=2;
			} else {
				if(currentcard->end<=r)
					count+=currentcard->end-currentcard->start+1;
				else if(currentcard->start<=r)
					count+=r-currentcard->start+1;
			}
		}
		currentnum+=nownum;
		currentcard=currentcard->next;
	}
	/*結果の出力*/
	printf("%d\n",count);
	/*メモリ解放*/
	while(first!=NULL) {
		currentcard=first->next;
		free(first);
		first=currentcard;
	}
	return 0;
}