D - Tiling

キーワード

解説

問題 (opens in a new tab)

使用するタイルとその回転の有無を bit 全探索する。

マスと面積が一致するようなタイルと順序を全探索し、左上から埋めていくと、どこかで全てを埋めることができるようなものが存在する。

タイルを置くごとに、そのタイルを重ならないように置くことができるかどうかチェックするのではなく、左上に置くことができるかどうかのみをチェックし、最後に全てのマスが埋まっているかどうかをチェックする。

最悪計算量は $\text{O}(2^N \cdot 2^N \cdot N! \cdot N \cdot HW) \approx \text{O}(10^9)$ となるが、実際はもっと早く終わる。(多分...)

解説は $\text{O}(2^N \cdot N! \cdot HW)$ だがよくわからん。

提出コード

func main() {
	var n, h, w int
	scanIntVariables(&n, &h, &w)
	AB := make([][]int, n)
	for i := 0; i < n; i++ {
		AB[i] = readInts()
	}
	s := 0
	for i := 0; i < n; i++ {
		s += AB[i][0] * AB[i][1]
	}
	if s < h*w {
		writeLine("No")
		return
	}
 
	// 使用するタイルをbit全探索
	for b := 1; b < (1 << n); b++ {
		uses := make([][]int, 0, n) // 使用するタイル
 
		// 面積が一致しな場合はスキップ
		s := 0
		for i := 0; i < n; i++ {
			if (b>>i)&1 == 1 {
				uses = append(uses, AB[i])
				s += AB[i][0] * AB[i][1]
			}
		}
		if s != h*w {
			continue
		}
 
		m := len(uses)
		// 使用するタイルの回転の有無をbit全探索
		for b := 0; b < (1 << m); b++ {
			arr := []int{}
			for i := 0; i < m; i++ {
				arr = append(arr, i)
			}
			// 使用するタイルの順序を全探索
			for {
				M := make([][]bool, h)
				for i := 0; i < h; i++ {
					M[i] = make([]bool, w)
				}
				for i := 0; i < m; i++ {
					t := []int{uses[arr[i]][0], uses[arr[i]][1]}
					if (b>>i)&1 == 1 {
						t = []int{t[1], t[0]} // 転置
					}
					ok := false // (j,k)を左上にすることができるか
					for j := 0; j <= h-t[0]; j++ {
						if ok {
							break
						}
						for k := 0; k <= w-t[1]; k++ {
							if M[j][k] {
								continue
							}
							ok = true
							for l := j; l < j+t[0]; l++ {
								for m := k; m < k+t[1]; m++ {
									M[l][m] = true
								}
							}
							break
						}
					}
				}
 
				if check(M) {
					writeLine("Yes")
					return
				}
 
				if !nextPermutation(arr, func(a, b int) int { return b - a }) {
					break
				}
			}
		}
	}
	writeLine("No")
}
 
func check(M [][]bool) bool {
	for i := 0; i < len(M); i++ {
		for j := 0; j < len(M[i]); j++ {
			if !M[i][j] {
				return false
			}
		}
	}
	return true
}

C - One Time Swap 349