ACM洋菓子店

- 切った後の長方形の数 = 切り分けた線分の数 + 1 なので、線分の数を数えることにする。
- 線分は周囲に3つのブロックがある格子点を端点に持っている。
  - 周囲に3つのブロックがある格子点を凹点と呼ぶことにする。
  - 全てのピースが長方形であるということは凹点が存在しないということ。
  - 線分の数は凹点の数でおさえられる。
- 凹点同士を結ぶ線分が多ければ多いほどよい。
- 線分の数 = 凹点の数 - 凹点同士を結ぶ線分の数
  - 凹点同士を結ぶ線分を1本引くと2つの凹点を潰すことが出来るため
- 凹点同士を結ぶ線分を2本交わるように引いても4つの凹点を潰したことにはならない。
  - 1本目の線分を引いた時点で多角形が切り分けられ、2本目は凹点同士を結ぶ線分にならない。
- 線分の数 = 凹点の数 - 交わらない凹点同士を結ぶ線分の数
- 交わらない凹点同士を結ぶ線分の集合を求めたい
  - 最大独立集合（最大安定集合）を求める。
  - 交わる線分は必ず水平方向と垂直方向の1本ずつ（同じ点で3本以上の線分が交わることはない）
  - 二部グラフ上の最大独立集合を求める
  - これは |全ての辺の数| - |二部マッチングの数| となる
  - 二部マッチングの数は最大流問題として解ける。
- 線分の数 = 凹点の数 - (|全ての凹点同士を結ぶ線分の数| - |交わる凹点同士を結ぶ線分のマッチング数|)