マス目(長方形)の性質

Math Algorithm

寝起きにぼけっと考えていた．

  • 縦 | 横 に切ると，再び長方形になる．
    • dp[y][x]や，dp[line][y]といったタイプの動的計画法に帰着しやすい．
  • 面積=縦×横．
  • 各マスに数字を書いたとき，その部分長方形の総和を，下準備O(W*H)の後でO(1)で求められる．
  • さらに，部分長方形の総和を求める，どこかのマスに変更を加える，という2種類の操作を，下準備O(W*H)の後でどちらも対数(の2乗)オーダーで実現できる．(BinaryIndexedTree)
  • マス目をグラフと見なすと：
    • 2部グラフである．
      • しかも左側の頂点集合と右側の頂点集合では個数は高々1しか違わない．
    • 各点の次数は高々4である．
    • カットがとても特徴的である(その平面的双対グラフが端から端まで横断するパスに対応する)
      • そのため，盤の端をSRC，他の盤の端をDSTとする最小カットは，最大流ではなくダイクストラによって解ける…かも．
    • 平面的双対グラフも再び長方形っぽくなる．(ただし端は除く)
    • 2点間の最短路の距離は，2点間のマンハッタン距離に相当．


ほかにももっと色々ありそうだけど，ぱっと思いつくのはこのへんだろうか．
ほかにもあったら教えてください．