この記事の続き
【へやわけ】角5x48に黒マスが87個しか入らないこと - SP1のぱずるにっき (hatenadiary.jp)
用語などはこれを参照のこと。
一般のケース
$5 \times L$ に入る黒マスの個数の最大を求める。なお、へやは左が $5$ の辺で盤面端、下が $L$ の辺で盤面端とする。
へやを上 $3$ 行と下 $2$ 行に分け、上に入る黒マスの個数を $X$, 下に入る黒マスの個数を $C$ とおく。また一番したの行に入る黒マスの個数を $r$ とおく。
前記事で紹介した補題により、$r\leq L-C+1$ が成り立つ。
下辺起因のペナルティを考えると、考慮すべきペアは $\lceil L/2 \rceil$ 個あり、よってペナルティとして $\max (0, C-1-\lfloor L/2 \rfloor) $ 献上する。
また上辺のハーフループ起因のペナルティを $f$ とおくと、$f$ は $L$ が偶数のとき $1$, 奇数のとき $0$ となる。
全体のペナルティ許容値を計算すると、$3(X+C) + f + C-1-\lfloor L/2 \rfloor \leq 5L + 3 + \lceil L/2 \rceil$ が成り立ち、特に $X+C$ を最大化したいことを念頭に置くと、以下の式が成立する必要があるとわかる：
$4(X+C) \leq 6L+4 + X - f$
$X$ については、辺 $L\times 3$ の MX 値により評価できる。具体的には以下：
- $L = 4k$ のとき、$X \leq 5k$
- $L = 4k+1$ のとき、$X \leq 5k+2$
- $L = 4k+2$ のとき、$X \leq 5k+3$
- $L = 4k+3$ のとき、$X \leq 5k+4$
これにより $X+C$ が評価される。
$L=16m+t$ とおいて、数値をまとめたものは以下：
| $L$ | $6L+4+X-f$ の上界 | $X+C$ の上界 |
|---|---|---|
| $16m$ | $116m+3$ | $29m$ |
| $16m+1$ | $116m+12$ | $29m+3$ |
| $16m+2$ | $116m+18$ | $29m+4$ |
| $16m+3$ | $116m+26$ | $29m+6$ |
| $16m+4$ | $116m+32$ | $29m+8$ |
| $16m+5$ | $116m+41$ | $29m+10$ |
| $16m+6$ | $116m+47$ | $29m+11$ |
| $16m+7$ | $116m+55$ | $29m+13$ |
| $16m+8$ | $116m+61$ | $29m+15$ |
| $16m+9$ | $116m+70$ | $29m+17$ |
| $16m+10$ | $116m+76$ | $29m+19$ |
| $16m+11$ | $116m+84$ | $29m+21$ |
| $16m+12$ | $116m+90$ | $29m+22$ |
| $16m+13$ | $116m+99$ | $29m+24$ |
| $16m+14$ | $116m+105$ | $29m+26$ |
| $16m+15$ | $116m+113$ | $29m+28$ |
一方、この値を実現する黒マスの配置は存在する (ベースケースに $29$ in 辺の $5\times 15$ を並べる)。よってこの上界がMX値となる。
