SRM 262 DIV1 Hard MagicBoxes
問題
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; } } };