集合写真できれいに写る配置は何通り?
締め切りが 2018/02/20 10:00 AM なので,その 1 分後に投稿されるように予約
設問
みんなで集合写真を撮るときの並び方の配置を考えます。
人数が少なければ一列に並ぶこともありますが、横に長くなると図のように複数列に並ぶことがあります。
複数列に並ぶときは、互い違いに並ばないと全員の顔が見えないので、
前の人の間から顔が見えるように並びます。
また、隣の人とは間を空けずに並ぶものとし、後ろに行けば行くほど人数が少なくなるものとします。
標準入力から人数 n が与えられたとき、n人が並ぶときの並び方が何通りあるかを求め、
標準出力に出力してください。
(個人は区別せず、その配置だけを考えます。)
なお、n は 1≦n≦200を満たす整数とします。
例えば、n=6 のとき、以下の8通りがあります。
【入出力サンプル】
標準入力
6
標準出力
8
==================================================================
これは,整数列大辞典の A001524 であるが,そこに書いてあるアルゴリズムの説明が不完全(?)で,私には解を導くことができなかった。
n が小さい場合について,順次列挙していくと,規則性が浮かび上がった。
R(n,r) は,n 人を並べるとき,最下段が r 人になる並び方の総数
R(n1, n1)=1,R(1,1)=r(6,3)=R(10,4)=1 などの自明な解と,規則的な関係が見られる。
規則をプログラムしたものの,R ではいつものとおり計算時間オーバーなので(私のシステムでは制限時間内),Python 3 でやってみても,やはり時間オーバー。
全く同じものを「Python3 ではなくて,Python だよ!」と,だましたら,パスした。なんだこりゃ。
R プログラム
f = function(N) {
n = 200
a = matrix(0, n, n)
for (i in 1:n) {
a[i, i] = 1
}
tri.max = 19
tri = integer(tri.max)
for (i in 1:tri.max) {
x = i*(i+1)/2
tri[i] = x
a[x, i] = 1
}
a[4, 3] = 2
a[5, 3] = 1
a[5 ,4] = 3
begin = 3
for (i in 6:N) {
begin = begin + (i %in% tri)
end = i-1
for (j in begin:end) {
top = i-j
temp = 0
for (k in top:1) {
mul = i-top-k
if (mul > 0) {
temp = temp+a[top, k] * mul
}
}
#cat(i, j, "\n")
a[i, j] = temp
}
}
options(scipen=100)
cat(sum(a[N,]))
}
# f(scan(file("stdin", "r")))
f(4) # 3
f(6) # 8
f(10) # 38
f(100) # 970174745
system.time(f(200)) # 56220326505673、0.126 s
=============================================
Python プログラム
import scipy as sp
def f(N):
n = 200
a = sp.reshape(sp.zeros(n*n), (n, n))
for i in range(n):
a[i, i] = 1
tri_max = 19
tri = sp.zeros(tri_max)
for i in range(1, tri_max+1):
tri[i-1] = i*(i+1)/2 - 1
for i in range(tri_max):
a[tri[i], i] = 1
a[3, 2] = 2
a[4, 2] = 1
a[4 ,3] = 3
begin = 2
for i in range(5, N):
if i in tri:
begin += 1
end = i-1
for j in range(begin, end+1):
top = i-j-1
x = 0
for k in range(top, -1, -1):
mul = i-top-k-1
if mul > 0:
x += a[top, k] * mul
a[i, j] = x
ans = 0
for i in range(N):
ans += a[N-1, i]
print(int(ans))
f(int(input()))
#f(6) # 8
#f(4) # 3
#f(10) # 38
#f(100) # 970174745
#f(200) # 56220326505673 Python 3 より Python 2 が速い? 0.91s