さっきのペナルティ理論を自分の問題に適用して考えてみる

2024年6月13日 19:29

これをペナルティで解いてみます。

前の記事で出した関係式を下に書きます。

'''
値を次のように決めます。
A_black = 境界線に1辺以上接する黒マスの数+境界線に2辺接する黒マスの数+2x境界線に3辺接する黒マスの数
A_blackMAX = 境界線に1辺以上接する黒マス最大値+境界線に2辺接する黒マス最大値+2x境界線に3辺接する黒マス最大値
A_penalty = A_black_MAX - A_black
A_all = 境界線に1辺以上接するマスの数+境界線に2辺接するマスの数+2x境界線に3辺接するマスの数

この時、
全体の辺の数(白-壁も含む)-4x黒マスの数-白マスの数-A_all+A_blackMAX = A_penalty + (白マスの2x2+白マスループ) - 白マスの塊の数
となる。
'''

盤面から得られる情報からペナルティの抽出

今回の問題だと、全体の辺の数=下図の黒い線の合計なので、220本となります。
黒マスは36、白マスは64なので,

220-4x36-64-A_all+A_blackMAX = A_penalty + (白マスの2x2+白マスループ) - 白マスの塊の数

次にA_all、A_blackMAXを考える。
A_all = 境界線に1辺以上接するマスの数+境界線に2辺接するマスの数+2x境界線に3辺接するマスの数
より、A_all=36+4+0=40となる

A_blackMAX=境界線に1辺以上接する黒マス最大値+境界線に2辺接する黒マス最大値+2x境界線に3辺接する黒マス最大値
なので、順番に見ていく。
1つ目は次のように分割重点すればわかる。

つまり、17個が最大値
2つ目は10x10の部屋の全ての角に黒マスを配置することは可能なので4個になる。
3つ目は該当なしで0

よって、A_blackMAX=17+4+0=21となる。

以上より、
220-4x36-64-40+21 = A_penalty + (白マスの2x2+白マスループ) - 白マスの塊の数

以上より、
-7= A_penalty + (白マスの2x2+白マスループ) - 白マスの塊の数
となる。

次に白マスの塊の数の最大値を考える。これは、できるだけ黒マスで分割することを考えればよい。

例えば、上の図だと白マスは9個に分割されているので、内部で他の白マスの塊と合体することがなければ、白マスの塊の数は9になる。今回は9の場合、下の1によって分断禁が起こるので不可能。白マスの塊の最大値は8となる。

ここで、-7 = A_penalty + (白マスの2x2+白マスループ) - 白マスの塊の数の関係式は
白マスの塊の数 = 白マスの塊の数の最大値 - 内部での他の白マスの塊との合体数となるので、
1 = A_penalty + (白マスの2x2+白マスループ) + 内部での他の白マスの塊との合体した数

という式が出てくる。

よって、上記の値がすべて0以上なので、

1 = 境界線に1辺以上接する黒マス最大値からの欠損+境界線に2辺接する黒マス最大値からの欠損+2x境界線に3辺接する黒マス最大値からの欠損+(白マスの2x2+白マスループ) + 内部での他の白マスの塊との合体した数

と表される。ここで、
境界線に2辺接する黒マス最大値からの欠損・・・第一種ペナルティ(角の黒マス)
境界線に1辺以上接する黒マス最大値からの欠損・・・第二種ペナルティ(境界線周りの黒マス)
白マスの2x2+白マスループ・・・第三種ペナルティ(部屋内部で発生したループ数)
内部での他の白マスの塊との合体した数・・・第四種ペナルティ(白マス塊の減少数)
境界線に3辺接する黒マス最大値からの欠損・・・第五種ペナルティ(岬の黒マス)

として、ぞれぞれp1,p2,p3,p4,p5とすると、これらは全て0以上になる。
よって、このうちどれかが1になることがわかる。