SRM 241 DIV1 Hard PatternCutting

問題 Editorial

問題

width*heightの長方形の紙がある。
ここから与えられたパターンpatternを何枚か切り取りたい。
パターンは90°刻みで回転してもいいが、反転してはいけない。
最大で何枚切り取れるかを求めよ

• 1 <= width, height <= 6
• 1 <= |pattern|, |pattern[0]| <= 6

解答

左上が紙の半分に収まる切り方を全列挙する。
そこで、もう半分にまたがる所のビットマスクに対してmaxを取る。
次にもう半分を、初期のマスクを上記のまたがるマスクにしてビットDPする。
Editorialや他の解いてる人はもっと簡単な感じの解き方。
1*2以下のものは場合分けし、うまく枝刈りとかする感じだけどわかってない

コード

#include <string>
#include <vector>
#include <algorithm>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
typedef vector<int> vi; typedef long long ll; typedef vector<long long> vl; typedef vector<string> vs;

int halfMax[1<<18];
struct PatternCutting {
	vl masks; vi ws, hs; int pn;
	int w, h, h2, h3;
	int searchHalfAll(ll mask, int y, int x, int num) {
		if(y == h2) {
			halfMax[mask] = max(halfMax[mask], num);
			return 1;
		}
		int ny = x == w-1 ? y+1 : y, nx = x == w-1 ? 0 : x+1;
		int r = 0;
		r += searchHalfAll(mask >> 1, ny, nx, num);
		rep(k, pn) {
			if(ws[k] <= w - x && hs[k] <= h - y && ((mask & masks[k]) == 0)) {
				r += searchHalfAll((mask | masks[k]) >> 1, ny, nx, num+1);
			}
		}
		return r;
	}
	int bitDP(int mask, int y, int x) {
		if(y == h3) {
			return 0;
		}
		int ny = x == w-1 ? y+1 : y, nx = x == w-1 ? 0 : x+1;
		int r = 0;
		r = max(r, bitDP(mask >> 1, ny, nx));
		rep(k, pn) {
			if(ws[k] <= w - x && hs[k] <= h3 - y && ((mask & masks[k]) == 0)) {
				r = max(r, 1 + bitDP((mask | masks[k]) >> 1, ny, nx));
			}
		}
		return r;
	}
	int getMax(int width, int height, vector <string> pattern) {
		w = width, h = height;
		int n = pattern.size(), m = pattern[0].size();
		//回転したパターンを作る。実はこれが結構書けない感じだったので、しっかり覚えて素早く書けよう
		vector<vs> patterns(4);
		patterns[0].assign(n, string(m, '!')); rep(i, n) rep(j, m) patterns[0][i][j] = pattern[i][j];
		patterns[1].assign(m, string(n, '!')); rep(i, n) rep(j, m) patterns[1][j][i] = pattern[n-i-1][j];
		patterns[2].assign(n, string(m, '!')); rep(i, n) rep(j, m) patterns[2][i][j] = pattern[n-i-1][m-j-1];
		patterns[3].assign(m, string(n, '!')); rep(i, n) rep(j, m) patterns[3][j][i] = pattern[i][m-j-1];
		//重複の削除は1*1パターンとかの高速化になる
		sort(all(patterns)); patterns.erase(unique(all(patterns)), patterns.end());
		rep(i, patterns.size()) if(h < patterns[i].size() || w < patterns[i][0].size()) {
			patterns.erase(patterns.begin()+i), i --;
		}
		pn = patterns.size();
		//パターンのビットマスクを作る
		hs.clear(), ws.clear(), masks.clear();
		rep(i, pn) {
			hs.pb(patterns[i].size()), ws.pb(patterns[i][0].size());
			ll mask = 0;
			rep(y, patterns[i].size()) {
				rep(x, patterns[i][y].size()) if(patterns[i][y][x] == 'X') {
					mask |= 1LL << (y * w + x);
				}
			}
			masks.pb(mask);
		}
		//左上が紙の半分に収まる切り方を全列挙する
		h2 = h / 2;
		mset(halfMax, -1);
		searchHalfAll(0, 0, 0, 0);
		//ビットDPを組み合わせる
		int r = 0;
		h3 = h - h2;
		rep(i, 1<<(w*h2)) if(halfMax[i] != -1) {
			r = max(r, halfMax[i] + bitDP(i, 0, 0));
		}
		return r;
	}
};