A - Polyomino Connection A

Contest Duration: 2021-10-10 13:30:00+0900 - 2021-10-10 17:30:00+0900 (local time) (240 minutes)

A - Polyomino Connection A Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

A,B,Cの3つの問題はテストケース数と入力の生成方法のみが異なります。

問題文

N\times N マスの盤面と B 種類のポリオミノがある。一番左上のマスの座標を (0, 0) とし、そこから下へ i マス、右へ j マス移動した先のマスの座標を (i, j) と定める。初期状態で全てのマスは通行不能であり、ポリオミノを盤面に配置するとその上が通行可能になる。盤面上の K 個のマスに印が付いており、ポリオミノを配置することで全ての印が付けられたマスが連結になるようにしたい。

例えば、上の図では左上の印と右上の印は連結になっているが、下の印とは連結になっていない。

同一種類のポリオミノを任意個配置することが出来るが、回転させたり、盤面からはみ出すように配置することは出来ない。また、1つのマスの上に2つ以上のポリオミノを重ねて配置することも出来ない。各ポリオミノの種類 b ごとにコスト C_b が定まっており、ポリオミノ b を m_b 個配置したとき、合計コストは \sum_{b=1}^B C_b m_b となる。出来るだけ小さい合計コストで全ての印が付けられたマスを連結にしてほしい。

得点

合計コストを S とすると、\mathrm{round}(10^8 / S) の得点が得られる。不正な出力(印のついたマスが連結になっていない、ポリオミノが盤面からはみ出している、もしくは重なっている)がされた場合、と判定される。 1つ以上のテストケースで以外の判定がされた場合、提出の得点は0点となる。コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。同じ得点を複数の参加者が得た場合、その得点を獲得した提出の早い方が上位となる。

入力

入力は以下の形式で標準入力から与えられる。

N K B
i_1 j_1
\vdots
i_K j_K
n_1 m_1 C_1
s^1_{1,1} \ldots s^1_{1,m_1}
\vdots
s^1_{n_1,1} \ldots s^1_{n_1,m_1}
\vdots
n_B m_B C_B
s^B_{1,1} \ldots s^B_{1,m_B}
\vdots
s^B_{n_B,1} \ldots s^B_{n_B,m_B}

一行目には盤面の縦・横の大きさを表す整数 N、印が付けられたマスの総数 K、ポリオミノの種類数 B が与えられる。全てのテストケースで N=50 で固定である。

続く K 行には印の付いたマスの情報が与えられ、その p 行目は p 番目の印の座標が (i_p, j_p) であることを表し、0\leq i_p\leq N-1, 0\leq j_p\leq N-1 を満たす。印の座標は全て異なる。

最後に B 種類のポリオミノに関する情報が一つずつ与えられる。

n_b と m_b は b 番目のポリオミノを囲う最小の長方形(バウンディングボックス)の縦・横の大きさを表す。n_1=m_1=1 であることが保証されている。
C_b は b 番目のポリオミノを1つ配置するのに必要なコストを表す正の整数である。
s^b_{i,j} は b 番目のポリオミノのバウンディングボックスの上から i マス目、左から j マス目の情報を表し、# の場合はポリオミノに属し、. の場合はポリオミノに属さないことを表している。
各ポリオミノは連結であることが保証されている。

出力

以下の形式で、一行目に使用するポリオミノの総数 m を、続く m 行には使用するポリオミノの種類を表す整数 b_i (1\leq b_i\leq B) とバウンディングボックスの左上の座標 (x_i, y_i) (0\leq x_i\leq N-n_{b_i}, 0\leq y_i\leq N-m_{b_i})を一行ずつ出力せよ。

m
b_1 x_1 y_1
\vdots
b_m x_m y_m

テストケース数

1 個

入力生成方法

A問題のテストケース数は1つであり、入力例 1 と同一である。手動等により事前に計算した出力のみを提出しても構わない。

ツール

Web版ビジュアライザ・入力ジェネレータ
ローカル実行版ビジュアライザ・入力ジェネレータ: 使用するには、Rust言語のコンパイル環境をご用意下さい。

入力例 1

50 70 11
0 0
35 0
49 14
8 49
0 2
1 19
41 31
30 18
3 8
44 10
32 42
27 27
0 27
17 3
28 18
17 48
4 13
1 21
17 17
10 25
14 16
35 36
19 7
25 12
6 46
25 24
18 32
31 47
15 12
41 15
24 16
49 22
49 17
29 42
30 32
22 8
36 39
9 12
7 7
20 46
16 15
17 34
16 21
17 28
46 4
26 21
45 17
10 32
26 35
45 31
40 45
28 45
0 20
17 22
45 9
33 34
39 20
46 20
30 5
10 48
9 37
26 37
29 30
29 46
41 19
0 4
4 47
6 37
36 2
2 25
1 1 1
#
7 4 2
####
#...
#...
###.
#...
#...
#...
4 5 2
#...#
#...#
#...#
#####
8 3 2
###
.#.
.#.
.#.
.#.
.#.
.#.
.#.
4 5 2
####.
#..##
####.
#..##
5 4 2
####
#...
###.
#...
####
4 4 2
####
#..#
#..#
####
5 8 3
#......#
#......#
########
#......#
#......#
8 7 3
..###..
.##.##.
##...##
#.....#
#######
#.....#
#.....#
#.....#
8 8 3
..######
.##.....
##......
#.......
#.......
##......
.##.....
..######
9 6 3
#....#
#...##
#..##.
#.##..
###...
#.##..
#..##.
#...##
#....#

出力例 1