情報オリンピック

[あか]

情報オリンピックの２００８年度予選問題３の連鎖のプログラムわかる方いらっしゃいましたら教えていただけないでしょうか？
どうしてもわかりません。お願いします。

http://www.ioi-jp.org/joi/2008/2009-yo- ... yo-t3.html

[non]

そんな、大会があるのですね。初めて知りました。HPを見たら、解説もありましたし、
何がわからないのか書いていただかないと、あの解説以上のことを書くのは面倒です。

[あか]

書き込みありがとうございます。

その解説ではなくて、その問題のプログラム自体がわからないので、プログラムを教えていただきたいんですけど。

[non]

丸投げは禁止されております。
できるところまで、作成されてはいかがですか。

[あか]

作成してみたのですが、実行できなくて困っているところです。

[non]

そのプログラムを貼り付けてください。

[あか]

これなんですが↓

#include<stdio.h>
int main(void)
{
FILE*fp;
fp=fopen("input.txt","r");
{
int a,b[10000][2],bb[10000][2],c,d=0,e;
fscanf(fp,"%d",&a);
fscanf(fp,"%d",&e);
fclose (fp);
scanf("%d",&a);
scanf("%d",&e);
b[d][0]=bb[d][0]=e;
b[d][1]=bb[d][1]=1;
for(c=0;c<a-1;c++){
scanf("%d",&e);
}
if(b[d][0]==e){
b[d][1]++;
bb[d][1]++;
}
}
else{
(d++;b[d][0]=bb[d][0]=e);
{bb[d][1]}
}
printf("---------------------\n");
for(c=0;c<d+1;c++){
printf("%d :%d-%d\n");
}
printf("---------------------\n");
if(bb[c][1]==bb[c-1][1]+bb[c+1][1]>=4;){
printf("%d",c,bb[c][0],bb[c][1]);
return 0;
}
}


このプログラムを修正していただけないでしょうか？

[non]

大変申し訳ないけど、あなたの実力はまだこのプログラムを作るところまで
来ていません。この、課題は学校の課題で与えられて解かなければいけないもの
なのでしょうか？もし、あなたが自分の実力をつけるためにこの課題に挑戦して
いるのでしたら、もうすこし基本の勉強してからの方がいいです。

仮に学校の課題で解かなければいけないのなら、まず、ファイルを読んで
配列に格納する所だけでも、正しく動くように作ってみて下さい。

[あか]

実力がなくて申し訳ありません。

教えていただけないのはとても残念です。

ありがとうございました。

他の人の意見を聞くことにします。

[non]

不快な思いをさせたようで申し訳ありません。
答えだけを習っても、勉強になりませんよと申し上げたかったのです。
学校の課題なら、先生に教えを請うのが一番いいと思います。
それが、学校の先生の役目ですから。
がんばってください。

なお、先ほど解いてみました。
お恥ずかしいことに、入力１と入力２は正解を導けましたが、
入力４と入力５は正解になりませんでした。
原因がわからずに、ちょっと気分転換です。

[あか]

先生は教えてくれたのですが、先生と同じプログラムではだめだと言われました。

答えを見ながら勉強するのも、よい勉強法の１つだと考えております。

どうか教えていただけないでしょうか？？

[sizuma]

面白そうですね。
丁度さっきからCのファイル入出力の勉強を始めたんで、演習代わりにテキスト見ながら僕もやってみようと思いいます

[あか]

もしわかりましたら、そのプログラム教えてください。

[kazuoni]

自分もやってみました。

・・・nonさんと同じく、答えが合わない・・・。orz
入力1、2は正解でした。
入力4=4973
入力5=9943

と出ました・・・。

[sizuma]

ファイル入出力はテキスト読んでからやって、それとなく出来たんですけどアルゴリズム考えるの難しいですねー
連鎖は汎用性がありそうなんで、他で出てきても使えるように
ーって考えてたんですがうまくいかず。
C#だったらChainクラスを作ってまとめるんだけど、Cではどうしよう・・・って行き詰まりました;
まぁとりあえず文法勉強しろよ、ってことなんですけどね（苦笑

一応一時間かけて、再帰で連鎖チェックする感じで大まかな骨組みはつくったんですけど、デバックする元気はないんで明日気が向いたら続きします。



