SRM 262 DIV1 Hard MagicBoxes

問題 Editorial フォーラム

問題

x*yのグリッドに1〜nのサイズの正方形を互いに重ならないように置きたい。最大のnを求めよ
1 <= x, y <= 30

解答

枝刈り全探索。
まず、(sum (map (^2) [1..14]) > 30 * 30)なのでnは13以下。
探索を少なくするために、大きいものから置いていく。
枝刈りとして、「『左右に壁か他の正方形が接している』というところにだけ置く」という未証明かつ謎の、まあそれっぽいけど…な枝刈りができる。もしこれに「上下に壁がある」も含めると計算時間が数倍になってTLEする。
他にも様々な枝刈りが考えられる。また様々な考察がフォーラムに見られる。
30*15程度の解を事前に計算しておいて埋め込むこともできる。フォーラムによると、何の枝刈り・最適化も無しのコードでもある程度の時間で事前計算できるようだ。

コメント

枝刈り謎。謎すぎる。もしかしたらシステムテストにある以外のケースで間違うかもしれない。
なんとなくのそれっぽい戦略ではあるけれど、証明できる気がしない。証明できなくても、これでいいと思える気もしない。
うーん…とりあえず埋め込みはするべきだろうな

コード

#include <string>
#include <vector>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;

unsigned b[31];
struct MagicBoxes {
	int w, h;
	bool search(int n) {
		if(n == 1) {
			rep(y, h) if(b[y] != (1U << w) - 1) return true;
		} else rer(y, 0, h-n) rer(x, 0, w-n) {
			unsigned mask = ((1U << n) - 1) << x;
			unsigned mask2 = (x == 0 ? 0 : 1U << (x-1)) | (x+n == h ? 0 : 1U << (x+n));
			bool t = false;
			t |= x == 0 || x+n == w;
			reu(i, y, y+n) {
				if(b[i] & mask) {
					while(b[i] & mask) mask <<= 1, ++ x;
					-- x;
					goto next;
				}
				t |= b[i] & mask2;
			}
			if(t) {
				reu(i, y, y+n) b[i] |= mask;
				if(search(n-1)) return true;
				reu(i, y, y+n) b[i] &= ~mask;
			}
			next:;
		}
		return false;
	}
	int biggest(int w_, int h_) {
		w = w_, h = h_;
		for(int n = 13; n >= 1; n --) {
			mset(b, 0);
			if(search(n)) return n;
		}
	}
};