どうもどうも。
地道に、問題をちょいちょい解いたのよ。
そしたらよ、結構詰まったことがあったのよ。
そのことについて書くのよ。
今回の、かなり長いです。いっぱいコードを貼っつけたので。
今回その引っかかりを産んでくれたのは京都大学プログラミングコンテストの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"に当たるものが必要なのか?
今のところは分かりません。
とりあえず一旦、ここまで。
頑張って調べよー