SuperCon2006予選課題

課題

正方格子の上の頂点に対し, すべて,1回だけ通る格子上の矩形閉路で, なるべく短いものを求めるプログラムを作りなさい.
  「正方格子」とは碁盤の目のようなもの.たとえば,以下(左図)は 8 x 8
  の正方格子の例.「矩形閉路」とは,格子の単位正方形の各辺からなる路
  で,同じ辺,点を二度は通らずに,元の頂点に戻ってくるもの.たとえば右図は
  左図の,* の点をすべて通る矩形閉路である(最短かどうかは不明).

   .  .  .  .  *  .  .  .     .  .  .  .--*  .  .  .
                                        |  |           
   .  .  *  .  .  .  .  .     .  .--*--.  .  .  .  .
                                  |        |           
   .  *  .  .  .  .  .  .     .  *  .  .  .  .  .  .
                                  |        |           
   .  *  .  .  *  .  *  .     .  *  .  .  *--.--*  .
                                  |              |     
   .  .  .  *  *  .  *  .     .  .  .--*  *--.  *  .
                                  |  |  |  |  |  |     
   .  .  *  *  *  .  *  .     .  .  *  *--*  .--*  .
                                  |  |                 
   .  *  .  .  .  .  .  .     .  *--.  .  .  .  .  .
                           
   .  .  .  .  .  .  .  .     .  .  .  .  .  .  .  .

問題の設定

正方格子の一辺を n とする. n は 100 以下の偶数とする. 正方格子上の座標は, 横が x,縦を y とし, 上から(左から)0, 1, 2, ..., n-1 と座標を与える. たとえば, 左上の座標が (0,0), 右上の座標が (n-1,0) , 左下の座標が (0,n-1) , 右下の座標が (n-1,n-1) である. 上図(左)では,(1,2), (1,3) などが指定された頂点である.
    例: 1 2
       1 3
       1 4
       1 5
       1 6
       2 6
       ...
       1 1
       1 2
       -1 -1

注:入力の,すべての点が1回ずつ現れるはず. また, 矩形巡回路なので, 同じ頂点は,(i) 出発点を除いて二度以上現れない, (ii) 連続する2つの座標は, x が同じで y が 1 だけ異なるか, あるいは,y が同じで x が 1 だけ異なるか, のいずれかである.

審査基準

5種類のデータを用意. それぞれのデータに対し, 制限時間(30秒)内で解答プログラムを 実行させ, 正しい閉路に対しその長さを合計し,より長さが短いものを上位とする. ただし,合計閉路長が同じ場合は実行時間の短いものを上位とする.

仮に,制限時間を越えた場合でも, 180 秒以内に終了し, かつ,正しい閉路を出力した 場合は, 閉路長に実行時間(秒)/30 の割合を掛けた値(または n x n の小さな方)を, その閉路の評価値として用いる.

誤った出力に対しては, n x n(最大閉路長)を評価値として用いる.

使用言語

ANSI C(参考『プログラミング言語C』カーニハン/リッチー)で 許される関数,ライブラリのみを使用すること.それ以外のライブラリ等を 使用した場合の不具合については,関知しない.

審査実行環境

AMD 2.4GHz,64bitプロセッサを,32ビットモードで使用.最適化オプションは一切使用しない.