Pascalと配列 ABC006D問題

さてさて、さらに前回の続きです。
AtCoder Beginner Contest 006の最後の、D問題をPascalで解きました。
やっぱり、配列をやったりと、ちょっと面倒でした。
慣れたら楽になるんですかね。

さて、練習のため、まずは部分点の解答を書いてみました。
アルゴリズムは高橋直大さんの解説スライドを参考にしています。
はい、コチラが部分点解答です。

program solve(input, output);
 
const
	MaxNum = 30000;
 
type
	Table = array[1..MaxNum] of Integer;
 
var
	n : Integer;
	inputTable, dpTable : Table;
 
procedure readArray(var limit : Integer);
	var j : 1..MaxNum;
begin
	for j := 1 to limit do
		readln(inputTable[j])
end;
 
procedure searchAnswer(dpTable : Table; var limit : Integer);
	var
	 j, answer, nowMax : 1..MaxNum;
begin
	nowMax := 0;
 
	for j := 1 to limit do begin
		if dpTable[j] > nowMax
		then begin
			nowMax := dpTable[j];
		end	
	end;
 
(*	writeln(nowMax);
	writeln(limit); *)
	writeln(limit - nowMax)
end;
(*
procedure writeTable(var aTable : Table; var limit : Integer);
	var j : 1..MaxNum;
begin
	for j := 1 to limit do
	writeln(aTable[j]);
	
end;
*)
procedure dp(var limit : Integer);
	var
	j, indNum, nowMax, m : 1..MaxNum;
begin
	dpTable[1] := 1;
 
	for j := 2 to limit do begin
		m := inputTable[j];
		nowMax := 1;
		for indNum := 1 to j - 1 do begin
			if ((dpTable[indNum] >= nowMax) and (m > inputTable[indNum]))
			then nowMax := dpTable[indNum] + 1
		end;
		dpTable[j] := nowMax
	end
end;
 
 
begin
	readln(n);
	readArray(n);
(*	writeln('inputTable is');
	writeTable(inputTable,n); *)
	dp(n);
(*	writeln('dpTable is');
	writeTable(dpTable,n); *)
	searchAnswer(dpTable,n);
	
end.

ちなみに、 (* *)を使ってコメントアウトしている部分は、デバッグのために使いました。

結構つまづいた部分は、手続きの引数あたりの問題です。
例えば、

procedure readArray(var limit : Integer);
	var j : 1..MaxNum;
begin
	for j := 1 to limit do
		readln(inputTable[j])
end;

のところ。
これは、inputTableという名前の配列に数字を読み込んでいく手続きです。
引数のlimitというのは、何個目まで読み込むかを表す整数です。
それでですね、この手続き内で使う変数、jについて、jは1からlimitまでしか増えないのですから、そこまでしか動かないようにしたいところです。
しかし、上の宣言部を

13.  procedure readArray(var limit : Integer);
14.   	var j : 1..limit;
15.  begin
16.  	for j := 1 to limit do
17.  		readln(inputTable[j])
18.  end;

とすると(説明のため、行番号を書いています)、次のようなエラーが出ます(ideoneにて)。

prog.pas(14,18) Error: Error in type definition
prog.pas(16,6) Error: Ordinal expression expected

宣言部には引数を使っちゃいけない、って感じなんですかね。
今参考にしている『基礎PASCAL』(萩原兼一さん)でも丁寧に書かれているんですが、なかなか感覚として理解できません。むずかしいぜ。

また、慣例としてどこまでを引数にして書くべきかとか、そういうのはまだまだ分からないですね。もちろん、競技プログラミングくらいでしか使わないので、どうでもいいっちゃあどうでもいいのですが。
これから何冊かPascalの本を読む(予定)なので、その中で自分なりのルールをちゃんと固められたら、と思っています。

さてさて、
満点の解答は次のような感じになりました。

program solve(input, output);
 
const
	MaxNum = 30000;
 
type
	Table = array[1..(MaxNum+2)] of Integer;
 
var
	n : Integer;
	inputTable, dpTable : Table;
 
procedure readArray(var limit : Integer);
	var j : 1..MaxNum;
begin
	for j := 1 to limit do
		readln(inputTable[j])
end;
 
procedure searchAnswer(var limit : Integer);
	var
	 j, answer : 1..MaxNum+1;
begin
	answer := 0;
 
	for j := 2 to limit+2 do begin
		if dpTable[j] > 30303
		then begin
			answer := j-2;
			break
		end	
	end;
 
(*	writeln(answer);
	writeln(limit); *)
	writeln(limit - answer)
end;
 
(*
procedure writeTable(var aTable : Table; var limit : Integer);
	var j : 1..MaxNum+2;
begin
	for j := 1 to limit+2 do
	writeln(aTable[j]);
	
end;
*)
 
procedure dpWithBinarySearch(var limit : Integer);
	var
	j, indNum, m, right, left, half : 1..(MaxNum+2);
begin
	dpTable[1] := 0;
(* 便宜上、3*10^4以上の数を入れておく *)
	for j := 2 to limit + 2 do
	 dpTable[j] := 31111;
 
	for j := 2 to limit + 1 do begin
		m := inputTable[j-1];
		left := 1;
		right := j + 2;
		half := (left + right) div 2;
 
		while (right - left > 1) do
		begin
			half := (left + right) div 2;
			if dpTable[half] > m
			then right := half
			else left := half
		end;
 
		if dpTable[right] > m
		then dpTable[right] := m
	end
end;
 
 
begin
	readln(n);
	readArray(n);
(*	writeln('inputTable is');
	writeTable(inputTable,n); *)
	dpWithBinarySearch(n);
(*	writeln('dpTable is');
	writeTable(dpTable,n); *)
	searchAnswer(n);
	
end.

途中に二分探索が出ますね。
ただ、先ほどの部分点コードの手続きの１つを書き直すだけだったので、割と楽にできました。

注意ですが、Sublime Text 2のPascalモード(以前導入したやつです)では、"break"の色が変わりません。
あれ、breakないのかな、って思っちゃいます。あります。よかった。

やはり、こうやってパーツ毎に分けて書けるのはいいですね。
個人的には、Javaよりは書きやすいです。

ちなみに、この満点回答をAtCoderに提出したところ、実行時間が28ms、また、ほぼ同じコードで使用メモリが924KBでした。
大量のC++解答の中で、実行時間は3位タイ(26msと27msの解答が1つずつありました(どちらもC++))、使用メモリはなんと最小！！
すごい、すごいよPascal・・・！
そのあと、実行時間も1位を狙おうと何個も同じコードを出してみたりしたんですが、28msを下回ることはありませんでした。
悔しい・・・

まぁ、今まで使っていたJavaとSchemeより圧倒的に速いのでよしとしましょう。よしよし。

これ以降は、木やスタックなどのデータ構造を使う問題を解いたら、基礎は一通り、という感じでしょうか。
あと、これまでグラフネットワークっぽい問題に弱かったので、その辺も解きたいところです。
データ構造については、Pascalで自分でデータ構造を書くことになると思います。
参考になりそうな本もすでに見繕ってあります。

次に受けるコンテストは、Code FormulaとCode Festivalの予選だと思うので、なんとか予選通過したいものです・・・！
もちろん、PascalとSchemeで。

また、@frfrfrfrproというIDでtwitterもやっています。
何か感想や間違いの指摘などあれば、コチラに連絡を頂けると嬉しいです。
というわけで、今回は以上です。