Skip to content

第三回マスターズ選手権-決勝-

問題概要

  • https://atcoder.jp/contests/masters2026-final
  • https://atcoder.jp/contests/masters2026-final-open
  • 32 * 32のピクセルからなるレイヤーがK枚ある
  • 使用できる色はC色あり、各ピクセルは0なら透明、1〜Cならその色であることを示す
  • 目標画像が与えられるので、レイヤー0にその画像を作ることを目指す
  • 初期状態はすべてのレイヤーで透明で、1回の操作で以下が行える
    • paint(k,i,j,x): レイヤーkの(i,j)の色をxにする(x=0なら透明にする)
    • copy(k,h,r,di,dj): レイヤーhをr回時計回りに90度回転したものをh'として、(di,dj)だけずらしたものをレイヤーkに上書きする
      • k=hであってもよい
      • 範囲外に色を塗るような場合は不正
    • clear(k): レイヤーkのすべてのピクセルを透明にする
  • できるだけ少ない操作回数で目標画像を完成させよ
  • 問題ごとの違い
    • A問題: あらかじめ決められた入力生成方法に従って生成されたものがテストケースになる
    • B問題: 参加者が用意した入力がテストケースになる(開始2時間後から提出可能)
    • C問題: 参加者が用意した入力の提出用(開始2時間まで提出可能)

時間

  • 360 分

個人的メモ

入力生成方法(A問題)

  • paintとcopyを使って連結を維持して大きくしていって、十分大きくなったらそのレイヤーを採用する、ような感じ
  • パラメータによって、比較的似たような色の塊だったり、ノイジーな感じだったりバリエーションがある
  • 生成時に使えるレイヤー数は、Kの2倍までありえるため、そういうケースでは生成方法と同じ手順がわかったとしても再現できない

アプローチ

  • いろんなアプローチが考えられるし、ぱっとよさそうなアプローチも見えないし、大方針を決めたとしても細かいところでも選択肢がたくさんあるので、6時間で詰め切るのはかなり厳しい、、、
  • 入力生成方法が平均40〜50ターンぐらいで作れそうで、100ターン切れるぐらいまでは目指せそうに見えるけど、実際はそんなにいけなかった

目標画像からパターン抽出する系?

  • 入力生成方法的にも、複数レイヤーでcopyしあって、パターンの組み合わせて作られているため、似たようなパターンが見られるので、共通のそういうパターンを見つける方針が考えられる
    • 画像処理っぽい感じもあり、マッチングや特徴量などそっちの知見からも攻められそう
    • 入力生成の逆手順とか見つけられないか、とか
  • ただ、このパターンを見つける方針は、うまく見つけられればターン数は少なくできそうだが、おそらくかなり厳しい方針だったっぽい
  • https://x.com/Shun___PI/status/2045498778426524125

スタンプ解法

  • おそらく、小さめのスタンプを作ってそれをレイヤー0に何度か押す感じがコスパよいアプローチだったっぽい
  • とはいえ、探索方法、選び方、レイヤーの使い方など、かなりバリエーションがある
必要ターン数
  • ざっくりと、「スタンプを作るのに必要なターン数＋スタンプを押す回数＋不一致ピクセルを修正する回数」ぐらいと考えられる
    • 小さめのスタンプは作るのにターン数が少なくてすむので、押す回数が多少増えてもそこまで変わらない可能性がある
スタンプの形状
  • 1*nサイズ(行単位列単位で考える)・小サイズ・長方形などに限定して考えるとかは考えやすかったかも
  • ただ、局所探索などでスタンプ形状を探索したり、貪欲に目標画像を参考に広げるとかしてるチームが多いかも？
スタンプを押す位置・向き
  • ランダムに選ぶか、探索する、貪欲に決めるか、あたりがありそう
    • A問題とかは色数が少ないケースも多いので、比較的ランダムに選んでも不一致がが少なくなる位置・向きが多そうでなんとかなっている可能性がありそう
    • 色数が多くノイジーなケースや、B問題などだと、ちゃんと探さないと不一致がが少なくなる位置・向きが見つけられない可能性がありそう
  • スタンプは、押すと上書きになるので、押す順番を逆順に考えると、確定したピクセルを変えずにスタンプを押す的なことを考えることもでき、不一致が少なくなる位置・向きを貪欲に選んでいくなどもできる
(自チームのアプローチのメモ)
  • 基本的に、スタンプ形状も押し方、順番も全部まとめて焼きなまし
    • 近傍もかなり単純な「形状の1ピクセル変更、押すところの追加/削除/変更、押す順番のswap」ぐらい
  • 素直に実装するとそこまでスコアは出ないので判断が難しいところだけど、以下の工夫を入れたらそこそこ効いてそうで、改善策も見えやすいのでこちらの方法を検討
    • スタンプ形状は既存のピクセルの近傍ピクセルを選ぶようにしてできるだけ塊になるようにする
    • レイヤー1を作るためにレイヤー2が使えるときは、若干時間を使って同様に局所探索でスタンプを作って押す(階層化)
    • 最後の不一致ピクセルで1*2マスがまとめて塗れるときは塗る
    • 近傍の採用確率をハイパラ探索
  • 逆に、以下は試したけどミスったのかうまくいかず捨ててしまったもの(他チームはやれてそうなので実装ミスってた可能性が高い・・・)
    • スタンプ押す位置を貪欲に選ぶ
    • 目標画像から部分集合を拾ってくる近傍
    • 階層全部をまとめて焼きなまし
    • 複数レイヤーが使える時は、異なるスタンプを作る
    • パターン生成の仕方を変える
    • 高速化
    • など
  • 延長戦ではA問題は500M点までは伸ばせたとのこと
  • おそらく色数が少ないケースでターン数が少なくできててそこで稼いでいるかも
    • 全部探索任せなので、スタンプ形状やスタンプを押す位置がうまく見つけられない色数が多いノイジーなケースなどだととあまりうまくいかず、そこをちゃんと探索や貪欲で決められていた他チームと差がついてしまっていたかも
    • 初期解などを工夫するなどが効いてそうだったけど、かなりスタンプ形状の近傍が限定的だったので局所解から抜け出せなかった可能性も高い

C問題(テストケース提出)

  • 得点の式は 10^6 ( 1 + log_2 U / T ) の形で、Uは全部埋まっているケースが最大でU=1024にでき、他チームとのターン数差が大きいほど加点が大きい
    • たとえば、他チームが300ターン(2.7M点/ケース)かかるところを20ターン(6.7M点/ケース)ぐらいでできたりすると、3ケース分で12M点ぐらい差をつけられる可能性があった
      • 実際、最後の解説で紹介されていたけど、10M点差ぐらいつけられていたチームがいたっぽい？
  • コンテスト中、どういうケース強いか判断つかなかったけど、結局少ターンの解を見つけるのが難しかったので、入力生成方法(K固定)で生成して埋め込むでも十分だったかも
  • C問題で提出したケースは、コードに目標画像と手順を埋め込んでおいて、画像をチェックし、該当する場合はその手順を返せば良い
  • https://x.com/gojira_kyopro/status/2045446205484982554

その他

自己copy

  • copy操作は同じレイヤーが指定できるので、ピクセル数を1,2,4,8,16,...と倍々にすることができる

2名以上が参加している所属機関一覧

出展企業紹介

お絵かき

解説

(発言を見つけられた方のみ)