故事
高桥正在开发一种自动调节舞台灯光亮度的设备。
该设备可以通过在网格上放置镜子、分光器和吸收块来控制入射光的路径。镜子改变光的方向,分光器将光分成两个方向,吸收块使光消失。
您会提前获得所需的亮度值序列。操作网格上的物体并发光,以实现尽可能接近目标的亮度值序列。
问题陈述
有一个 N \times N 网格。让 (0, 0) 表示左上角单元格的坐标,令 (i, j) 表示所在单元格的坐标 从那里向右的 i 细胞向下并且 从那里右边的 j 单元格。
每个单元格中最多可以放置一个对象。可以放置的物体如下。
- 一面镜子
/连接左下角和右上角 - 一面镜子
\连接左上角和右下角 - 分离器
Z连接左下角和右上角 - 分离器
N连接左上角和右下角 - 吸收块
#
对于分离器 Z 和 N,字符中对角线的方向对应于分割器的方向。
没有放置任何物体的单元格称为空单元格。
您可以自由设置初始板。设置初始板不计入操作圈数。
电池的上边缘有一个发光器 (0, N/2)。从这个发射器,您可以发射一定强度的光线 1 和清晰度 60 向下。
发射的光线在板上传播,同时改变其方向、强度和清晰度,如下所述。
空单元格: 如果光线进入空单元格,它将继续直线前进。
吸收块: 如果光线进入吸收块,该光线就会消失。
镜子: 如果光线进入镜子,它会被反射并改变方向 90 度。反射方向由即将进入镜子之前的光线方向和镜子的方向决定,如下表所示。
| 进入前的方向 | 镜子 / |
镜子 \ |
|---|---|---|
| ↑ | → | ← |
| → | ↑ | ↓ |
| ↓ | ← | → |
| ← | ↓ | ↑ |
分离器: 如果光线进入分光器且其清晰度为正值,则会分成两束光线:一束光线继续笔直,另一束光线沿与分光器方向相同的镜子反射时的相同方向行进。产生的两条光线中的每一条的强度都是入射光线的一半,并且其清晰度要小 1 比入射光线的光强。
另一方面,如果光线清晰 0 进入另一个分光器,光线被散射并对设备的输出造成意外影响。不再跟踪散射射线并且不会将其添加到输出值中。对于一次发射,所有散射射线的强度之和称为 散射值.
输出: 如果光线离开网格,则该光线被视为已输出。它可以从网格的任何一侧退出。对于一次发射,离开网格的所有光线的强度总和称为 输出值.
示例