＞答えを見ながら勉強
よいソースをトレースするのはいい勉強になると思います。
でもそれはどんな風に構造化してるのか、などのテクニックを勉強するのにですね。
文法をお手本にするためなら、それはただ答えを見て写す作業と一緒です。
まぁ100回ぐらい繰り返せば使えるようになるかもしれませんね。


＞そのプログラム教えてください
先生は書いたプログラムを見せてくれたのですよね？それをみて勉強して、書いてみてはどうですか？
べつに出来たのをのせるのは構わないんですが。
正直僕（初心者）のソースを見ても勉強にならないと・・・


＞教えていただけないのはとても残念です
nonさんの書き込みはただ自分の書いたソースをのせるより、よっぽどあなたのためになる書き込みだと思います。せっかくアドバイス頂いたんですから、とりあえずnonさんの書かれてるようにまずファイルIOの部分をしっかり作ってみてはどうですか？
僕はインデントがないコードがスラスラ読めるほどのレベルではないんで（心も狭いし）
あかさんのコードは読んでないですが。
こんなアルゴリズム組めなくてもたいした問題ではないと思いますけど、ファイルIOは重要だと思います。
なんか僕、説教くさくてウザいですかね^^;

[non]

おはようございます。
布団の中で考えていたら、間違いに気がつきました。
無事に、すべて正解と一致しました。
kazuoniさんもきっと同じ間違いでしょう。
問題をよく読み直せば、最初の条件が２回目以降とちょっと違うのに気がつきます。
じゃ、がんばってください。

[sizuma]

僕も今走らせてみたんですが、kazuoniさんと同じ結果になりましたorz

問題読み直してきますー

[sizuma]

自分のミスを2点見つけたんですが、一つ目の修正を試してみたら1000ではちゃんと動くのが5000では途中で動かなくなりました。むしろ1000でちゃんと動くのが不思議なんですけどね。
5000もある配列の処理に再帰なんて使ってたからだろうか・・・


全部書き換えるのは面倒なんで、ここでやめておきます
見難い再帰はただのダメプログラムだ、といい勉強になりました
というわけであかさんすいません、できませんでした（苦笑

[素人]

熟練のプログラマーさん＞
やってみるだけやってみたんですけど、確認したいんで、そのプログラムはってくれませんか？？

[あか]

緊急事態なんです。
なんとか教えてもらえないでしょうか？？

[たいちう]

> 先生は書いたプログラムを見せてくれたのですよね？
> それをみて勉強して、書いてみてはどうですか？

と、sizumaさんも書いてますが、緊急事態なら勉強してはどうでしょうか。

[あか]

先生は見せてくれましたが一瞬しかみせてくれなかったのでどんな内容なのかメモできませんでした。

時間がないので、本当にお願いします。

教えてください。

[＼(^o^)／]

掲示板から掲示板を進めるのはどうかと思いますが、
私も含めてここにいる人たちでも分からないならば
2chの
C/C++の宿題片付けます 128代目
http://pc12.2ch.net/test/read.cgi/tech/1245853701/
プログラマーを本職にしてる人たちが大勢いるスレなので
ここで聞けばすぐに答えが返ってくると思います。
聞いてみてはいかがでしょうか？

[あか]

ありがとうございます。

聞いてみます。

[non]

あらまぁ、２チャンネルにいっちゃった。
どうして、少しは努力しようとしないのかなぁ？
ファイルの入力だけでもできたら教えるつもりだったのに。

じゃ、他の人の参考までに。

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

int data[10000+2];
int N;

int data_load(void)
{
     略
}
void disp(int n)
{
	int i;
	for(i=1;i<=n;i++)
		printf("%d\n",data);
}
int noc(int i,int c)
{
	int p,q,n;
	int size;
	n=N;
	p=i-1;
	q=i+1;

	size=1;
	while(data[p]==c){
		size++;
		p--;
	}
	while(data[q]==c){
		size++;
		q++;
	}

	while(size>=4){
		n=p+(N+1-q);
		size=0;
		c=data[p];
		while(p>=0 && data[p]==c){
			size++;
			p--;
		}
		while(q<=N && data[q]==c){
			size++;
			q++;
		}	
	}
	return n;
}
			
int main(void)
{
	int min,m;
	int i,j;
	N=data_load();
	min=N;
	for(i=2;i<N;i++){
		for(j=1;j<4;j++){
			m=noc(i,j);
			if(min>m)
				min=m;
		}
	}
	printf("min=%d\n",min);
	return 0;
}

