Skip to content

Instantly share code, notes, and snippets.

@kenkoooo
Created November 21, 2019 11:34
Show Gist options
  • Save kenkoooo/65d83cee867d7455ff380098e7cf5297 to your computer and use it in GitHub Desktop.
Save kenkoooo/65d83cee867d7455ff380098e7cf5297 to your computer and use it in GitHub Desktop.
- 切った後の長方形の数 = 切り分けた線分の数 + 1 なので、線分の数を数えることにする。
- 線分は周囲に3つのブロックがある格子点を端点に持っている。
- 周囲に3つのブロックがある格子点を凹点と呼ぶことにする。
- 全てのピースが長方形であるということは凹点が存在しないということ。
- 線分の数は凹点の数でおさえられる。
- 凹点同士を結ぶ線分が多ければ多いほどよい。
- 線分の数 = 凹点の数 - 凹点同士を結ぶ線分の数
- 凹点同士を結ぶ線分を1本引くと2つの凹点を潰すことが出来るため
- 凹点同士を結ぶ線分を2本交わるように引いても4つの凹点を潰したことにはならない。
- 1本目の線分を引いた時点で多角形が切り分けられ、2本目は凹点同士を結ぶ線分にならない。
- 線分の数 = 凹点の数 - 交わらない凹点同士を結ぶ線分の数
- 交わらない凹点同士を結ぶ線分の集合を求めたい
- 最大独立集合(最大安定集合)を求める。
- 交わる線分は必ず水平方向と垂直方向の1本ずつ(同じ点で3本以上の線分が交わることはない)
- 二部グラフ上の最大独立集合を求める
- これは |全ての辺の数| - |二部マッチングの数| となる
- 二部マッチングの数は最大流問題として解ける。
- 線分の数 = 凹点の数 - (|全ての凹点同士を結ぶ線分の数| - |交わる凹点同士を結ぶ線分のマッチング数|)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment