アルゴリズムデザインコンテスト2018（ADC2018）ルール説明

概要

• 基本は、ADC2016,ADC2017と同じく「ナンバーリンク(３次元拡張)＋解の品質」
• １つ以上の盤面に数字が配置されており、同じ数字の間を線で接続する
• 線は横方向(X)、縦方向(Y)、または隣接する盤面の同じ位置の間(Z)に引くことができる
• 線は分岐してはいけない

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

詳細

問題フォーマット

1. 盤面サイズは [X]X[Y]X[Z] の形で表される
   1. (X,Y): 盤面平面のマスの数を表す(X:横方向、Y:縦方向)
   2. Z : 盤面の層の数を表す
2. 盤面平面のサイズは最大で72x72 (つまり、X,Y はそれぞれ 1 ≦ X ≦ 72, 1 ≦ Y ≦ 72 を満たす)
3. 層数は最大で8 (つまり、Z は 1 ≦ Z ≦ 8 を満たす)
4. LINEの定義がある。LINE は 連続する自然数 (1,2,…) で表される
5. 各LINEは、LINEを表す数字と、端点を示す複数の位置 (x,y,z) により定義される (0 ≦ x ＜X, 0 ≦ y ＜Y, 1 ≦ z ≦ Z)
   1. LINEは分岐しない、つまり、端点を示す位置の数は2個とする
   2. LINEは層をまたいでも良いし、またがなくても良い。つまり、端点を示す2つの位置 (x1,y1,z1), (x2,y2,z2) について、z1 ＝ z2 でも z1 ≠ z2 でも良い
6. LINE数に上限なし（コンテストとしては、nlcheck.pyを通ることは事前確認されたい）

回答フォーマット

1. 盤面層数分の2次元回答フォーマットを並べたものがADC2018の回答フォーマットとなる
2. 2次元回答フォーマット(＝盤面の各層の回答フォーマット)は、各マスに数字を当てはめたものとする（2016年度までと同様）
3. 隣接する上下両方の盤面と接続されるマスは、盤面平面内ではどの線にも接続されていない孤立点となる

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

テキストダウンロード

回答ルール

1. 問題で指定されたLINEの端点の間を分岐の無い線で接続する
   1. LINEの端点が存在するマスは、X, Y, Z方向に隣接する最大6個のマスのうち1個と接続される
   2. LINEを構成する端点以外のマスは、X, Y, Z方向に隣接する最大6個のマスのうち2個と接続される
2. 問題で指定されたLINEの端点に接続の無い線を引いてはいけない
3. LINEに属さないマスは0を当てはめる

(注) 同じ数字の置かれたマスは接続されているものとみなす。コの字型の迂回がある回答などは、上記のルールに違反する場合があるため注意すること。

その他

• 問題ファイル、回答ファイルは１問１ファイルのテキスト形式。文字コードはASCII、改行コードはCR+LF(Windowsなど)、または、LF(UNIX, Linux, MacOS Xなど)
• 参加１チームあたり最大３問まで問題を自作して当日提供可能
• 問題ファイル、回答ファイルは、運営側が準備する会場の無線LANアクセスポイント(802.11b/g)経由で自動運営システムとの間でやり取りする
• 一度回答を提出した問題を、再度回答するのは不可
• 会場以外の場所(遠隔地)にソルバーを設置して、ネットワーク経由で利用するのは不可
• 事前に作成した自作問題の解をそのまま提出するのは不可。自作の問題も競技時間内にソルバーで解くこと。
• 求解手法を当日ポスターで発表すること

得点の計算方法

隣接配線境界数のカウント方法

• Z平面において、縦方向（Y方向）、横方向（X方向）で5マス以上、他の線と隣接している境界の個数をカウントします。 下図(2)のLINE1とLINE2のように、一旦離れて再度隣接した場合は合計でカウントします。

上図(1)、上図(3)は線長の合計と線が曲った回数は同じですが、隣接している境界の数が19と0で異なります。(3)の方が品質がよいものとします。

並行区間の境界数の計算方法のイメージを、以下に示します。

def calc_number_of_parallel_borders():
    number_of_parallel_borders = 0
    for line1 in range(1, number_of_lines-1):
        for line2 in range(line1+1, number_of_lines):
            para_len = get_parallel_line_length(line1, line2)
            if 5 <= para_len:
                number_of_parallel_borders += para_len
    return number_of_parallel_borders

get_parallel_line_lengthは、線と線が隣接する境界の数の合計を求めます（下図参照）。

計算式

• 正解ポイント：問題ごとに、正解のとき＋１ポイント
• 品質ポイント：問題ごとに、正解した全チームへ１０ポイントを解の品質に応じて比例配分 （解の品質） ＝ １／（（線長の合計）＋（線が曲がった回数）＋ １／３×（隣接配線境界数））… 値が大きいほど良い解
  （線長は、マスの中心を線の起点／終点／曲がる点として測る。XYZ方向とも１マスが長さ１）
• 出題ボーナスポイント：参加チームが持参した問題を自分で正解したとき、ボーナスで＋１ポイント

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