GCJ 2014 Round1C C. Enclosure

その他

large解法は解説でたら確認したい。

問題

囲碁のような、N*Mの長方形のグリッドがあり、その交点に石を置ける。
石の数と石で囲まれた領域のマスの数が少なくともKとなるように配置したい。
(囲碁とは違って、端を使って囲むようなことはできない)

.oo..
o..o.
.oo..
.....

例：4x5グリッドで、K=8であれば、石が最小6個あればよい。

N,M,Kが与えられるので、必要な最小の石の数を返す。
1<=N
1<=M
1<=K<=N*M
small: N*M<=20
large: N*M<=1000

いくつか自明なこと

  • K<=4までは、答えはK
  • NまたはMが2以下の場合、囲むように配置できないので、答えはK
  • 答えは、最大でもK以下

small解答

N*M<=20であることが保障されているので、「N*M要素からK個えらぶ組み合わせを全通り」試してみればよい。

やり方はいろいろあるけど、bitでの部分集合列挙は、蟻本の「集合の整数表現」などを参照。
http://d.hatena.ne.jp/jetbead/20121202/1354406422　の6も。
(例：(n,k)=(4,2)のときは、0011,0101,0110,1001,1010,1100)

N*M要素で1となっているK個の要素について、グリッドに配置しなおして、1となっているところの4近傍に必ず1があるときは領域ができているので、1となっているところの4近傍の1の数が4未満の数を数えれば、石の数がわかる。

Comb(N*M, K)は最大でも184,756なので、余裕で間に合う。

large解答

他の人の回答やkmjpさんを見てみると、以下のように解く模様。


面積がKを超えるW*Hの領域を削ってK個にする。削り方は、点対象に4つ角から削っていく。
左上、左下、右下、右上、のように順番に45度方向に削っていく。
左上の部分だけ取り出すと、

oooo
o...
o...
o...

.ooo
o...
o...
o...

..oo
.o..
o...
o...

...o
..o.
.o..
o...

のような削り方。


よくわかっていないのは、囲まれた領域がK以上のであれば削っていくが、削られていく領域が1,1,1,1,2,2,2,2,3,3,3,3,...のようにどんどん1回で削る量が増えてて、

..oo
.o..
o...
o...

から

...o
.oo.
o...
o...

のような削り方をすれば削られていく領域を1つずつにできる気がするけど、なんでそれが必要ないのか。。。
最適解の形が↑のような形になっていることがわかってればいいけど、なぜかはちゃんと説明できないorz


任意形状を取れるような領域は、その領域を含む長方形を取り出してそこで考えると無駄な計算をしなくてすみますね。