集合写真できれいに写る配置は何通り？
2月20日（火）AM10:00の締め切りが過ぎたので投稿します。
CodeIQにこんな問題があったので解いてみました。
問題
みんなで集合写真を撮るときの並び方の配置を考えます。
人数が少なければ一列に並ぶこともありますが、横に長くなると
図のように複数列に並ぶことがあります。
複数列に並ぶときは、互い違いに並ばないと全員の顔が見えないので、
前の人の間から顔が見えるように並びます。
また、隣の人とは間を空けずに並ぶものとし、後ろに行けば行くほど人数が少なくなるものとします。
標準入力から人数 n が与えられたとき、n人が並ぶときの並び方が何通りあるかを求め、
標準出力に出力してください。
（個人は区別せず、その配置だけを考えます。）
なお、n は 1≦n≦200を満たす整数とします。
例えば、n=6 のとき、以下の8通りがあります。
解答
とりあえず何も考えずpython3で書いてみました。
コード
codeiq_combination.py
#! python3
# お題：集合写真できれいに写る配置は何通り？
from functools import lru_cache
# num : これから並べる人数, space : すでに並んでいる人の間の数
@lru_cache(maxsize=10000)
def Lineup(num,space):
if num == 0:
return 1
count = 0
for forward in range(1,num+1)[::-1]:
# 並べられるかチェック
if forward > space:
continue
# 次後ろの人たちの数
back = num-forward
tmp = Lineup(back,forward-1)
cmb = space - forward + 1
count += tmp * cmb
return count
n = int(input())
result = 0
for forward in range(1, n+1)[::-1]:
back = n-forward
result += Lineup(back,forward-1)
print(result)
解説
基本的には再帰で後ろの人の並び方を求めていく感じで書いていきました。再帰なのですごく処理が重く時間もかかり、実行時間のリミット内に終わらない問題が発生してしまいました。（C++とかでやったら早いのかな？）
私はpython以外で書くのがめんどくさかったのでどうにかして早くする方法はないかを探してみたところ、高速化の定番のメモ化を発見しました。
メモ化とは、関数実行時の引数と結果を記録しておき、再度その引数で関数を実行するときに、記録していた結果を出力することによって余分な計算を省く高速化の手法です。
ただし関数は引数の値によって結果が一意に決まるものでしか使えません。
今回の再帰呼出に使っている関数は引数の値で結果が固定されているので導入してみました。
メモ化にはlru_cacheというライブラリが用意されているみたいなのでこちらを使いました。
使い方は、以下のようにインポートして再帰関数の上に@lru_cache(maxsize=10000)を付けるだけです。
from functools import lru_cache
@lru_cache(maxsize=10000)
def foo(hoge):
return foo(hoge-1)
maxsizeはメモのサイズです。大きく設定すればそれだけ多くのパターンに対応できますがメモリの消費量が多くなりますので注意してください。
これによって数秒かかっていた処理が1秒もかからず処理できるようになりました。すばらしい！
実際に実行してみて体感してみてください。
input
100
output
970174745
感想
高速化はあまり意識したことがなかったのですが実際問題にぶち当たって、試して体感すると、その重要さと感動に気付かされるものですね。
これから高速化も意識してコードを書いていきましょう。