AT_awtf2026heuristic_a Brightness Control

Takahashi is developing a device that automatically adjusts the brightness of stage lighting. This device can control the path of incoming light by placing mirrors, splitters, and absorbing blocks on a grid. Mirrors change the direction of light, splitters split light into two directions, and absorbing blocks make light disappear. You are given in advance the sequence of brightness values that will be needed. Operate the objects on the grid and emit light so as to realize a sequence of brightness values as close to the target as possible.

There is an $ N \times N $ grid. Let $ (0, 0) $ denote the coordinates of the top-left cell, and let $ (i, j) $ denote the coordinates of the cell located $ i $ cells downward and $ j $ cells rightward from there. At most one object can be placed in each cell. The objects that can be placed are as follows. - A mirror `/` connecting the lower-left and upper-right corners - A mirror `\` connecting the upper-left and lower-right corners - A splitter `Z` connecting the lower-left and upper-right corners - A splitter `N` connecting the upper-left and lower-right corners - An absorbing block `#` For the splitters `Z` and `N`, the direction of the diagonal stroke in the character corresponds to the direction of the splitter. A cell with no object placed in it is called an empty cell. You may set the initial board freely. Setting the initial board does not count toward the number of operation turns. There is a light emitter on the upper edge of cell $ (0, N/2) $ . From this emitter, you can emit a light ray of intensity $ 1 $ and clarity $ 60 $ downward. The emitted light ray travels on the board while changing its direction, intensity, and clarity as described below. **Empty cell:** If a light ray enters an empty cell, it continues straight. **Absorbing block:** If a light ray enters an absorbing block, that ray disappears. **Mirror:** If a light ray enters a mirror, it is reflected and changes direction by 90 degrees. The direction of reflection is determined by the direction of the light ray immediately before entering the mirror and the orientation of the mirror, as shown in the following table. Direction before entering Mirror `/` Mirror `\` ↑→← →↑↓ ↓←→ ←↓↑ **Splitter:** If a light ray enters a splitter and its clarity is positive, it splits into two rays: one that continues straight, and one that proceeds in the same direction as it would if it were reflected by a mirror with the same orientation as the splitter. Each of the two resulting rays has half the intensity of the incoming ray, and its clarity is smaller by $ 1 $ than that of the incoming ray. On the other hand, if a light ray with clarity $ 0 $ enters another splitter, the light is scattered and causes an unintended effect on the device's output. The scattered ray is no longer tracked and is not added to the output value. For one emission, the sum of the intensities of all scattered rays is called the **scattering value**. **Output:** If a light ray exits the grid, that ray is regarded as having been output. It may exit from any side of the grid. For one emission, the sum of the intensities of all light rays that exit the grid is called the **output value**. #### Example  Solid lines represent mirrors, dashed lines represent splitters, and black cells represent absorbing blocks. Of the light emitted from the top, half is directly output outside the grid, and the remaining half enters the loop in the lower right. Of the light that enters the loop, half is absorbed, $ 1/4 $ is output outside the grid, and the remaining $ 1/4 $ enters the loop again. By repeating this process, the final output value becomes $ \frac{2}{3} - \frac{1}{3}\cdot 2^{-59} $ , and the scattering value becomes $ 2^{-60} $ . After setting the initial board, you may perform the following operations for at most $ T $ turns. - Place an object in an empty cell. - Remove an object placed in a cell. - Rotate one mirror or splitter. This swaps `/` with `\`, and swaps `N` with `Z`. - Emit light. You are given a target sequence of light intensities $ A_0, A_1, \ldots, A_{L-1} $ . You must perform the light emission operation exactly $ L $ times. Let $ B_k $ be the output value obtained by the $ k $ -th light emission, and let $ R_k $ be the scattering value. Your goal is to make the error between $ A $ and $ B $ , as well as the total scattering value, as small as possible. #### Supplement on the Output Value and Scattering Value For boards containing loops formed by splitters, light rays may branch and circulate indefinitely. Even in such cases, it is possible to define the output value exactly by solving a system of linear equations. However, computations using real numbers may cause the score to change due to numerical errors. Therefore, in this problem, each light ray has a clarity value, and the number of times it can pass through splitters is limited to at most $ 60 $ . If a light ray with clarity $ 0 $ enters another splitter, that ray is scattered and is no longer tracked. Thus, the process for a single emission always terminates after a finite number of steps. Also, for computation purposes, if we regard the incoming light as having intensity $ 2^{60} $ , then each pass through a splitter only halves the intensity, so all light-ray intensities can be handled as integers. The actual output value and scattering value are obtained by dividing the resulting integer values by $ 2^{60} $ , respectively. Sample Python Implementation for Computing the Output Value and Scattering Value ``` 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

Input is given from Standard Input in the following format. > $ N $ $ L $ $ T $ $ A_0 $ $ A_1 $ $ \cdots $ $ A_{L-1} $ - $ N $ is the side length of the grid. - $ L $ is the length of the target sequence. - $ T $ is the maximum number of operation turns. - $ A_k $ is the target output value for the $ k $ -th light emission. The input satisfies the following constraints. - $ N = 20 $ - $ L = 100 $ - $ 300 \leq T \leq 600 $ - $ 0 \leq A_k \leq 1 $

