アルゴリズムデザインコンテスト2019(ADC2019)ルール説明

更新情報

概要

※ 「ナンバーリンク」は株式会社ニコリの登録商標です。

問題例

問題例

解答例

解答例
この場合の解の品質は「横9マス×縦8マス=72」となる

詳細

問題フォーマット

  1. 盤面サイズは SIZE [X]X[Y] の形で定義される
    • (X,Y): 盤面平面のマスの数を表す(X:横方向、Y:縦方向)
  2. 盤面平面のサイズは最大で72x72(つまり、X,Yはそれぞれ 1≦X≦72, 1≦Y≦72 を満たす)
  3. 使用ブロックの数は BLOCK_NUM [N] で定義される。Nはブロックの数であり、連続する自然数 (1,2,…) で表される
  4. 各ブロックは、ブロックの通し番号を示す数字と、ブロック形状および配線の端点を示す数字・記号列により定義される
    1. ブロックの形状は1マスのモノミノ、および5種類のテトロミノのうちいずれかである
    2. ブロックのサイズは BLOCK#[i] [W]X[H] で定義される。iはブロック番号、WとHはそれぞれブロックの幅と高さである
    3. ブロック内の数字の配置はカンマ区切りで記述される。配線の端点となるマスには数字が入る。数字が入らないブロック内のマスは + で示される。ブロック外の領域は 0 で示される。すべてが+のブロックもあり得る
    4. 配線の端点は必ずペアを成す。つまり、全てのブロック中で使用される数字は必ず2回ずつ現れる
  5. ブロック数に上限はない(コンテストとしては、nlcheck.pyを通ることは事前確認されたい)

回答フォーマット

  1. 全てのブロックを囲む矩形サイズ、盤面上の数字の2次元フォーマット、および各ブロックの配置座標を記述したものがADC2019の回答フォーマットとなる
  2. 全てのブロックを囲む矩形サイズは SIZE [W]X[H] の形式で記述する
  3. 盤面上の数字の2次元回答フォーマットは、各マスに数字を当てはめたものとする(2018年度までと同様)
  4. ブロックの配置座標は BLOCK#[i] @([X],[Y]) の形式で記述する。iはブロック番号、(X,Y)はブロックの左上端マス(ブロック外 0 の場合も含む)の座標である。座標系は盤面の左上端を原点(0,0)とする
回答フォーマットの曖昧さについて補足

詳細情報 Issues #17

もともとブロック内で+となっている部分が、公開されている回答例では、0と表記されていました。

0は、空き地の意味で使われていますが、ブロックのマスは線が通れないので、空き地ではありません。回答フォーマットでは、+と表記するべきでした。

今からルール変更すると迷惑をかけてしまうため、今回(2019年)は、回答フォーマットでの0+は同一視する、ということにします。

回答フォーマットにおいて、ブロックのマスの部分は、0としても、+としても、どちらでもよい、とします。

問題フォーマット、回答フォーマットの例

上の問題例・解答例に対応する問題・回答フォーマット例を以下に示す

テキストダウンロード

問題フォーマット例
SIZE 10X10
BLOCK_NUM 8

BLOCK#1 1X4
1
+
8
7

BLOCK#2 3X2
0,8,0
7,6,+

BLOCK#3 2X3
10,0
 +,0
 3,9

BLOCK#4 2X2
1,2
4,+

BLOCK#5 3X2
11,+,+
 0,0,3

BLOCK#6 3X2
0, +,2
5,11,0

BLOCK#7 3X2
0,10,6
9, 5,0

BLOCK#8 3X2
+,+,0
0,+,4
回答フォーマット例
SIZE 9X8
 0, 1, 1, 1, 1, 2, 2, 2, 2
 0, 0, 0, 0, 4, 0, 0, 0, 2
 0, 8, 8, 8, 4, 4, 4, 4, 2
 0, 7, 7, 6, 0, 0, 0, 4, 2
10,10,10, 6, 0, 2, 0, 4, 2
 0, 9, 5, 5,11, 2, 2, 2, 2
 3, 9, 0, 0,11, 0, 0, 0, 0
 3, 3, 3, 3, 3, 3, 3, 0, 0
BLOCK#1 @(1,0)
BLOCK#2 @(2,2)
BLOCK#3 @(0,4)
BLOCK#4 @(4,0)
BLOCK#5 @(4,6)
BLOCK#6 @(3,4)
BLOCK#7 @(1,4)
BLOCK#8 @(5,3)

回答ルール

  1. 問題で指定された全てのブロックを盤面上に配置する
    1. ブロックは回転、反転させてはならない。上下左右の平行移動のみ行う
    2. ブロック同士は重なって配置してはならない
  2. ブロック上の端点の間を交差・分岐の無い配線で接続する
    1. 配線の端点が存在するマスは、X, Y方向に隣接する最大4個のマスのうち1個と接続される(ナンバーリンクと同じ)
    2. 配線を構成する端点以外のマスは、X, Y方向に隣接する最大4個のマスのうち2個と接続される(ナンバーリンクと同じ)
  3. 問題で指定された端点に接続しない線を引いてはならない(ナンバーリンクと同じ)
  4. ブロックまたは配線に属さないマスには0を当てはめる
  5. ブロック外の領域(0で示されるマス)には、線を引ける。数字が入らないブロック内の領域(+で示されるマス)には、線を引けない。

(注) チェックツールの仕様により、同じ数字の置かれたマスは接続されているものとみなす。コの字型の迂回がある回答などは、上記のルールに違反する場合があるため注意すること(2018年度までと同様。詳細はこちらを参照)

その他

※以下は暫定版です。今後変更の可能性があります。

得点の計算方法

計算式

※以下は暫定版です。今後変更の可能性があります。

質問・不具合等

GitHubのIssuesにご登録下さい


Copyright (c) 2019 DAシンポジウム実行委員会