解説 ヘヤジリン1（アゼン〜ハバネロ）

問題　http://puzsq.sakura.ne.jp/main/puzzle_play.php?pid=4284

まずとっかかりが掴めなさそうですが、なんとなく最密だろうなという予想を立てて、それを検証していきます。

まず壁に挟まれた3×10の空間について考えてみます。

高難易度のヤジリンに置いて使われる手筋に "2×3の空間には黒マスが最大2個までしか入らない" というものがあります。3個入れると、くの字型になり、破綻するからです。

これを使って考えてみると、おそらく10個まではいるだろうと予測が立ちます。さらにここから、10個の黒マスを入れるときに3×1の空間に、2個以上入らないことを示します。

(1) 壁際の3×1の空間・・・行き止まりができるのでだめ

(2)空中の3×1の空間・・・必ず、その3×1の空間を端っこに含まない3×4の空間が存在して、その3×4の空間に4つの黒マスを入れることは不可能→2つの黒マスを含まない2×3の空間が存在するので、最密にはならないのでだめ

よって、3×1の空間には、2個以上入らないので、必ず1個だけ黒マスが含まれていることがわかります。

以上で、壁に挟まれた3×10の空間には最大で10個黒マスが入り、そのとき、3×1の空間には必ず1つの黒マスが含まれていることが示せました。

次に、右下の変な出っ張りについても黒マスがいくつ入るか考えます。こちらは簡単で、1×5と2×2の空間に分けたとき、片方が最密ならもう片方は最密-1個までしか入らないことが、先読みでわかるので、最高4個まで入ります。

よって図のように空間を分けて最密の黒マスの和を数えると、

1+1+10+1+2+4=19となり、入る黒マスの値と一致するので、ある空間の最密の時の黒マス＝実際に入る黒マスとなります。

あとはゴリゴリやってください。また補足すると、右上の4マスの空間は、偶数端点法を使うとやりやすいです。

おわり