ぬりかべ

積Maximumぬりかべ

表出数字の積を最大化する。同じ表出数字を入れない。

黒マスを減らそうとする場合、上記の記事のようなシマの形の方が効率が良い。

また、辺にある黒マスは出来るだけ減らす。

数字なしぬりかべ

全てのヒントが？で、唯一解となる問題を作る。

9x9, 17-given

author: PinkHoodie 掲載20240809出題20240122

1-nを1つずつ表出する。

最密

7x7, n=7 author: Calcogen 掲載20230127出題20221227

10x10,n=9 author: takmu 掲載20230731出題20221002

最密

最密ぬりかべ

ぬりかべの盤面サイズをnxmとする。

盤面にある「格子点」（各マスの角の点）は全部で(n+1)(m+1)個である。1x1盤面なら4個、1x2なら6個、10x10なら121個、正方形盤面nxnなら(n+1)^2個。

これらの点を2種類に分類する：点の周囲4マス中に白マスを1つも含まない点、1つでも含む点。ただし盤面外は黒マスと扱う。

白マスを1つも含まない点の個数をbとおく。盤面の外周すべてに黒マスを置いたとき、bは最大値b=2(n+m)をとる。これ以上bを増やそうとすると黒マスの2x2禁に違反する。

また、白マスを1つでも含む点を、さらに分類する：その点の周囲の白マスがまとめて1つのシマに占有されている点、その点の周囲に白マスが2つあって別々のシマになっている点。それぞれ点の個数をw1,w2とおく。

さらに、シマの数をiとおき、そのうち盤面の辺上の白マスを含まないシマの個数をi_fとする。

b+w1+w2の値は一定であり、w2<=i_f。さもなければ黒マスのひとつながりルールに違反する。

i個のシマたちが占有する格子点の総和はw1+2*w2。黒マスを減らし、白マスを増やす場合には、この値を増やしたい。よってbを小さく、w2を大きく（最大i_f個、最大のとき全てのシマは斜めにつないでいくと盤面外周のどこかに到達し、黒マスループが存在しなくなる。）すればよい。iを保ったままi_fを大きくするには、外周黒マスを減らすことが必要になる。

解は以下の通り。

https://gyazo.com/a4d22294d5ccd0314d519573d11a2d0b

白丸はw1、二重丸はw2。

それぞれのシマが占有する格子点は、1～6のシマがそれぞれ4,6,8,9,11,12個。

i_fは1（1のシマ一つのみ）。4+6+8+9+11+12=50>49より、w2=1が必要。

まとめ：1つのシマがあまり多く格子点を占有しないようにする。例えば、Oテトロミノは他のテトロミノより1ポイント得。

「占有する格子点が少ない」は「内部格子点（白マス4マスに囲まれた格子点）が多い」と同値：シマの面積が1大きくなるとき、占有する格子点は通常2増えるが、内部格子点が1つ増えるとき占有格子点は1しか増えない。

辺上の白マスを含むシマが1つ少なくなると1ポイント得。角黒マスは1ポイント損。辺上で黒マスが2マス並んでいると1ポイント損。黒ループも1ポイント損。またiを一定にしたとき、外周黒マスを減らし、辺上の白マスを含むシマを減らす。

各シマがどれだけ多くの辺上の白マスを含むことができるか数える。

そのシマが角を含む場合は増える（以下の表の4列目）が、盤面には角は4つしかない。

table: サイズ、格子点数、辺上、角

サイズ 格子点数 辺上 角

1 4 1 1

2 6 2 2

3 8 3 3

4 9 2 3

5 11 3 4

6 12 3 4

7 14 4 5

8 15 4 5

9 16 3 5

10 18 5 6

11 19 4 6

12 20 4 6

13 22 5 7

14 23 5 7

15 24 5 7

16 25 4 7

17 27 6 8

一辺12だが、1～13のシマはいずれも辺上6未満のため、どの辺でも角・辺・角と最低3個のシマが並ぶ必要があり、盤面全体で辺上のシマは8個。このときi_f=13-8=5。

1～13のシマ：4+...+22=174、w2=5、i_f=5より最密。

作意：6が端の白マスを含まないと上辺が12,13で覆い切れない、R7C8が黒マス。

また、この議論は黒マスの数を出来るだけ増やしたい場合も使うことが出来る。1つのシマが出来るだけ多くの格子点を占有するようにする（＝内部格子点を減らす。白マス2x2に囲まれた格子点1つにつき1ポイント損。）2つのシマが格子点を共有すると1ポイント損。辺上で黒マスが2マス並んでいないと1ポイント損。