[kazuoni]

nonさんのコード・・・簡潔すぎますｗ

自分のやつすごいです。非効率過ぎました。。
黒歴史で載せます・・・。小一時間頑張ったので・・・ｗ
うーん。これはオリンピック予選敗退ですね。
しかも高校生・・・。

はぁ。全然だめでした。肩ががっくり落ちました。。

[sizuma]

考えるの普通に面白いんですけどね
＞nonさんのプログラム
やっぱり再帰じゃないほうがシンプルで見やすいですねorz
僕はmain書きながらプログラム考えてたんですが、やっぱりだんだんごちゃごちゃしてきました


ちなみに僕はこんな感じでした

>添付ファイルにしました

とりあえず読みづらいなぁー
書いてるうちにグローバル変数が増えてきて・・・
関数に渡す引数も多くなってくるし
すごい助長な部分もあります。そのまえに5000じゃ正しく動作しないし(笑
連鎖の2回目から条件がちょっと違うのも変えてないです
初めてのCでのFile入出力でしたが、やっぱり実際してみるとちょっと分かった気分になりますね


＞貼ってみるとやはり長かったんで、添付にしました



＞kazuoniさん
僕の方が非効率な自信があります（笑
難しいですよねー
自分は文法本見ながらファイルIOしましたが、これだけで3時間かかりました；
正解率を見てみると、問3からが難しいみたいですね
1，2でちゃんととって、3～6でどれかできれば、予選突破レベル
ってすれば、予選は突破できる、、、、かも

[あか]

２チャンネルでも解答返ってきませんでした。

熟練のプログラマーｓ＞
言っておきますけど努力はしましたよ。
勝手に努力してないみたいな言い方はやめてほしいものですね。
それからあなたのプログラムは長すぎると思います。
もっと短いプログラムでできますよ。

でも、解決しましたので、皆さんにはお礼をいわなければなりません。
こんな自分のためにいろいろ書き込みありがとうございました。
感謝いたします。

プログラムはなんとか自分ですることができました。（他の方のを参考にして）

本当にありがとうございました。

[kazuoni]

>勝手に努力してないみたいな言い方はやめてほしいものですね。

その努力を見たかったので、nonさんは
>>仮に学校の課題で解かなければいけないのなら、まず、ファイルを読んで
>>配列に格納する所だけでも、正しく動くように作ってみて下さい。
と伝えたのです。これができれば、アルゴリズムの解説に移ることができますしね。

>それからあなたのプログラムは長すぎると思います。
>もっと短いプログラムでできますよ。
プログラムを極端に短くすることは、可読性が落ちる可能性もありますし、
処理効率が一概にいいとは言い切れないと思います。
まずは、自分ならこう組みますが？っと提示するのが前提かと。

（自分のプログラムは無駄が多すぎますが・・・）

[non]

>それからあなたのプログラムは長すぎると思います。
>もっと短いプログラムでできますよ。
あきれて、何もいうことがない。
じゃ、作ってアップしてくれ。

って、相手してもしょうがないので・・・
短くしました。ついでに、再帰プログラムにしました。

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

int data[10000+2];
int N;

int data_load(void)
{
	FILE *fp;
	int n,i=1;
	if((fp=fopen("data1.txt","r"))==NULL){
		printf("File Open ERROR!\n");
		exit(1);
	}
	fscanf(fp,"%d",&n);
	while(fscanf(fp,"%d",&data[i++])!=EOF){}
	fclose(fp);
	return n;
}
int renoc(int c,int p,int q,int sw)
{
	int n,size;
	n=p+(N+1-q);
	size=(sw==0)?1:0;
	while(p>=0 && data[p]==c){
		size++;
		p--;
	}
	while(q<=N && data[q]==c){
		size++;
		q++;
	}
	return (size>=4)?renoc(data[p],p,q,1):((sw==0)?N:n);
}
int main(void)
{
	int min,m;
	int i,j;
	N=data_load();
	min=N;
	for(i=2;i<N;i++){
		for(j=1;j<4;j++){
			m=renoc(j,i-1,i+1,0);
			if(min>m)
				min=m;
		}
	}
	printf("min=%d\n",min);
	return 0;
}

[七誌]

> ２チャンネルでも解答返ってきませんでした。
返ってきてますよ。

[a]

2chの返答はこうなったようですね

#include <stdio.h>

void check_file(char *filename);
int check_okikata(int *array, int size, int index, int color);

int main()
{
char *filenames[/url] = {
"2009-yo-t3-in1.txt",
"2009-yo-t3-in2.txt",
"2009-yo-t3-in3.txt",
"2009-yo-t3-in4.txt",
"2009-yo-t3-in5.txt",
};
int nfiles = sizeof(filenames) / sizeof(*filenames);
int i;

for (i = 0; i < nfiles; ++i) { check_file(filenames); }

return 0;
}

void check_file(char *filename)
{
FILE *fp;
int N, *array, i, color, min;

fp = fopen(filename, "r");
if (fp == NULL) {
printf("Error: can't open file %s\n", filename);
exit(1);
}

if (fscanf(fp, "%d", &N) != 1) {
printf("Error: illegal data format %s\n", filename);
exit(1);
}

array = (int *)malloc(N * sizeof(int));
if (array == NULL) {
printf("Error: no memory\n");
exit(1);
}

for (i = 0; i < N; ++i) {
if (fscanf(fp, "%d", &array) != 1 || array < 1 || array > 3) {
printf("Error: illegal data format %s\n", filename);
exit(1);
}
}

min = N;
for (i = 0; i < N; ++i) {
for (color = 1; color <= 3; ++color) {
int nokori = check_okikata(array, N, i, color);
if (nokori < min) min = nokori;
}
}
printf("%s : %d --> %d\n", filename, N, min);

free(array);
fclose(fp);
}

int check_okikata(int *array, int size, int index, int color)
{
#define RENZOKU 4

int i, imin, imax, length, sum;

imin = index - 1;
imax = index + 1;
sum = 0;
length = 1;
for (;;) {
while (imin >= 0 && array[imin] == color) { --imin; ++length; }
while (imax < size && array[imax] == color) { ++imax; ++length; }
if (length < RENZOKU) break;
sum += length;
if (imin < 0 || imax >= size) break;
length = 0;
color = array[imax];
}

return size - sum;
}

[b]

せっかく答えて下さっているnonさんに対して、
スレ主は失礼過ぎると思います。

#include<stdio.h> 
int main(void) 
{ 
	FILE*fp; 
	fp=fopen("input.txt","r");
	
	/*↓「｛ 」の位置がおかしい	*/
	{ 
		/*変数の宣言位置がおかしい*/
		/*変数名がa,bだと何を表わすのか、ぱっと見わからない*/
		/*他の人に、修正を求めるのであればわかりやすい変数名、もしくはコメントをつけるべき*/
		/*２次元配列にした理由はなぜか？*/
		int a,b[10000][2],bb[10000][2],c,d=0,e;
		
		fscanf(fp,"%d",&a);
		fscanf(fp,"%d",&e);
		fclose (fp);
		
		/*ここでfscanfで読み込んだ値を上書きしている？　間違い*/
		scanf("%d",&a); 
		scanf("%d",&e); 
		
		b[d][0]=bb[d][0]=e; 
		b[d][1]=bb[d][1]=1; 
		
		/*同じ変数eに何回も入力をしている*/
		for(c=0;c<a-1;c++){ 
			scanf("%d",&e); 
		} 
		if(b[d][0]==e){ 
			b[d][1]++; 
			bb[d][1]++; 
		}
	/*変数のスコープは↓ここまで。つまり、ここ以下では変数は機能しない*/
	/*そもそも、基礎的な書き方が間違っているので何とも言えない*/
	} 
	else{
		/*↓何をしたいのか、わからない	根本的な文法的間違い*/ 
		(d++;b[d][0]=bb[d][0]=e); 
		{
			/*↓何をしたいのか、わからない	文法的な間違い*/ 
			bb[d][1]
			} 
		} 
		printf("---------------------\n"); 
	for(c=0;c<d+1;c++){ 
		printf("%d :%d-%d\n"); 
	} 
	printf("---------------------\n");
	
	/*文法的な間違い*/ 
	if(bb[c][1]==bb[c-1][1]+bb[c+1][1]>=4;){
 		/*printfの書き方が違う*/
		printf("%d",c,bb[c][0],bb[c][1]); 
		
		/*return の位置が違う*/
		return 0; 
	}
}

スレ主は、これを修正してください、ということでしたが、
これを直すなら、全部書き変えなくてはいけません。
基礎的な構文も間違っているので、これで努力していると言っても説得力が全くないですね。