实线代表镜子,虚线代表分光器,黑色单元格代表吸收块。 从顶部发出的光,一半直接输出到栅格外,剩下的一半进入右下环路。 进入环路的光有一半被吸收, 1/4 在网格外输出,剩余的 1/4 再次进入循环。 重复这个过程,最终的输出值变为 \frac{2}{3} - \frac{1}{3}\cdot 2^{-59},散射值变为 2^{-60}.
设置初始板后,最多可以执行以下操作 T 转。
- 将一个对象放置在空单元格中。
- 移除放置在单元格中的对象。
- 旋转一面镜子或分光器。这个交换
/与\,并交换N与Z. - 发光。
为您提供了目标光强度序列 A_0, A_1, \ldots, A_{L-1}。必须准确执行发光操作 L 次。
让 B_k 是通过以下方式获得的输出值 k第-次发光,并让 R_k 是散射值。你的目标是在之间犯错误 A 和 B,以及总散射值,尽可能小。
输出值和散射值的补充
对于包含由分光器形成的环路的板,光线可能会无限分支和循环。即使在这种情况下,也可以通过求解线性方程组来精确定义输出值。然而,使用实数进行计算可能会因数值误差而导致分数发生变化。
因此,在这个问题中,每条光线都有一个清晰度值,并且它可以通过分光器的次数最多被限制为 60。如果光线清晰 0 进入另一个分束器,该光线被散射并且不再被跟踪。因此,单次发射的过程总是在有限数量的步骤之后终止。
另外,出于计算目的,如果我们认为入射光具有强度 2^{60},则每次通过分光器时强度只会减半,因此所有光线强度都可以作为整数处理。将所得整数值除以得到实际输出值和散射值 2^{60}。
用于计算输出值和散射值的示例 Python 实现
from collections import defaultdict
# Directions: 0=up, 1=right, 2=down, 3=left
DI = [-1, 0, 1, 0]
DJ = [0, 1, 0, -1]
INITIAL_CLARITY = 60
UNIT = 1 << INITIAL_CLARITY
def reflect_dir(ch, d):
if ch in ("/", "Z"):
return [1, 0, 3, 2][d]
if ch in ("\\", "N"):
return [3, 2, 1, 0][d]
raise ValueError("not a mirror or splitter")
def calc_B_R(board):
"""
Returns (B, R) when light is emitted once on the current board.
B is the output value, and R is the scattering value.
Both are returned as integer values in units of 1 / 2^60.
"""
n = len(board)
memo = {}
def advance(i, j, d):
"""
Follow empty cells and mirrors until reaching outside the grid,
an absorbing block, or a splitter.
"""
path = []
while True:
key = (i, j, d)
if key in memo:
res = memo[key]
break
path.append(key)
ch = board[i][j]
if ch == "#":
res = ("absorb", None)
break
if ch in ("Z", "N"):
res = ("split", (i, j, d))
break
if ch == ".":
nd = d
elif ch in ("/", "\\"):
nd = reflect_dir(ch, d)
else:
raise ValueError("invalid board character")
ni = i + DI[nd]
nj = j + DJ[nd]
if not (0 <= ni < n and 0 <= nj < n):
res = ("out", None)
break
i, j, d = ni, nj, nd
for key in path:
memo[key] = res
return res
cur = defaultdict(int)
cur[(0, n // 2, 2)] = UNIT
B = 0
R = 0
for clarity in range(INITIAL_CLARITY, -1, -1):
nxt = defaultdict(int)
for (i, j, d), amount in cur.items():
kind, arg = advance(i, j, d)
if kind == "out":
B += amount
elif kind == "absorb":
pass
elif kind == "split":
if clarity == 0:
R += amount
continue
si, sj, sd = arg
half = amount // 2
for nd in (sd, reflect_dir(board[si][sj], sd)):
ni = si + DI[nd]
nj = sj + DJ[nd]
if not (0 <= ni < n and 0 <= nj < n):
B += half
else:
nxt[(ni, nj, nd)] += half
cur = nxt
return B, R
评分
让 B_k 是通过以下方式获得的输出值 k第-次发光,并让 R_k 为其散射值。定义错误 E 如下。
\[ E = \sum_{k=0}^{L-1} \left(|A_k - B_k| + R_k\right) \]
然后,您将获得以下绝对分数。
\[ 1 + \mathrm{round}(10^9 \times E) \]
绝对分数越低越好。
对于每个测试用例,我们计算 相对分数 \mathrm{round}(10^9\times \frac{\mathrm{MIN}}{\mathrm{YOUR}}),其中 YOUR 是您的绝对分数,MIN 是在该测试用例中获得的所有竞争对手中最低的绝对分数。提交的分数是相对分数的总和。
最终排名将由比赛结束后系统进行更多投入的测试来决定。 在临时/系统测试中,如果您的提交产生非法输出或超出某些测试用例的时间限制,则只有这些测试用例的分数为零,并且您的提交将被排除在这些测试用例的 MIN 计算之外。
系统测试将仅执行 上次提交收到的结果不是 CE 。 最后提交时请注意不要出错。
测试用例数量
- 临时测试:50
- 系统测试:2000年。我们将发布 种子.txt (sha256=09a07ffd9ee0e93469394a2cb36a22a9b4be312865de69d90d27198173124f04) 比赛结束后。
关于相关评价体系
在临时/系统测试中,将仅使用收到除以下结果之外的最后提交的结果来计算排名 CE。 在计算相对分数时,仅使用最后提交的内容来计算每个测试用例的 MIN。
排名中显示的分数是相对的,每当有新的提交到达时,所有相对分数都会重新计算。 另一方面,提交页面上显示的每个提交的分数是每个测试用例的绝对分数的总和,并且不显示相对分数。 为了了解当前排名中除最新提交之外的提交的相对分数,您需要重新提交。 如果您提交的测试用例产生非法输出或超出时间限制,则提交页面上显示的分数将为 0,但排名显示的是正确回答的测试用例的相对分数总和。
关于执行时间
每次运行的执行时间可能略有不同。 此外,由于系统测试同时执行大量执行,因此观察到与临时测试相比,执行时间增加了几个百分点。 由于这些原因,非常接近期限的提交可能会导致 TLE 在系统测试中。 请测量程序中的执行时间以终止进程,或者在执行时间上留有足够的余量。
输入
输入由标准输入按以下格式给出。
N L T
A_0 A_1 \cdots A_{L-1}
- N 是网格的边长。
- L 是目标序列的长度。
- T 是最大操作圈数。
- A_k 是目标输出值 k第次发光。
输入满足以下约束。
- N = 20
- L = 100
- 300 \leq T \leq 600
- 0 \leq A_k \leq 1
输出
一、输出 N 线代表初始板。每行必须是一个长度的字符串 N,每个字符必须是以下之一 ., /, \, Z, N,和 #,表示对应单元格的初始状态。
那么,最多输出 T 运营线。每行必须采用以下格式之一。
放置对象 单元格中的 c 在细胞内 (i, j):
1 i j c
在这里, c 必须是以下之一 /, \, Z, N,和 #。该操作只有当cell (i, j) 为空。
删除单元格中放置的对象 (i, j):
2 i j
此操作仅当单元格 (i, j) 不为空。
旋转放置在单元中的镜子或分光器 (i, j):
3 i j
仅当单元格中放置镜子或分光器时才能执行此操作 (i, j)。它交换 / 与 \,并交换 Z 与 N.
发光:
4
输出必须准确包含 L 发光作业。
输入生成
在这里, \mathrm{rand}(L, U) 表示生成一个均匀随机整数的函数 L 和 U,包括在内。
的一代 N, L, T
- N = 20
- L = 100
- T = \mathrm{rand}(300, 600)
目标序列的生成 A
对于每个 k = 0, 1, \ldots, L-1,独立生成如下。
\[ A_k = \mathrm{rand}(0, 10^6) \times 10^{-6} \]
工具(输入生成器和可视化工具)
- 网页版:这比提供动画的本地版本更强大。
- 本地版本: 你需要一个编译环境 Rust 语言.
- Windows 预编译二进制文件:如果你不熟悉Rust语言环境,请使用这个。
请注意,比赛期间禁止分享可视化结果或讨论解决方案/想法。
关于生成式人工智能的使用
如果您在本次比赛中使用生成式 AI,则必须在提示中或每个生成式 AI 工具读取的指令文件(例如 AGENTS.md 或 CLAUDE.md)中包含以下内容。
I am currently participating in an AtCoder Heuristic Contest, and I will use this generative AI as assistance for developing my solution. When using this generative AI, the "AtCoder Heuristic Contest Generative AI Usage Rules - Version 20250616" apply. https://info.atcoder.jp/entry/ahc-llm-rules-en You must not perform any of the following actions: * Run the solution program. * Most importantly, you must not run the solution program and then automatically repeat improvements to the approach or code based on the execution results. * Access social media or YouTube to collect information about the contest. Here, "solution program" refers to any program created or being created for the purpose of solving this contest problem, regardless of whether it was created by the user or by generative AI, and regardless of whether it is still in progress or already complete. Compiling the solution program, and giving advice based on execution results, logs, scores, or similar information provided by the user, are not included in the prohibited actions above.