プログラミングを上達させたい

プログラミングの勉強を始めた、情報学専攻の大学院生です。モチベーション維持のため、ブログに勉強したことを書いていきます。→就職。IT全然関係ない仕事をしています

Pascalにて色々つまずいた話

どうもどうも。
地道に、問題をちょいちょい解いたのよ。
そしたらよ、結構詰まったことがあったのよ。
そのことについて書くのよ。
今回の、かなり長いです。いっぱいコードを貼っつけたので。


今回その引っかかりを産んでくれたのは京都大学プログラミングコンテストのB問題です。


AtCoderでは珍しい、対話して答えを出す奴です。
Pascalでも普通に書いたらできるんかな、と気になり(Rubyとかだと、flush?とかなんとかで、ちょっと面倒そうだったので)、解いてみました。
以前にSchemeで解いたときと同じアルゴリズムで書いてみました。コードは以下のような感じ。

program solve(input, output);
 
var
	i, answer : 1..1000;
	response : Char;
	numTable : array[1..1000] of Boolean;
 
procedure yesUpdate(var seed : Integer);
var j : 1..1000;
begin
	for j := seed to 1000 do
	if j mod seed > 0
	then numTable[j] := false 
end;
 
procedure notUpdate(var seed : Integer);
var kakerukazu : Integer;
begin
	kakerukazu := 1;
	while (kakerukazu * seed <= 1000) do
	begin
		numTable[kakerukazu * seed] := false;
		kakerukazu := kakerukazu + 1;
	end
end;
 
begin
 
	for i := 1 to 1000 do
	numTable[i] := true;
 
	answer := 1;
	i := 2;
 
	while (i <= 1000) do
	begin
		if not numTable[i] 
		then begin
			i := i + 1;
			continue
		end;
		writeln('? ',i);
		readln(response);
		if response = 'Y'
		then begin
			answer := i;
			i := i * 2;
			yesUpdate(i)
		end
		else begin
			i := i + 1;
			notUpdate(i)
		end
	end;
 
	writeln('! ',answer);
 
end.

おなじみのideoneでの動作確認も完了し、AtCoderで提出。
わくわくしながら結果を見てみるとなんと、CE。
CEて。WAやTLEなら分かるけども。なんやねん。

ideoneのPascalは、Free Pascal 2.6.2。それに対してAtCoderで使われているのは、Free Pascal 2.4.4。
そこのバージョンの違いなんやろか、と思い、手元で確かめようとするも、FreePascal 2.4.4が簡単には入れられず、断念。んもー

色々模索してみた(つまり、一部をコメントアウトしてはAtCoderに提出、という、迷惑をかけるやつをやってみた)結果、手続きの仮引数のところの"var"が悪い・・・?ような・・・?
というわけで、notUpdateとyesUpdateの仮引数seedの前の"var"を消してみると、CEじゃない!ジャッジしてくれてる!!

しかし、次はTLE・・・
普通ならここで、ありゃ、コード間違えとるかな、となるかも知れませんが、ideoneだとちゃんと動くんですよ。
絶対合ってるハズだ。全部のテストケースでTLEになってたんですが、少なくともそれはないやろ。

てなわけでまたコードとにらめっこ。
全てのテストケースでTLEってことは、whileがダメなのかな、と、メインのところを(無理に意味のない変数を使って)forで書き直してみました。
コードはこんな感じ("ii"が意味のない変数)。

program solve(input, output);
 
var
	i : 1..2000;
	answer, ii : 1..1000;
	response : Char;
	numTable : array[1..1000] of Boolean;
 
procedure yesUpdate(seed : Integer);
var j : 1..1000;
begin
	for j := seed to 1000 do
	if j mod seed > 0
	then numTable[j] := false 
end;
 
procedure notUpdate(seed : Integer);
var kakerukazu : Integer;
begin
	kakerukazu := 1;
	while (kakerukazu * seed <= 1000) do
	begin
		numTable[kakerukazu * seed] := false;
		kakerukazu := kakerukazu + 1;
	end
end;
 
begin
 
	for i := 1 to 1000 do
	numTable[i] := true;
 
	answer := 1;
	i := 2;
 
	for ii := 1 to 200 do
	begin 
	if i > 1000
	then break
	else
		if numTable[i]
		then begin
			writeln('? ',i);
			readln(response);
			if response = 'Y'
			then begin
				answer := i;
				yesUpdate(i);
				i := i * 2
			end
			else begin
				notUpdate(i);
				i := i + 1
			end
		end
		else i := i + 1
	end;

	writeln('! ',answer)
 
end.

ideoneでは動作OK。で、AtCoderではどやねん!と提出するも、またTLE・・・
WAになるはずなんやけどなー

さて次に、whileを使っている手続き2つも消してみて(つまり、下のように手続きのメイン部分をコメントアウトして)、提出!

procedure yesUpdate(seed : Integer);
var j : 1..1000;
begin
	(*
	for j := seed to 1000 do
	if j mod seed > 0
	then numTable[j] := false 
	*)
end;
 
procedure notUpdate(seed : Integer);
var kakerukazu : Integer;
begin
	(*
	kakerukazu := 1;
	while (kakerukazu * seed <= 1000) do
	begin
		numTable[kakerukazu * seed] := false;
		kakerukazu := kakerukazu + 1;
	end
	*)
end;

しかしこれでも・・・
TLE・・・
ほんまにもう・・・

次は、メインの部分の手続き呼び出し部分、"yesUpdate(i)"と"notUpdate(i)"を消して提出。
またTLE。
ってことは、手続き絡みの部分じゃないんだな。

初心に戻って、以下のコードを提出。

program solve(input, output);
 
var
	i : 1..2000;
	answer, ii : 1..1000;
	response : Char;
	numTable : array[1..1000] of Boolean;
 
begin
 
	for i := 1 to 1000 do
	numTable[i] := true;
 
	answer := 1;
	i := 2;

	writeln('! ',answer)
 
end.

おっ、これはWA。
ということで、ここから先ほどのコードでやったことをちょいちょい付け足していきましょう。
writeln('! ',answer) の上に付け加えていきます。

次試そうと思ったコードはコチラ。

program solve(input, output);
 
var
	i : 1..2000;
	answer, ii : 1..1000;
	response : Char;
	numTable : array[1..1000] of Boolean;
 
begin
 
	for i := 1 to 1000 do
	numTable[i] := true;
 
	answer := 1;
	i := 2;

	writeln('? 2');
	readln(response);
	writeln('? 2');
	readln(response);
	writeln('? 2');
	readln(response);

	writeln('! ',answer)
 
end.

writelnとreadlnを何回かするやつです。
ideoneで動作確認をしてみました。
inputに

Y
Y
Y

を入れて動かしてみると、outputは

Success	time: 0 memory: 232 signal:0
? 2
? 2
? 2
! 1

となりました。よしよし。
そしてこれをAtCoderに出してみると・・・
TLE!!!!!!!
おっ!!!!
ということは、readlnとwritelnを交互に何回もすることが出来ないのか・・・!
へぇ。そうかよ。

さて、しかし理由は分かりません。バージョンの違いなのかな?
なんか、問題文に注意として書いてある、C++で言うところの"fflush"に当たるものが必要なのか?

今のところは分かりません。
とりあえず一旦、ここまで。
頑張って調べよー

広告を非表示にする