2003/Contest/国内予選

Problem E : Square Carpets †

問題概要 †

長方形の部屋の一部の床が傷ついている。傷をごまかすのに必要なカーペットの最小枚数を求める。

• カーペットは正方形。異なる大きさのカーペットが混在してもよい。
• カーペットを重ねて敷いてもよい。ただし折り曲げるのはダメ。
• 傷ついていない床にはカーペットを敷いてはいけない。

解法 †

最終的には全探索となるが、O(2^N)なので前処理で可能性を絞ることが必要。うまく前処理をすれば、探索なしで解が求まることもある。

前処理 †

1. 敷くことが可能なすべてのカーペットの集合を計算する。カーペットの形状を10x10の配列で保持しておけば、手順3が楽になる。
2. 集合の要素のうち、他の要素に包含されるものを取り除く。
3. ある1マスを覆えるカーペットが1枚だけなら、それを敷く。さらに、残りの要素のそれぞれについて、敷いたカーペットと重なる部分を取り除く。
4. できる限り、2と3を繰り返す。

議論・その他 †

• 参考のため、菊地のソースファイルと、e1.txtに対する出力を示した（解の正しさは未検証）。
  Sample Input では、3番目のデータ以外は前処理のみで済んだ。
  3番目のデータの全探索も、前処理で探索数を2^12通りに絞ったので一瞬。
  
• ZJU で菊地さんのプログラムの正しさを確認。出力データをリネーム。 (三廻部; Dec 7, 2005)

ファイルを添付する †

carpets.out.txt

carpets.txt

e.kikuchi.cpp