JOI '13 春合宿２：2 - マスコットの片付け

問題
解法
解答

問題

http://imoz.jp/data/joi/2013-sp-d2-mascots.pdf

解法

まず，長方形になる回数を最大化する方法を考えると，最初に与えられた状態をまず出来るだけ小さい長方形にし，４辺それぞれを拡大していくのが最適になる．

最初に与えられた状態から長方形にするまでの通り数は，(目標の長方形の空いているマスの数)! になる．次に，この長方形を１辺ずつ拡大していくことをする．ここで，DP を考えるが「上・下・左・右方向にそれぞれ何マス拡大したか？」という情報を持つ DP をすると計算量が O(R^2 * C^2) になってしまうので，「上下・左右方向にそれぞれ何マス拡大したか？」という情報だけを持つ DP をすれば O(RC) に抑えられる．最後に，上下方向・左右方向にまとめてしまったので，後から上・下・左・右と区別をつける必要がある．これは，C( (上下方向の移動量), (上方向の移動量) ) * C( (左右方向の移動量), (左方向の移動量) ) を計算すれば可能．

これら３つの要素を掛け合わせたものが答えになる．O(RC)．