Q.60：セルの結合パターン
カテゴリ：プログラミング(Python)、アルゴリズム、Atcorder
➊ 問題概要
その昔『プログラマ脳を鍛える数学パズル』を読んで解説が難解だったため、わかりやすくまとめてみました
＜セルの結合パターン＞2行2列のセルがあったとき，これを結合可能なパターンは８通りある
正方形または長方形以外の形が生じた場合はNGとなる
設問①: 3行3列の場合に結合してできるパターンは何通りか？
例） 2行2列の場合のOKパターンとNGパターン
設問②: 3行3列の場合に1×1のセルが無いように結合するパターンは何通りか？
例） 2行2列の場合のNGパターン
➋ 赤線と青線でパターンを洗い出す
N＝３の時赤線が6本、青線が6本存在するものとする ※ 赤線をwidth、青線をlengthとする
それぞれ線の表示・非表示を2進数で表現させる(表示：1、非表示：0)
widthとlengthに図に表すと以下となる
widthとlengthの表示・非表示でパターンを全て表すことができる
今までの解説をコードにすると以下になる、パターンは4096通りあることが分かる
import itertools
N = 3
CNT = 0
for wed in itertools.product([0,1],repeat=N*(N-1)):
for len in itertools.product([0,1],repeat=N*(N-1)):
print([wed],[len])
CNT += 1
print(CNT)
例えば width , length = (0, 0, 0, 0, 0, 0) , (0, 0, 0, 0, 0, 0)のときは
格子点からの線が全て非表示のため、大きい1つの正方形となる
❸ 格子点を設定し、十字でwidth1,2とlength1,2を考える
次は格子点(lattice)に注目してlat1とlat2を使いつつ、width1と2、length1と2を求める
3×3の場合だと格子点は4つ存在する
N=3、width =(1, 1, 0, 0, 1, 0) のとき width1 = width[lat1*(N-1)+lat2] width2 = width[(lat1+1)*(N-1)+lat2]
N=3、length =(1, 1, 0, 0, 1, 0) のとき length1 = length[lat1 * N + lat2] length2 = length[lat1 * N + lat2 + 1]
表を見る通り、それぞれの格子点で左右上下で線の表示・非表示を確認している
❹ ここまでのおさらい
ここまでで以下を実施している
・正方形のパターンを赤線と青線に注目して洗い出す(表示：1、非表示：0)
・格子点を設定する
・格子点ごとに十字でwidth1,2とlength1,2を考える
今までの解説をコードにすると
import itertools
N = 3,CNT = 0
def check1(width, length):
for lat1 in range(N - 1):
for lat2 in range(N - 1):
width1 = width[lat1 * (N - 1) + lat2]
width2 = width[(lat1 + 1) * (N - 1) + lat2]
length1 = length[lat1 * N + lat2]
length2 = length[lat1 * N + lat2 + 1]
#print(width,length)
return True
for wed in itertools.product([0, 1], repeat=N * (N - 1)):
for len in itertools.product([0, 1], repeat=N * (N - 1)):
if check1(wed, len):
CNT += 1
print(CNT)
❺ Badパターンに合致する形を除外する
【設問①を求める考え方】全てのパターン(4096通り)を洗い出して，Badパターンは除いてカウントすれば良い
ここで重要なのはBadパターン条件を整理することである
★ Badパターン（2つ結合する場合）
★ Badパターン（1つ結合する場合）
よって今までの要素をコードにすると設問① cnt1 = 322が求められる
import itertools
N = 3
def solve():
cnt1 = cnt2 = 0
for wed in itertools.product([0, 1], repeat=N * (N - 1)):
for len in itertools.product([0, 1], repeat=N * (N - 1)):
if check1(wed, len):
cnt1 += 1
print("cnt1 =", cnt1)
def check1(width, length):
#結合パターン
for lat1 in range(N - 1):
for lat2 in range(N - 1):
width1 = width[lat1 * (N - 1) + lat2]
width2 = width[(lat1 + 1) * (N - 1) + lat2]
length1 = length[lat1 * N + lat2]
length2 = length[lat1 * N + lat2 + 1]
# 格子点で2箇所結合するNGパターン
bad2_1 = width1 and not width2 and length1 and not length2
bad2_2 = not width1 and width2 and length1 and not length2
bad2_3 = width1 and not width2 and not length1 and length2
bad2_4 = not width1 and width2 and not length1 and length2
nogood1 = bad2_1 or bad2_2 or bad2_3 or bad2_4
# 格子点で1所結合するNGパターン
bad1_1 = width1 and not width2 and not length1 and not length2
bad1_2 = not width1 and width2 and not length1 and not length2
bad1_3 = not width1 and not width2 and length1 and not length2
bad1_4 = not width1 and not width2 and not length1 and length2
nogood2 = bad1_1 or bad1_2 or bad1_3 or bad1_4
if nogood1 or nogood2:
return False
#print(width,length)
return True
if __name__ == '__main__':
solve()
設問①でだいぶ長くなってしまったので設問②は次回以降とします、お楽しみに～ ☺