Skip to content

estieプログラミングコンテスト2022(AtCoderHeuristic Contest 014)

問題概要

  • N * Nの方眼紙上に格子点があり、M個の格子点には印がついている
  • 以下の操作を可能な限り繰り返すことで印と長方形を描いていく
    • まだ印のついていない格子点p_1と、印がついている格子点p_2,p_3,p_4が以下の条件をすべて満たすものを選ぶ
      • この4点を順番に結ぶと、軸に平行、または、45度傾いた長方形になる
      • 長方形の外周上にはこの4点以外の印のついた格子点がない
      • 長方形の外周はすでに書かれた他の長方形と辺を共有しない(点で交わるのはOK)
    • 条件を満たす格子点に印をし、長方形を方眼紙に描く
  • 格子点には重みがあり、印がついた格子点の重みの和に基づく得点が得られる
  • できるだけ高得点が得られるようにゲームをプレイせよ(操作列を求めよ)

時間

  • 340時間

個人的メモ

  • できるだけ中心から遠く＆多くの格子点に印をつける、のが難しい問題
  • 方眼紙の部分領域の破壊＆再構築＋小さい長方形を優先する焼きなましが強かった模様
    • 操作列を求める問題だが、盤面の局所性を活かせるかが鍵だった

問題固有の性質

  • 小さい長方形の方を優先したほうが良い
    • 大きい長方形は遠くに行けるが、後々邪魔になりやすい
    • 良い解(高密度な解)の場合は1x1長方形を多用する
  • 各頂点について、その頂点が接する長方形の数は最大4つまで
    • 8方向あり、長方形で2方向消費するため
    • 長方形の形や周囲の長方形の状況で、4つにできない場合が出る
    • できるだけ4つの長方形に接するようにしたほうが良い
  • パリティ的なのが揃うと外に広げられる(ピラミッド、雪崩)

盤面の局所性

  • 盤面に注目すると、ある部分領域の格子点の印を削除したい場合、それに依存している格子点＆長方形を連鎖的に削除することで、部分的に作り直すことが可能
  • 実際は、「上の方はうまくできてても下の方はうまくいっていない」ような場合に、下の方だけやり直すなどが可能
    • 自分は、採用してたアプローチのためか、文脈がかなり強いと思い、ある長方形を削除したらそれ以降においたすべての長方形が削除されうると思ってしまっていたので部分破壊は難しいのでは？と思って考慮から除いてしまっていた、、、

長方形または部分領域内の印のある格子点の削除＆再構築

  • 領域の部分破壊＆再構築を近傍とすることで、焼きなませる
    • 今回の場合は、矩形領域内でなくても、ある格子点を選ぶと連鎖的に関連する格子点、長方形がでてくるので、それでもある程度の範囲が消える
  • https://twitter.com/ks4m/status/1578048974078251008

操作の依存関係をグラフとみなす

盤面の状態の持ち方

  • 印の有無、その格子点の8方向について長方形の辺を持つか否か
    • bool[N][N]、bool[N][N][8]
  • 印の有無、辺の有無(4方向)
  • 印の有無、対応する辺の終了位置

合法手の列挙、高速化

  • 盤面の合法手の列挙は、単純にやるとかなり時間がかかってしまう
    • 3点選んで長方形になるか＋外周に他の点や辺がないかチェック、などだと結構重い
  • ここらへんはうまく高速化する
    • p_3に対応する印のある格子点を選んで、長方形の角度を決めれば8パターンだけになる
      • 途中に印のある格子点や他の長方形の辺がない必要があるため、p_2やp_4はその方向で一番最初に見つかった印のある格子点になる
    • p_1を選んで同じようにする方法もあるが、外周チェックをO(N)でやると、印がない格子点のほうが多いので、p_3を中心に探索したほうが無駄が減る
      • ただ、自分は、外周チェックを更新O(N)確認O(1)にしていたので、p_1でやっていたが、p_3に変更してもあんまり変わらないと思う
  • bit演算を使うと、Nは61程度なので、uint64_tを1つで1列分持てて、高速に列挙や探索が可能

手の評価値

  • 手に優先度をつけることで、より良い操作列を選びやすくする
  • 問題の性質から、「小さい長方形のほうがよい」「各頂点についてできるだけ接する長方形数が多いほうがよい」などを取り入れる
    • 1x1を優先、各頂点について180度反対方向の辺が使われているか、他の辺上に印をつけるか
    • 固定パターン(良い部分形)にマッチしているか
    • 各頂点の次数の和
    • 長方形の大きさ
    • 頂点の重み
    • など

手をランダムに選ぶ方法

盤面の評価値、ビームサーチ

  • ゲームの途中の盤面の評価が難しく、「盤面に対する評価値」が使いにくい
    • 単純なスコアでは、先に外側に置こうとして大きな長方形を使いがちになってしまう
    • 最後の方まで手を進めて見ないと良し悪しが決まらない
  • そのため、ビームサーチやゲーム木探索でうまくスコアを取るのが難しかった
  • とはいえ、ビームサーチで60M超えはできるらしい

その他

解説

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