Skip to content

THIRDプログラミングコンテスト2024(AHC039)

問題概要

  • 二次元平面上(それぞれ10^5以下)に、N(=5000)匹のサバとN匹のイワシがいる
  • 以下の条件を満たす多角形を構築し、その内部に含まれるサバの総数からイワシの総数を引いた値を最大化せよ
    • 多角形の頂点数 <= 1000
    • 多角形の辺の長さの合計 <= 4 * 10^5
    • 各辺はx軸またはy軸に平行
    • 多角形は自己交差しない

時間

  • 240 時間

個人的メモ

問題固有の性質

  • 二次元平面のサイズが結構大きい
  • 魚は、結構、塊(クラスタ)になっている
  • 多角形の条件の「周の長さが 4 * 10^5以下」という条件は、結構厳しい
    • 「E」や「凹」みたいな形にしようとすると周の長さが結構長くなってしまいがち

幾何的アプローチ

  • 結構実装しんどい気がするけど、こちらのアプローチで上位の人も結構いた模様
  • ぱっと見だと、魚が塊で存在しているので、それらを囲った長方形を見つけて、それらを細い道(余計なイワシを拾わないようにしたい)みたいなのでつなぐ感じが考えられる
  • しかし、長方形の集合をうまく見つけるのも、それらをつなぐ実装も結構大変で、しかも、周の長さが長くなりがちで制約を満たすように制限する必要があるなど、4時間では結構厳しいかも
    • 細い道/橋みたいなのは辺の長さを使う割にスコアが得られないので、あまり長いのは作りたくない
    • 平面のサイズが大きいことや、実装によっては重なり/自己交差に気をつける必要があったり、など

良い長方形を見つける

  • 辺の長さの制約は、平面いっぱいの長方形でも満たせるので、任意の長方形はすべて条件を満たせる
  • 長方形を決め打ちした場合、その時のスコアは、各魚(=10^4)が長方形内部にいるかどうかで判定できる
  • ランダムに長方形を生成して一番いいスコアをものを採用する、などができる
    • 2秒でも数万回ぐらいは回せる
  • (k-meansとかして各クラスタを囲む最小長方形、とかもありかも？)

長方形を加える・削る、辺を動かす

  • 多角形に対して、その形を変形させる局所探索も考えられる
    • (辺に隣接するような)長方形を加える、長方形を削る
    • 多角形の辺を動かす

塊を長方形で囲って連結

  • 長方形の候補をたくさん作って、貪欲によいものを連結していく
    • とはいえ、長方形内のサバとイワシの数を求めるのはそんなに

多角形を生成

  • 出力形式で多角形を作ってスコアを計算する、のを繰り返すのも考えられる
    • ランダム生成や、頂点集合を局所探索、など
  • 多角形(自己交差なし)の内外判定は、頂点から軸に平行な半直線を伸ばして交差する辺の数の偶奇で判断できる(Crossing Number Algorithm)
    • 角度を使うWinding Number Algorithmというのもあるっぽい
  • 辺の長さや頂点数に気をつけつつ、自己交差もしないように多角形を作るのは結構たいへんかも

グリッドアプローチ

  • 平面を大雑把にグリッドに分割して、マスを選ぶ/選ばないで考えると、マスを選んだときのスコアが前計算できたりなど、扱いやすくなる
  • 基本は、連結なマスの集合(穴なし)を多角形にすることを考える

分割の仕方

  • 基本は、x軸y軸を等間隔に分割したもの
  • x軸とy軸で分割数を変える
  • 乱択で決める
  • 分割位置を等間隔じゃなくする(分割位置変更を近傍に局所探索)
  • など

分割サイズ

  • 基本的には、可能な限り細かく分割したほうが調整しやすそうに見えるが、必要な探索量も増えてしまって最適解にたどりにくくなってしまう可能性がある
    • 荒く分割する場合、サバもイワシも含まれてしまってスコアが伸ばしにくい
    • 細かく分割する場合、探索空間が大きくなってしまう(遠くのマスとの連結になるまでに探索量を必要としてしまう、局所解に陥りやすい)

