Windowsの下でバッチ処理プログラムで対拍する

アルゴリズム系コンテストのテーマを作るとき、素朴で完全に正しいアルゴリズムを保証できるが、タイムアウトすると考えやすい.効率的なアルゴリズムは、完全に正しいことを保証することはできません.この場合、効率的なアルゴリズムの正確性を検証するために、素朴なアルゴリズム、データ生成プログラム、ファイル比較プログラムを自分で書くことができます.
Windowsでは、fcコマンドがファイルを比較する機能を提供しており、バッチ処理はLinuxのbashなどに及ばないが、自動的に比較するプログラムを書くのに十分である.
以下、逆シーケンス対を例に挙げる.タイトルはPOJ 3067に似ていて、並べ替えた後に逆の順序を求めます.データ量N=300000.泡立ちソートに似た列挙逆順対を思い浮かべやすく,先に書く.standardという名前です.pas

const
    MAXN = 500000;
type 
    car = record x,v:longint end;
    
var
    a: array[0..MAXN] of car;
    n : longint;
    i, j : longint;
    sum : longint;

procedure swap(var a, b:car);
var
    temp:car;
begin
    temp := a;
    a := b;
    b := temp;
end;

begin
    readln(n);
    for i:=1 to n do
        readln(a[i].x , a[i].v);
    for i:=1 to n-1 do
        for j:=i+1 to n do
            if a[i].x > a[j].x then
                swap(a[i], a[j]);
    for i:=1 to n-1 do
        for j:=i+1 to n do
            if a[i].v > a[j].v  then
                inc(sum);
    writeln(sum);
end.

Nlognのプログラムを統合ソートなどの高度なアルゴリズムで実現してこそ、この問題を解決することができる.タイトル要求と命名されたovertaking.pas.プログラムは集計ソートでソートし、この集計ソートをコピーして逆順ペアを求める統計過程に変更します.

const
    MAXN = 500000;
type 
    car = record x,v:longint end;
    
var
    temp, a: array[0..MAXN] of car;
    n : longint;
    i : longint;
    sum : int64;

procedure swap(var a, b:car);
var
    temp:car;
begin
    temp := a;
    a := b;
    b := temp;
end;

procedure qsort(l, r:longint);
var
    i, j, m:longint;
begin
    i:=l;j:=r;m:=a[(l+r)div 2].x;
    repeat
        while (a[i].x < m) do inc(i);
        while (a[j].x > m) do dec(j);
        if i <= j then
        begin
            swap(a[i],a[j]);
            inc(i);
            dec(j);
        end;
    until i > j;
    if l < j then
        qsort(l, j);
    if i < r then
        qsort(i, r);
end;

procedure merge(left, mid, right :longint);
var
    i, j, p, k:longint;
begin
    k := left;
    i := left;
    j := mid + 1;
    while (i <= mid) and (j <= right) do
    begin
        if a[i].x <= a[j].x then
        begin
            temp[k] := a[i];
            inc(i);
            inc(k);
        end
        else begin
            temp[k] := a[j];
            inc(j);
            inc(k);
        end;
    end;
    for p := i to mid do
    begin
        temp[k] := a[p];
        inc(k);
    end;
    for p := j to right do
    begin
        temp[k] := a[p];
        inc(k);
    end;
    for i:= left to right do
        a[i] := temp[i];
end;
        
procedure merge_sort(left, right:longint);
var
    mid : longint;
begin
    if left >= right then    
        exit;
    mid := (left + right) shr 1;
    merge_sort(left, mid);
    merge_sort(mid+1, right);
    merge(left, mid ,right);
end;
        
        
        
procedure merge2(left, mid, right :longint);
var
    i, j, p, k:longint;
begin
    k := left;
    i := left;
    j := mid + 1;
    while (i <= mid) and (j <= right) do
    begin
        if a[i].v <= a[j].v then
        begin
            temp[k] := a[i];
            inc(i);
            inc(k);
        end
        else begin
            inc(sum, mid - i + 1);
            temp[k] := a[j];
            inc(j);
            inc(k);
        end;
    end;
    for p := i to mid do
    begin
        temp[k] := a[p];
        inc(k);
    end;
    for p := j to right do
    begin
        temp[k] := a[p];
        inc(k);
    end;
    for i:= left to right do
        a[i] := temp[i];
end;
        
procedure merge_sort2(left, right:longint);
var
    mid : longint;
begin
    if left >= right then    
        exit;
    mid := (left + right) shr 1;
    merge_sort2(left, mid);
    merge_sort2(mid+1, right);
    merge2(left, mid ,right);
end;


procedure select_sort;
var 
    i, j:longint;
begin
    for i:=1 to n-1 do
        for j:=i+1 to n do
            if a[i].x > a[j].x then
                swap(a[i], a[j]);
end;

begin
    
    readln(n);
    for i:=1 to n do
    begin
        readln(a[i].x, a[i].v);
    end;
    merge_sort(1, n);
    merge_sort2(1, n);
    writeln(sum);
    
  
end.

次にデータジェネレータを書きます.この問題はデータを作るのが簡単で、乱数を生成すればいいです.

const
    INF = 199303170;
    MAXN = 3000;
    
var
    i, n:longint;
begin
    randomize;
    n := random(MAXN);
    writeln(n);
    for i:=1 to n do
        writeln(random(INF),'',random(INF));
end.
    

その後、バッチの対拍を書き、3つのプログラムの入出力を画面、キーボードからファイルに自動的にリダイレクトし、standardを比較する.exeとovertakingで生成されたデータ.

:loop
make.exe > data.txt
standard.exe < data.txt > std.txt
overtaking.exe < data.txt > ans.txt
fc std.txt ans.txt
if errorlevel 1 goto end
goto loop
:end

コマンドラインインタフェースでは、ファイルの違いが見つからないことを絶えず提示し、安心して提出することができます.もちろん、素朴なアルゴリズムが正しいことが前提です.