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)

ファイルを添付する

filecarpets.out.txt 568件 [詳細] filecarpets.txt 581件 [詳細] filee.kikuchi.cpp 658件 [詳細]
[添付ファイル一覧] [全ページの添付ファイル一覧]
アップロード可能最大ファイルサイズは 10,240KB です。

管理者パスワード:

添付ファイル: filecarpets.out.txt 568件 [詳細] filecarpets.txt 581件 [詳細] filee.kikuchi.cpp 658件 [詳細]

Last-modified: 2009-11-06 (金) 13:26:46 (3153d)