外周をたどる方法(出力の生成方法)

  • グリッド上の連結なマスの集合(穴なし)が与えられた時、その外周を順番にたどる辺の集合を求めるのは、主に2つのアプローチが考えられる
  • 右手法(左手法)
    • 進行方向の右側に壁(連結成分)が来るように辿る
      • 角からスタートして、進行方向の左、まっすぐ、右の順で壁(選択したマス)があるかチェックしながらたどるとかすればよい
  • 外周の辺を列挙して連結する

評価関数

  • 基本は生のスコアをそのままで十分な模様
  • スコア(サバの総数 - イワシの総数)
    • スコアに係数をかけたもの
      • イワシの総数の方の係数を大きくすると、イワシを含むような長方形を避けるようにできる
  • 網の長さ
    • 短いほうがよい(探索しにくくなってしまう可能性もある)
    • 制限超えてなければよい
    • 超えてる分をペナルティ(invalidを許容)

貪欲

  • 各マスについてスコアがわかるので、スコアが大きいマスから選ぶような貪欲が考えられる
    • 隣接マスを優先度付きキューに入れて拡張
      • 周の長さやスコアを見て一番良いタイミングのものを返す
    • プリム法ベースシュタイナー木的に連結

区間DP

  • y軸の小さい方から、x軸のどの区間を選ぶか？と周の長さ、その時のスコアで考えるDP
    • 片方の方向だけしかへこませられない
  • 「広がる->狭くなる」という形に制限してDP

局所探索

  • 連結を保ってマスの連結成分を変形させる局所探索ができる
  • 連結成分変形
    • あるマスをOFFにした場合、連結成分が別れてしまうか(関節点か)どうかは、まともに連結成分計算すると重いが、3x3関節点高速化など近似だが高速な方法がある
    • あるマスをONにしたときに連結成分の塊の内側に「穴」ができてしまうのを避けたい場合、OFFマスに対して上記の関節点判定をしてあげれば、穴ができないようにできる
      • (ON->OFFはONマスをちぎらないか、OFF->ONはOFFをちぎらないかをチェックする)
      • (穴ありでやって実装間に合わずに最終的に穴を無視して囲っても、その分のマイナスが増えるだけではある)
  • 近傍
    • 連結成分変形操作
      • マスのON/OFFを変える
        • 1マス/複数マス
  • 初期解
    • 全マスを選んだ状態からスタートした場合、周の長さが最大で、「凹」のような形にしたくても制限を超えてしまうため、変形しにくい問題がある模様
    • 1マススタートや、魚が存在しない外周マスは無視するとか、ある程度貪欲解とかからスタートとか、がよい？
  • 分割サイズを段階的に細分化
    • 最上位は、比較的少ないグリッドの分割から初めて、段階的に細かいグリッド(分割幅を½するなど)にしていくアプローチをしていた模様
    • マスの大きさが大きい場合、おおよその形は見つけられるが、細かいところを見ると改善の余地があり、グリッドを細かくすることで、改善できる
      • 最初からマスの大きさを小さくしてしまうと、いい形を見つけるまで探索量が必要になって間に合わないなどある
      • サイズ調整など結構重要かも

その他

Wavelet Matrixで2次元クエリ処理

魚が存在する範囲

  • 入力的には各魚は0<=x,y<=10^5だが、実際は魚が存在する範囲はもうちょっと小さい
    • 端の方の領域で魚が存在しないところとかは伸ばすだけ無駄な可能性がある

塊に穴を作りたい場合

  • 一応、辺の長さが足りるなら、頂点や辺を増やせば内側に穴を作ることはできる
    • 以下みたいに穴までと穴の部分を囲む頂点や辺を用意する
+------------+
|            |
|            |
+--------+   |
+---+    |   | ← ちょっとだけずらす
|   |    |   |
|   +----+   |
|            |
|            |
+------------+

お絵かき

解説

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