切手を切って！
締め切りが 2018/02/14 10:00 ＡＭ なので，その 1 分後に投稿されるように予約
設問
次のような切手シートがあります。
この切手シートから、3枚の切手がつながったまま切り取る方法は、以下のように10通りあります。
【問題】
切手シートの、たて・よこ・切り取りたい枚数が与えられたとき、切り取り方の総数を求めてください。
たて・よこの枚数は、いずれも1～10枚、切り取りたい枚数は1～5枚を想定してください。
【入力】
次の書式で数値が与えられます。
●1行目に、データセットの件数nが書かれています。
●2行目以降のn行に、たての枚数・よこの枚数・切り取りたい切手の枚数が、半角スペースで区切られています。
----（例）----
2
2 3 2
2 3 3
----（例）----
【出力】
データセット毎に、改行区切りで切手の切り取り方が何通りあるかを出力してください。
----（例）----
7
10
----（例）----
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
たとえば，正方形のピース数が k で，外形の行数が 2，列数が 3 のものは，以下の 6 通りのパーツである。
そのパーツを ｍ × ｎ の枠内に配置する方法は (m-2+1)×(n-3+1)×k 通りある。
k ごとの外形行数・列数，パーツの種類は以下のようになっている。
row col parts
k 外形行数 外形列数 パーツの種類
2 2 1 1
1 2 1
3 3 1 1
2 2 4
1 3 1
4 4 1 1
3 2 8
2 2 1
2 3 8
1 4 1
5 5 1 1
4 2 12
3 2 6
3 3 25
2 3 6
2 4 12
1 5 1
Ｒ によれば，プログラムは非常に簡単に書ける。
f = function(m, n, k) {
param = list(0,
list(row=2:1, parts=c(1,1)),
list(row=3:1, parts=c(1,4,1)),
list(row=c(4, 3, 2, 2, 1), parts=c(1, 8, 1, 8, 1)),
list(row=c(5, 4, 3, 3, 2, 2, 1), parts=c(1, 12, 6, 25, 6, 12, 1)))
p = param[[k]]
col = rev(p$row)
ans = sum((m-p$row+1)*(n-col+1)*p$parts)
cat(ans)
}
f(2, 3, 2) # 7
f(2, 3, 3) # 10
f(5, 5, 2) # 40
f(3, 4, 3) # 34
f(3, 4, 4) # 65
f(6, 7, 5) # 1282
f(100,100,5) # 606196
Python3 では
def f(m, n, k):
param = list([
[[2,1], [1,1]],
[[3,2,1], [1,4,1]],
[[4, 3, 2, 2, 1], [1, 8, 1, 8, 1]],
[[5, 4, 3, 3, 2, 2, 1], [1, 12, 6, 25, 6, 12, 1]]])
p = param[k-2]
ans = 0
length = len(p[0])
for i in range(length):
ans += (m-p[0][i]+1)*(n-p[0][length-1-i]+1)*p[1][i]
print(ans)
なお，ピース数 k ごとに，外形が m×n のパーツが何種類あるかは，以下のプログラムで求めることができる。
check = function(x) {
if (any(colSums(x) == 0, rowSums(x) == 0)) {
return(FALSE)
}
m = nrow(x)
n = ncol(x)
z = matrix(0, m+2, n+2)
z[1+1:m, 1+1:n] = x
for (i in 1+1:m) {
for (j in 1+1:n) {
if (z[i, j] == 1) {
z[i, j] = 2
break
}
}
if (z[i, j] == 2) {
break
}
}
repeat {
replace = FALSE
for (i in 1+1:m) {
for (j in 1+1:n) {
if (z[i, j] == 2) {
if (z[i-1, j] == 1) {
z[i-1, j] = 2
replace = TRUE
}
if (z[i+1, j] == 1) {
z[i+1, j] = 2
replace = TRUE
}
if (z[i, j-1] == 1) {
z[i, j-1] = 2
replace = TRUE
}
if (z[i, j+1] == 1) {
z[i, j+1] = 2
replace = TRUE
}
}
}
}
if (!replace) {
break
}
}
!any(z == 1)
}
g = function(m, n, k=6, vervose=FALSE) {
library(e1071)
b = bincombinations(m*n)
s = rowSums(b)
b = b[s == k, , drop=FALSE]
count = 0
for (i in 1:nrow(b)) {
x = matrix(b[i, ], m, n)
if (check(x)) {
count = count+1
if (vervose) {
cat(count, "\n")
print(x)
}
}
}
cat(count, "pattern(s)\n")
}
