Skip to content

AtCoder Heuristic Contest 032

問題概要

  • N * N (N=9)マスの盤面があり、各マスにはあらかじめ整数が設定されている
  • 3 * 3マスの各マスに整数が設定されているスタンプがM(=20)個あり、はみ出さないようにK(=81)回好きなスタンプを押すことで、その盤面の各マスにスタンプの整数分加算することができる
  • 最終的な盤面のマスの値を997244353で割った余りの総和を最大化せよ

時間

  • 4 時間

個人的メモ

問題固有の性質

  • N,M,Kは全ケースで固定で、あまり大きくない
    • 状態や遷移数が小さく抑えられる
  • 1マスあたりの調整に使える回数は、マスが81箇所あるのでマス当たりだと81/81=1回だが、押せる箇所が7*7=49箇所しかないので、押せる箇所当たりでは81/49=1.653回
  • スタンプを押す順番は入れ替えても最終状態は変化しない

マスを確定させていく貪欲、ビーム

  • 左上(0,0)のマスを考えると、そのマスは(0,0)にスタンプを押すしかなく、そこを確定させると、その下と右が角になり、そこについても同様にそこにスタンプを押すしかなくなる
  • ここから、順番にマスを確定していくことが考えられる
  • 今回、1マスあたり1〜2回はスタンプを押す余地があるので、各確定したいマスに注目して、値が最大になるようにスタンプを選ぶ
    • 左上6x6マスについては、1マスについて考えられるが、右端と下端、右下3x3は調整できないので、1x3、3x1、3x3のマスをまとめて確定すると考える
    • 「そのターン以降で調整できなくなるマス」を対象として考えるとよいよう

合成スタンプの列挙

  • 同じ場所に複数のスタンプを押す場合、それらのスタンプを全部合成(各マスの総和)したスタンプを考え、それを1回押すのは同じ
  • また、押す順番は関係ないので、M個あるスタンプのうち、K回どれかを選ぶ組み合わせの数は、重複組合せH(M,K)回程度
    • (さらに無駄に「同じスタンプは重複して使わない」とか入れてしまうと、C(M,K)ぐらいしか用意できない・・・)
    • 押す順番を区別するとM^Kになってしまうが、H(M,K)はそんなに大きくない
    • K=9程度でも10^7個いかない程度
  • 合成スタンプは、順番に「前に選んだインデクス以上しか選べない」ように制約をいれてDFSなどすれば列挙できる

複数マスを同時に確定させる場合の問題

  • 「1マスを1回以下のスタンプで揃える」ではなく「3マスを3回以下のスタンプで揃える」とか「9マスを9回以下のスタンプで揃える」かなどが考えられる
    • 右端・下端、右下の部分はこれになっている
    • 左上6x6の部分についても複数マスを同時に確定させるバリエーションは考えられる
      • 盤面全体を3x3マスが9個あると考える、とか
  • 複数のスタンプを同じスタンプ位置で適用する場合、その組み合わせは上の合成スタンプと同じでH(M,K)種類程度しかない
    • この中にうまく高スコアになる組み合わせが含まれていて欲しいが、結構少ない
    • (高スコアが出すのに必要な種類数の見積もりは解説放送)
  • しかし、「1マスを1回以下のスタンプで揃える」場合、他の位置の別のスタンプとの組み合わせになるため、そのマスに対して適用できる和の組み合わせの数はかなり多くなる
  • そのため、同じところで複数回スタンプを適用するよりも分散してスタンプしたほうが調整しやすい

マスを辿る順番

  • マスを辿る順番によってスコアに違いがでる
    • 複数マスの確定が連続すると調整しにくいとか、未確定マスの状態が変わるので古い状態に依存してる部分は、後になると多様性がなくなっていってしまう恐れとか、あるっぽい
  • 左上6x6を先に処理し、右端と下端を処理、右下3x3を処理
    • 「右端を処理してから下端」ではなく、「右端と下端を交互に処理する」などすると、右下3x3の多様性ができやすいかも
  • 「左から右」を上から下に繰り返す(行ずつ処理)
  • 左から右、右から左、を交互に繰り返す(ジグザグ型)
  • 中心にむかってぐるぐる回るように辿る
    • 外側から埋める
  • 横方向、縦方向を交互に繰り返す
  • いくつかの盤面走査パターンを試す(盤面の上下左右反転・回転したものについても考える)

各マスで何回までスタンプを押すか

  • あらかじめ決め打ちで、「左上6x6は1回まで、右端下端は3回まで、右下は9回まで」などとすると制限回数の81回以下で解は得られる
  • しかし、押さなかったマスがあった場合、次以降でその分を使うことでよりよい解が得られる可能性がある
  • 「そこまでのターン数を超えない回数までは押すのを許す」とか、「各ターンでの最大スタンプ可能数を決めておく」など

ビームの種類

  • 「確定マス」ベース
    • 確定マスをターンとする
    • 残り操作回数が状態に入る
  • 「残り操作回数」ベース
    • 残り操作回数をターンとする
    • 確定したマスが状態に入る

評価関数/ペナルティ

  • 確定スコア
    • 確定したマスについては、スコアも決まるので、それを評価値とする
  • 残り操作回数
    • (解説放送)
    • 操作回数がいい感じに多いほうがよい、最後に残らないほうがよい
  • 1手当たりのペナルティ
  • 未確定マスのスコア

高速化

その他

押すスタンプ集合を焼きなまし

  • スタンプ(種類と位置)を状態として焼きなましするアプローチも考えられる(初手で試してみた人は多かった模様)
    • 押す順番は関係ないので集合で考えられ、スタンプは7*7*20=980通り程度で、K=81個までなので結構小さい
    • また、スタンプで3x3しか変化しないので局所性が見られ、局所改善アプローチが有効そうに見える
  • しかし、今回は、スタンプの種類数が少ないため、置き換えた場合のスコアの変動が大きくならざるをえず、複数マスを同時に高い値にできるような組み合わせにすることが難しい
  • そのため、適当な近傍(1つのスタンプの追加・削除・置き換え)では、あまり探索空間が滑らかにならず、そこそこのスコアは出るが、今回はそれでは不十分だった
    • (初期解を貪欲解にしたり、大きめの近傍(合成スタンプで扱うとか)にしたりとかすれば改善するかもしれないが)

その他

理論値計算

ビームサーチの各ターンでのスコア分布の可視化

  • (解説放送)
  • 各ターンで、ビーム内がどのようなスコア分布になっているかをプロットするといろいろ知見が得られそう
    • 最大値の推移だけでなく、最大、最小、平均などもプロット

お絵かき

解説

(50位まで&発言を見つけられた方のみ)