AT_masters2026_final_a Copy-Paste Painting (A)

高橋画伯は、画像編集ソフトを駆使して新作アートの制作に取り組んでいる。 作品作りでは、複数のレイヤーを使い分けながら、少しずつ絵を描き足したり、別のレイヤーの内容を回転して重ねたり、不要になったレイヤーを消したりできる。 目標となる画像をできるだけ少ない手数で完成させる手順を求めてほしい。

$ N\times N $ のピクセルからなるレイヤーが $ K $ 枚ある。 各レイヤーには $ 0,\cdots,K-1 $ の番号が付けられている。 左上のピクセルの座標を $ (0,0) $ とし、そこから下に $ i $ ピクセル、右に $ j $ ピクセル進んだ先のピクセルの座標を $ (i,j) $ とする。 使用できる色は $ C $ 色あり、各色には $ 1,\cdots,C $ の番号が付けられている。 レイヤー $ k $ のピクセル $ (i,j) $ の色を $ c(k,i,j) $ で表すことにする。 $ c(k,i,j)=0 $ は、そのピクセルが透明であることを表す。 目標画像は、各ピクセルの色 $ g_{i,j} $ によって与えられる。 すべての $ (i,j) $ について $ c(0,i,j)=g_{i,j} $ が成り立つとき、目標画像が完成しているものとする。 他のレイヤーの状態は問わない。 初期状態では、すべてのレイヤーは透明であり、すべての $ k,i,j $ について $ c(k,i,j)=0 $ である。 以下の操作を高々 $ N^2 $ 回繰り返すことで、目標画像を完成させよ。 - $ \mathrm{paint}(k,i,j,x) $ : レイヤー $ k\in\{0,\cdots,K-1\} $ 、ピクセル $ (i,j) $ 、色 $ x\in\{0,\cdots,C\} $ を指定し、 $ c(k,i,j)=x $ に変更する。 **$ x=0 $ を指定した場合、そのピクセルは透明に戻る。** - $ \mathrm{copy}(k,h,r,\Delta i,\Delta j) $ : レイヤー $ k,h\in\{0,\cdots,K-1\} $ 、整数 $ r\in\{0,\cdots,3\} $ 、 $ \Delta i\in\{-N+1,\cdots,N-1\} $ 、 $ \Delta j\in\{-N+1,\cdots,N-1\} $ を指定する。レイヤー $ h $ を時計回りに 90 度回転する操作を $ r $ 回行って得られるレイヤーを $ h' $ とする。ただし、レイヤー $ h $ 自体は変更されない。 $ h' $ の左上のピクセルがレイヤー $ k $ のピクセル $ (\Delta i,\Delta j) $ に対応するように配置し、重ねる。その後、 $ h' $ で透明でないピクセルをレイヤー $ k $ に上書きする。すなわち、 $ c(h',i,j)\neq 0 $ であるすべての $ (i,j) $ に対し、 $ c(k,\Delta i+i,\Delta j+j)=c(h',i,j) $ と更新する。この操作によってレイヤー $ k $ の範囲外のピクセルが塗られる場合、WA と判定される。 **$ k=h $ であってもよい。** - $ \mathrm{clear}(k) $ : レイヤー $ k $ のすべてのピクセルを透明にする。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ C $ $ g_{0,0} $ $ \cdots $ $ g_{0,N-1} $ $ \vdots $ $ g_{N-1,0} $ $ \cdots $ $ g_{N-1,N-1} $ 入力は以下の制約を満たす。 - レイヤーの一辺の長さ $ N $ は $ N=32 $ で固定されている。 - レイヤーの枚数 $ K $ は $ 2 $ 以上 $ 5 $ 以下の整数である。 - 色の種類数 $ C $ は $ 2 $ 以上 $ 4 $ 以下の整数である。 - $ g_{i,j} $ は目標画像のピクセル $ (i,j) $ の色を表す $ 0 $ 以上 $ C $ 以下の整数である。 - 目標画像において、 $ 1,\cdots,C $ のすべての色が出現するとは限らない。 - 目標画像における非透明なピクセル数は $ N^2/2 $ 以上である。

行った操作を実行順に、以下の形式で 1 行ずつ標準出力に出力せよ。 - $ \mathrm{paint}(k,i,j,x) $ > $ 0 $ $ k $ $ i $ $ j $ $ x $ - $ \mathrm{copy}(k,h,r,\Delta i,\Delta j) $ > $ 1 $ $ k $ $ h $ $ r $ $ \Delta i $ $ \Delta j $ - $ \mathrm{clear}(k) $ > $ 2 $ $ k $

### 得点 操作回数を $ T $ とする。 目標画像において非透明なピクセル数、すなわち $ g_{i,j}\neq 0 $ を満たす $ (i,j) $ の個数を $ U $ とする。 このとき、以下の得点が得られる。 \\\[ \\mathrm{round}\\left(10^6\\times \\left(1+\\log\_2 \\frac{U}{T}\\right)\\right) \\\] 入力生成方法の違いにより、問題は A・B の 2 問 に分かれている。 それぞれ 150 個ずつのテストケースがあり、各テストケースの得点の合計がその問題に対する提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWAやTLEとなる。 各問題に対して獲得した最高得点の総和で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数のチームが得た場合、提出時刻に関わらず同じ順位となる。 ### 入力生成方法 $ \mathrm{rand}(L,U) $ を、 $ L $ 以上 $ U $ 以下の整数を一様ランダムに生成する関数とする。 非透明なピクセル全体からなる集合が上下左右 4 方向に連結であるとき、そのレイヤーの非透明なピクセルは連結であると呼ぶ。 A 問題の入力は以下のように生成される。 #### $ N $ , $ K $ , $ C $ の生成 $ N=32 $ で固定である。 $ K=\mathrm{rand}(2,5) $ 、 $ C=\mathrm{rand}(2,4) $ により生成される。 #### $ g $ の生成 まず、 $ K'=\mathrm{rand}(1,2K) $ を生成する。 $ K' $ 枚の透明なレイヤーを用意し、レイヤー $ k $ のピクセル $ (i,j) $ の色を $ c(k,i,j) $ とする。 $ c(0,N/2,N/2)=1 $ とする。 また、パラメータ $ p=\mathrm{rand}(2,5) $ を生成する。 以下の処理を繰り返す。ある操作によって更新されたレイヤーの非透明なピクセル数が初めて $ N^2/2 $ 以上となった時点で処理を終了し、そのレイヤーの画像、すなわち各ピクセルの色を $ g_{i,j} $ とする。 各反復では、 $ p/10 $ の確率で paint 操作を、 $ 1-p/10 $ の確率で copy 操作を行う。 **paint 操作:** $ k=\mathrm{rand}(0,K'-1) $ によりレイヤーを選択する。 レイヤー $ k $ が透明な場合は $ (i,j)=(N/2,N/2) $ を、そうでない場合は $ (i,j)=(\mathrm{rand}(0,N-1),\mathrm{rand}(0,N-1)) $ を生成する。 すべてのレイヤーにおける色 $ x $ のピクセル数を $ \mathrm{num}(x) $ とする。 $ \mathrm{num}(x) $ が最小となる色 $ x\in\{1,\cdots,C\} $ の中から、一様ランダムに 1 つ選ぶ。 仮に $ c(k,i,j)=x $ と更新し、レイヤー $ k $ の非透明なピクセルが連結であるかを判定する。 連結でない場合はこの試行を破棄し、 $ (i,j) $ の生成からやり直す。 **copy 操作:** コピー先のレイヤー $ k=\mathrm{rand}(0,K'-1) $ を生成する。 非透明なピクセルを持つレイヤー $ h $ を一様ランダムに選択する。 回転回数 $ r=\mathrm{rand}(0,3) $ を生成する。 レイヤー $ h $ を時計回りに 90 度回転する操作を $ r $ 回行って得られるレイヤーを $ h' $ とする。 $ h' $ の非透明なピクセルのうち、 $ i $ 座標の最小値を $ i_0 $ 、最大値を $ i_1 $ 、 $ j $ 座標の最小値を $ j_0 $ 、最大値を $ j_1 $ とする。 シフト量 $ (\Delta i,\Delta j) $ を $ (\mathrm{rand}(-i_0,N-1-i_1),\mathrm{rand}(-j_0,N-1-j_1)) $ により生成する。 操作 $ \mathrm{copy}(k,h,r,\Delta i,\Delta j) $ を仮に適用し、レイヤー $ k $ の非透明なピクセルが連結であるかを判定する。 連結でない場合はこの試行を破棄し、 $ k $ の選択はそのままで、レイヤー $ h $ の選択からやり直す。 ### B 問題について **B 問題の入力は、各チームが自ら作成して提出によって差し替えることができる。** 作成した入力の提出方法については、C 問題のページを参照せよ。 各チームは4つの入力を提出する。提出された4つの入力のうち、ランダムに1件が全チームに公開され、残りの3件がジャッジに使用される。 **入力の公開およびジャッジの開始は、コンテスト開始から2時間20分後程度を目安としている。** 準備が整い次第、全体アナウンスを行う。 入力を提出しなかったチームの分は、前述の A 問題の入力生成方法に従ってランダムに生成された4つの入力が代わりに用いられる。 なお、自分のチームが提出した入力は既知であるため、対応する出力を事前に計算して解答プログラムに埋め込むことも許される。 C 問題への提出は何度でも行うことができる。ただし、各チームについて、コンテスト開始から **120 分未満** に提出されたもので ACを獲得した提出のうち、最後の1件のみが使用される。 ### ツール(入力ジェネレータ・スコア計算) - [ローカル版](https://img.atcoder.jp/masters2026-final/aCVc95hT.zip): 使用するには[Rust言語](https://www.rust-lang.org/ja)のコンパイル環境をご用意下さい。 - [Windows用のコンパイル済みバイナリ](https://img.atcoder.jp/masters2026-final/aCVc95hT_windows.zip): Rust言語の環境構築が面倒な方は代わりにこちらをご利用下さい。 コンテスト期間中に、チーム外とのビジュアライズ結果の共有や解法・考察に関する言及は禁止されています。ご注意下さい。