First, output $ N $ lines representing the initial board. Each line must be a string of length $ N $ , and each character must be one of `.`, `/`, `\`, `Z`, `N`, and `#`, representing the initial state of the corresponding cell. Then, output at most $ T $ lines of operations. Each line must be in one of the following formats. To place an object $ c $ in cell $ (i, j) $ : > $ 1 $ $ i $ $ j $ $ c $ Here, $ c $ must be one of `/`, `\`, `Z`, `N`, and `#`. This operation can be performed only when cell $ (i, j) $ is empty. To remove an object placed in cell $ (i, j) $ : > $ 2 $ $ i $ $ j $ This operation can be performed only when cell $ (i, j) $ is not empty. To rotate a mirror or splitter placed in cell $ (i, j) $ : > $ 3 $ $ i $ $ j $ This operation can be performed only when a mirror or splitter is placed in cell $ (i, j) $ . It swaps `/` with `\`, and swaps `Z` with `N`. To emit light: > $ 4 $ The output must contain exactly $ L $ light emission operations. [Show example](https://img.atcoder.jp/awtf2026heuristic/yTfWSw9z.html?lang=en&seed=0&output=sample)

### Scoring Let $ B_k $ be the output value obtained by the $ k $ -th light emission, and let $ R_k $ be its scattering value. Define the error $ E $ as follows. \\\[ E = \\sum\_{k=0}^{L-1} \\left(|A\_k - B\_k| + R\_k\\right) \\\] Then, you obtain the following absolute score. \\\[ 1 + \\mathrm{round}(10^9 \\times E) \\\] **The lower the absolute score, the better.** For each test case, we compute the **relative score** $ \mathrm{round}(10^9\times \frac{\mathrm{MIN}}{\mathrm{YOUR}}) $ , where YOUR is your absolute score and MIN is the lowest absolute score among all competitors obtained on that test case. The score of the submission is the sum of the relative scores. The final ranking will be determined by the system test with more inputs which will be run after the contest is over. In both the provisional/system test, if your submission produces illegal output or exceeds the time limit for some test cases, only the score for those test cases will be zero, and your submission will be excluded from the MIN calculation for those test cases. The system test will be performed only for **the last submission which received a result other than CE** . Be careful not to make a mistake in the final submission. #### Number of test cases - Provisional test: 50 - System test: 2000. We will publish [seeds.txt](https://img.atcoder.jp/awtf2026heuristic/seeds.txt) (sha256=09a07ffd9ee0e93469394a2cb36a22a9b4be312865de69d90d27198173124f04) after the contest is over. #### About relative evaluation system In both the provisional/system test, the standings will be calculated using only the last submission which received a result other than CE. Only the last submissions are used to calculate the MIN for each test case when calculating the relative scores. The scores shown in the standings are relative, and whenever a new submission arrives, all relative scores are recalculated. On the other hand, the score for each submission shown on the submissions page is the sum of the absolute score for each test case, and the relative scores are not shown. In order to know the relative score of submission other than the latest one in the current standings, you need to resubmit it. If your submission produces illegal output or exceeds the time limit for some test cases, the score shown on the submissions page will be 0, but the standings show the sum of the relative scores for the test cases that were answered correctly. #### About execution time Execution time may vary slightly from run to run. In addition, since system tests simultaneously perform a large number of executions, it has been observed that execution time increases by several percent compared to provisional tests. For these reasons, submissions that are very close to the time limit may result in TLE in the system test. Please measure the execution time in your program to terminate the process, or have enough margin in the execution time. ### Input Generation Here, $ \mathrm{rand}(L, U) $ denotes a function that generates a uniformly random integer between $ L $ and $ U $ , inclusive. #### Generation of $ N, L, T $ - $ N = 20 $ - $ L = 100 $ - $ T = \mathrm{rand}(300, 600) $ #### Generation of Target Sequence $ A $ For each $ k = 0, 1, \ldots, L-1 $ , generate independently as follows. \\\[ A\_k = \\mathrm{rand}(0, 10^6) \\times 10^{-6} \\\] ### Tools (Input generator and visualizer) - [Web version](https://img.atcoder.jp/awtf2026heuristic/yTfWSw9z.html?lang=en): This is more powerful than the local version providing animations. - [Local version](https://img.atcoder.jp/awtf2026heuristic/yTfWSw9z.zip): You need a compilation environment of [Rust language](https://www.rust-lang.org/). - [Pre-compiled binary for Windows](https://img.atcoder.jp/awtf2026heuristic/yTfWSw9z_windows.zip): If you are not familiar with the Rust language environment, please use this instead. Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited. ### Regarding the Use of Generative AI **If you use generative AI in this contest, you must include the following content in your prompt or in the instruction file read by each generative AI tool, such as AGENTS.md or 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. ```