AT_awtf2026heuristic_a Brightness Control

高橋君は、舞台照明の明るさを自動で調整する装置を開発している。 この装置では、格子状の盤面に反射板、分光板、吸収ブロックを配置することで、入射した光の進み方を制御できる。反射板は光の向きを変え、分光板は光を 2 方向に分け、吸収ブロックは光を消滅させる。 これから順番に必要となる明るさの列が事前に与えられている。盤面上の部品をうまく操作しながら光を発射し、できるだけ目標に近い明るさの列を実現せよ。

$ N \times N $ のグリッドがある。左上のマスの座標を $ (0, 0) $ とし、下方向に $ i $ マス、右方向に $ j $ マス進んだ位置の座標を $ (i, j) $ とする。 各マスには、高々 1 つの物体を設置できる。設置できる物体は以下のいずれかである。 - 左下と右上を結ぶ反射板 `/` - 左上と右下を結ぶ反射板 `\` - 左下と右上を結ぶ分光板 `Z` - 左上と右下を結ぶ分光板 `N` - 吸収ブロック `#` なお、分光板 `Z` と `N` では、文字中の斜め線の向きが分光板の向きに対応している。 物体が設置されていないマスを空マスと呼ぶ。 初期盤面は自由に設定してよい。初期盤面の設定は操作ターン数に含まれない。 マス $ (0, N/2) $ の上辺には光線の発射装置がある。この装置から、強さ $ 1 $ 、鮮明度 $ 60 $ の光線を下向きに発射できる。 発射された光線は、以下のように進行方向・強さ・鮮明度を変えながら、盤面上を進む。 **空マス：** 光線が空マスに入った場合、光線はそのまま直進する。 **吸収ブロック：** 光線が吸収ブロックに入った場合、その光線は消滅する。 **反射板：** 光線が反射板に入った場合、光線は 90 度向きを変えて反射される。反射方向は、入射する直前の光線の進行方向と反射板の向きによって次の表のように定まる。 入射前の進行方向 反射板 `/` 反射板 `\` ↑→← →↑↓ ↓←→ ←↓↑ **分光板：** 光線が分光板に入った場合、鮮明度が正なら、光線は直進する光線と、分光板と同じ向きの反射板で反射された場合と同じ方向へ進む光線の 2 本に分かれる。分かれた後の 2 本の光線の強さは、それぞれ入射した光線の半分であり、鮮明度は入射した光線より $ 1 $ 小さい。 一方、鮮明度が $ 0 $ の光線がさらに分光板に入ると、光は散乱し、装置の出力に予期しない影響を与えてしまう。散乱した光線はそれ以上追跡せず、出力値には加算されない。1 回の発射において、散乱したすべての光線の強さの合計を**散乱値**とする。 **出力：** 光線がグリッドの外へ出た場合、その光線は出力されたものとみなす。グリッドのどの辺から外へ出てもよい。1 回の発射において、グリッドの外へ出たすべての光線の強さの合計を**出力値**とする。 #### 例  実線は反射板、破線は分光板、黒マスは吸収ブロックを表す。 上部から入射した光は、半分がそのままグリッドの外へ出力され、残りの半分が右下のループに入る。 ループに入った光は、その半分が吸収され、 $ 1/4 $ がグリッドの外へ出力され、残りの $ 1/4 $ が再びループに入る。 これを繰り返すことで、最終的に出力値は $ \frac{2}{3} - \frac{1}{3}\cdot 2^{-59} $ 、散乱値は $ 2^{-60} $ となる。 あなたは初期盤面を設定したあと、以下の操作を最大で $ T $ ターンまで行うことができる。 - 空マスに物体を設置する。 - マスに設置されている物体を除去する。 - 反射板または分光板 1 つを回転する。これにより `/` と `\` が、`N` と `Z` がそれぞれ入れ替わる。 - 光を発射する。 目標となる光の強さの列 $ A_0, A_1, \ldots, A_{L-1} $ が与えられる。あなたは光の発射操作をちょうど $ L $ 回行わなければならない。 $ k $ 回目の光の発射によって得られた出力値を $ B_k $ 、散乱値を $ R_k $ とする。 $ A $ と $ B $ の誤差、および散乱値の総和をできるだけ小さくせよ。 #### 出力値と散乱値に関する補足 分光板によるループを含む盤面では、光線が無限に分岐・循環しうる。このような場合でも、連立一次方程式を解くことで出力値を厳密に定義することはできる。しかし、実数値を用いた計算では、計算誤差によりスコアが変わる可能性がある。 そこで本問題では、各光線に鮮明度を持たせ、分光板を通る回数を高々 $ 60 $ 回に制限している。鮮明度が $ 0 $ の光線がさらに分光板に入った場合、その光線は散乱し、それ以上追跡されない。このため、1 回の発射における処理は必ず有限回で終了する。 また、計算上は強さ $ 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

