HexTiles
問題文
六角形のタイルを回転させ、指定された出口どうしをパスで接続してください。
各タイルには、6つの辺を3組に結ぶ 3本の線分 があります。タイルは、各辺に N 枚のタイルを持つ六角形のグリッド上に配置されています。隣接するタイルの辺どうしが接することで線分がつながり、グリッド内を通るパスを形成します。
パスはグリッド外周の辺から入り、別の外周の辺から出ます。外周の各出口には 0 から始まる番号が、左上のタイルから時計回りに付けられています。
入力として P 組の出口ペアが与えられます。指定された2つの出口を結んでいるパスを 一致パス (matched path) と呼びます。
また、グリッド内には B 枚の ボーナスタイル が存在します。一致パスがボーナスタイルを通過すると、そのパスの得点が高くなります。
操作
1回の操作で、グリッド内のタイルを1枚選び、次のいずれかを行えます。
- 時計回りに 60° 回転する。
- 反時計回りに 60° 回転する。
操作回数を m とします。操作は最大 24 × N × N 回まで行えます。
一致パスの得点
一致パス1本の得点は次のように計算されます。
すべての一致パスの得点の合計を t とします。
最終得点
この値が負になった場合、最終得点は 0 になります。
例
以下は seed=1 に対する解の例です。
- 色付きのパス: 一致パス
- 灰色のパス: 不一致パス
- 黒色のパス: ループ
- 太いパス: 最も高得点のパス
- シアンのタイル: ボーナスタイル
- 太枠のタイル: 最後に回転したタイル
-showCoords を指定すると各タイルの座標も表示されます。グリッドとタイル
グリッドの表現
六角形グリッドは、W = 2N − 1 として W × W の正方形配列で表現されます。
正方形配列の四隅の一部は六角形グリッドに含まれないため、未使用セルとなります。未使用セルの値は -1 です。
タイルの向き
各タイルは 0 以上 5 以下 の整数で向きを表します。向きによって3本の線分が結ぶ辺の組み合わせが変わります。
入力
入力は標準入力から以下の形式で与えられます。
N
M
B
P
p_0 q_0
p_1 q_1
...
p_{P-1} q_{P-1}
a_{0,0}
a_{0,1}
...
a_{W-1,W-1}
r_0 c_0
r_1 c_1
...
r_{B-1} c_{B-1}
ここで W = 2N − 1 です。
- N
- グリッドサイズ。
- M
- 1回の操作あたりのペナルティ。
- B
- ボーナスタイルの枚数。
- P
- 接続すべき出口ペアの数。
- p_i, q_i
- 0-indexed の出口ID。出口
p_iと出口q_iを接続する必要があります。 - a_{r,c}
- 座標
(r,c)のタイルの向き。0〜5。未使用セルは -1。 - r_i, c_i
- i番目のボーナスタイルの座標。0-indexed。
制約
- 3 ≤ N ≤ 20
- 1 ≤ M ≤ 5
- 1 ≤ B ≤ 10
- 各タイルの向きは 0〜5、未使用セルは -1。
- ボーナスタイルは互いに異なるグリッド内のタイルです。
出力
最初に操作回数 m を出力し、その後に各操作を出力してください。
m
r_0 c_0 dir_0
r_1 c_1 dir_1
...
r_{m-1} c_{m-1} dir_{m-1}
各操作では座標 (r_i, c_i) のタイルを回転します。
dir_i = +1: 時計回りdir_i = -1: 反時計回り
m ≤ 24 × N × N を満たす必要があります。
得点
Raw Score
上で定義した最終得点が、そのテストケースにおける Raw Score です。
出力が不正な場合、そのテストケースの Raw Score は -1 になります。
不正解となる主な例は以下です。
- 出力形式が不正。
- 24 × N × N 回を超える操作を出力した。
- グリッド外または未使用セルのタイルを回転しようとした。
- 回転方向が
+1または-1ではない。 - 制限時間を超過した。
Normalized Score
Raw Score が負の場合、そのテストケースの Normalized Score は 0 です。それ以外の場合は次式で計算されます。
MAX の計算では、各競技者の最新提出のみが対象になります。
最後に、全テストケースの得点の合計が 100点満点 になるよう正規化されます。
入力生成方法
厳密な生成方法は、公式ビジュアライザのソースコードにある generate() メソッドを参照してください。
- N は 3〜20 から一様ランダムに選ばれます。
- M は 1〜5 から一様ランダムに選ばれます。
- B は 1〜10 から一様ランダムに選ばれます。
- まず各タイルの向きを 0〜5 からランダムに選んで 目標グリッド を生成します。
- 目標グリッド上で形成されたパスから、接続対象となる出口ペアが決定されます。
- 実際に入力として与えられるグリッドは、各タイルの向きを 0〜5 から改めてランダムに選んで生成されます。
- グリッド内から互いに異なる B 枚のボーナスタイルがランダムに選ばれます。
テストケース
- サンプルテストケース: 10 個
- 暫定テストケース: 100 個
- 最終テストケース: 5000 個
- このマッチはレーティング対象です。
ローカルテスター・ビジュアライザ
公式のオフラインテスターを使用して、ローカルでテスト・デバッグできます。テスターのソースコードには入力生成および得点計算の厳密な実装も含まれています。
基本的な実行方法
java -jar tester.jar -exec "<command>" -seed <seed>
<command> には解答プログラムを起動するコマンドを指定します。
主なオプション
| オプション | 説明 |
|---|---|
-seed <seed> | テストケース生成seed。0はランダム、1は各パラメータの最小値、2は最大値。既定値は1。 |
-debug | デバッグ情報を表示。 |
-noanimate | アニメーションを行わず、最終状態のみ表示。 |
-novis | 可視化を無効化。 |
-manual | 手動操作モード。左クリックで反時計回り、右クリックで時計回り。 |
-pause | 一時停止状態で開始。 |
-delay <ms> | 各手の表示間隔。既定値は100ms。 |
-showCoords | 各タイルの座標を表示。 |
-showOriginal | 目標グリッドを入力グリッドとして表示。 |
-N <N> | グリッドサイズを指定。 |
-M <M> | 操作ペナルティを指定。 |
-B <B> | ボーナスタイル数を指定。 |
通常モードでは -delay で指定した間隔で各操作を表示します。一時停止モードではキー入力ごとに次の操作へ進みます。スペースキーで通常モードと一時停止モードを切り替えられます。
seed範囲の一括実行、並列実行、制限時間設定、標準入出力の保存など、追加機能については Marathon Match Local Tester Parameters を参照してください。
提出
提出物は、ソースコードのみを含む 500 MB 以下の単一 ZIP ファイル とします。
ソースコードのファイル名は HexTiles.<適切な拡張子> とします。
対応言語は C#、Java、C++、Python、Rust、Kotlin です。