Google Code Jam 2014 Round 1C : C. Enclosure

Bよりこっちの方がすんなりかも…。
https://code.google.com/codejam/contest/3004486/dashboard#s=p2

問題

NxMの盤で行われる囲碁風ゲームを考える。
ここに石をいくつか置いた場合、以下の合計ポイントを得られる。

• 石を置いたマスの数
• 石に囲まれた（＝石のない隣接マスをたどっても盤の一番外側のマスにたどりつけない）マスの数

得られたポイントがちょうどKの場合、Kポイントを得る最小の石の数を答えよ。

解法

石に囲まれたマスを作るには、そのマスの上下左右に石を置く必要がある。
よってK<=4の場合や、盤の幅・高さが2以下の場合は石で囲むことができないため、素直にK個石を置くしかない。
以下は、Kが4より大きく、幅や高さが3以上を前提とする。

Kポイントより大き目のポイントを得ている場合、少しポイントを減らすのは容易である。
例えば以下のようにちょっとへこませれば3ポイント得られる。

ooooooo      oo oooo
o.....o      o.o...o
o.....o  ->  o....o 
o.....o      o..o..o
ooooooo      ooo ooo

よって、Kポイント以上得られる最小石数を求めよう。
Kポイントを超えた分は、上のようにへこませて調整できる。

同じ石の数を使って得られる最大得点は、以下のように星形に置くことであり、縦横に石を並べるよりも囲えるマスが大きい。

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

NxMの盤目の一部WxHの領域をこの星形で埋めることを考える。
H < Wとし、以下のように配置する。

以下Hが奇数の場合(H=7,W=9)である。
この時、４ツ角(xxxの部分)は、１個石を増やすとxの個数、すなわち3個囲まれたマスを増やせる。
下は左上の角の部分の石を１個増やし(*の部分)、3ポイント増やした様子である。
この次にこの角は、１個石を増やしても2ポイントしか増やせないので、次は他の角に石を置くのが効率的である。

  xooo          x*ooo
 xo...o        x*... o
xo.....o       *..... o
o.......o  ->  o.......o
 o.....o        o.....o
  o...o          o...o
   ooo            ooo

このように、４つの角に順々に石を増やしてポイントを稼ぎ、Kを超えるまで処理を繰り返せばよい。

Hが偶数の場合、以下のように４ツ角の大きさを少しずらすとよい。(H=6,W=9)

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

補足

自分は星形から角を広げていったけど、逆に長方形から角を削る方がわかりやすいかも。
GCJ 2014 Round1C C. Enclosure - れどこだ目指すよ！ (；`・ω・）

int N,M,K;

int dodo(int H,int W,int K) {
	if(H*W<K) return K;
	int num = 2*W-2;
	int tot;
	int left[4];
	
	if(H%2) {
		tot=H*W-(H/2)*(1+H/2)/2*4;
		left[0]=left[1]=left[2]=left[3]=H/2;
	}
	else {
		tot=H*W-(H/2)*(1+H/2)/2*2-(H/2-1)*(H/2)/2*2;
		left[0]=left[1]=H/2-1;
		left[2]=left[3]=H/2;
	}
	
	while(tot<K) {
		sort(left,left+4);
		num++;
		tot+=left[3]--;
	}
	return num;
}

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M>>K;
	if(N>M) swap(N,M);
	
	if(N<=2 || K<=4) return _P("Case #%d: %d\n",_loop,K);
	
	int mi=K;
	for(x=3;x<=N;x++) for(y=x;y<=M;y++) mi=min(mi,dodo(x,y,K));
	_P("Case #%d: %d\n",_loop,mi);
}

まとめ

なんか予選のマインスイーパっぽい問題。
本番正答者の考え方はよくわからないけど、自分のも割とわかりやすい手順だと思うけどどうだろう。