入力は以下の形式で標準入力から与えられる。 > $ 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 $ の文字列であり、各文字は対応するマスの初期状態を表す 1 文字 `.`, `/`, `\`, `Z`, `N`, `#` のいずれかである。 続いて、最大で $ T $ 行の操作を出力せよ。各行には、以下のいずれかの形式で操作を出力する。 マス $ (i, j) $ に物体 $ c $ を設置する場合： > $ 1 $ $ i $ $ j $ $ c $ ここで $ c $ は `/`, `\`, `Z`, `N`, `#` のいずれかである。この操作は、マス $ (i, j) $ が空マスである場合にのみ実行できる。 マス $ (i, j) $ に設置されている物体を除去する場合： > $ 2 $ $ i $ $ j $ この操作は、マス $ (i, j) $ が空マスでない場合にのみ実行できる。 マス $ (i, j) $ に設置されている反射板または分光板を回転する場合： > $ 3 $ $ i $ $ j $ この操作は、マス $ (i, j) $ に反射板もしくは分光板が置かれている場合にのみ実行できる。 光を発射する場合： > $ 4 $ 出力に含まれる光の発射操作はちょうど $ L $ 回でなければならない。 [例を見る](https://img.atcoder.jp/awtf2026heuristic/yTfWSw9z.html?lang=ja&seed=0&output=sample)

### 得点 $ k $ 回目の光の発射によって得られた出力値を $ B_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{全参加者中の最小絶対スコア}{自身の絶対スコア}) $ の**相対評価スコア**が得られ、その和が提出の得点となる。 最終順位はコンテスト終了後に実施される、より多くの入力に対するシステムテストにおける得点で決定される。 暫定テスト、システムテストともに、一部のテストケースで不正な出力や制限時間超過をした場合、そのテストケースの相対評価スコアは 0 点となり、そのテストケースにおいては「全参加者中の最小絶対スコア」の計算から除外される。 システムテストは**CE 以外の結果を得た一番最後の提出**に対してのみ行われるため、最終的に提出する解答を間違えないよう注意せよ。 #### テストケース数 - 暫定テスト: 50 個 - システムテスト: 2000 個、コンテスト終了後に [seeds.txt](https://img.atcoder.jp/awtf2026heuristic/seeds.txt) (sha256=09a07ffd9ee0e93469394a2cb36a22a9b4be312865de69d90d27198173124f04) を公開 #### 相対評価システムについて 暫定テスト、システムテストともに、CE 以外の結果を得た一番最後の提出のみが順位表に反映される。 相対評価スコアの計算に用いられる各テストケースごとの全参加者中の最小絶対スコアの算出においても、順位表に反映されている最終提出のみが用いられる。 順位表に表示されているスコアは相対評価スコアであり、新規提出があるたびに、相対評価スコアが再計算される。 一方、提出一覧から確認できる各提出のスコアは各テストケースごとの絶対スコアをそのまま足し合わせたものであり、相対評価スコアは表示されない。 最新以外の提出について、現在の順位表における相対評価スコアを知るためには、再提出が必要である。 不正な出力や制限時間超過をした場合、提出一覧から確認できるスコアは 0 となるが、順位表には正解したテストケースに対する相対スコアの和が表示される。 #### 実行時間について 実行時間には多少のブレが生じる。 また、システムテストでは同時に大量の実行を行うため、暫定テストに比べて数%程度実行時間が伸びる現象が確認されている。 そのため、実行時間制限ギリギリの提出がシステムテストでTLEとなる可能性がある。 プログラム内で時間を計測して処理を打ち切るか、実行時間に余裕を持たせることを推奨する。 ### 入力生成方法 以下では、 $ \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} \\\] ### ツール(入力ジェネレータ・ビジュアライザ) - [Web版](https://img.atcoder.jp/awtf2026heuristic/yTfWSw9z.html?lang=ja): ローカル版より高性能でアニメーション表示が可能です。 - [ローカル版](https://img.atcoder.jp/awtf2026heuristic/yTfWSw9z.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/awtf2026heuristic/yTfWSw9z_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。 ### 生成AIの利用に関して **本コンテストで生成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. ```