CodeIQ：あなたは乗り鉄？撮り鉄？それとも？

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「あなたは乗り鉄？撮り鉄？それとも？」（CodeIQ）を参照してください。

問題の概要

問題を引用します。

あなたは電車の車両編成を考えています。
この鉄道会社では、２種類の形の車両があります。
一つは運転席がある車両、もう一つは客席のみの車両です。

これらを組み合わせて編成するのですが、運転席がある車両は必ずペアで交互に逆向きに配置する必要があります。
つまり、図の上にあるような配置は可能ですが、図の下にあるような配置にすることはできません。
当然、両端は運転席がある車両になります。

【OKな例】

< □ □ >
< > < >

※ <、>は運転席のある車両、□は客席のみの車両

【NGな例】

< □ < > （ペアになる相手がいない）
< < > > （同じ向きになっている）

n両編成の車両を構成する場合、その組み合わせが何通りあるかを求めてください。
個々の車両は区別せず、配置のみを考えるものとします。
また、左右反転は同じものとしてカウントします。

私のプログラム

Pythonで解答しています。

#!/usr/local/bin/python3

import fileinput

def C(n,r):
	if r==0:
		return 1
	if n < r:
		return Nan

	ret = 1
	for i in range(n, n-r, -1):
		ret *= i
	for i in range(r, 1, -1):
		ret //= i
	return ret

'''
	>と<のペアを挿入する位置の組み合わせを求める。

	(1)
	両端が<>で固定されているため、選択可能な場所の動力車は必ず>で始まり<で終わる。
	そのため、動力車の挿入位置は車両数-2から2の倍数（n>=0)ごとに位置の組み合わせを決定すれば
	良い。<と>の順番は><の順で固定なので一意にに決定されるため、反転した場合を含めて組み合わせ
	の数に等しい。

	(2)
	反転できないパターンはfloor((車両数-2)/2)から動力車の数/2（0<n<floor((車両数-2)/2)）
	の組み合わせを選択する場合の数に等しい。
	（例：N=6の場合）
		先頭と末尾を除いて動力車を2台選択する場合、選択可能な4台の半分の2台から1台を選択した
		場合、次の2パターンが(1)の組み合わせの中で反転できないパターンとして含まれる。(カッコ)
		内は全体のパターンにした場合
		・>_ (>__<)
		・_> (_><_)

	従って、反転可能なパターンは(1)の組み合わせ数から(2)を引いた数の1/2となる。

	(3)
	結果は(1)から(2)を引いた数になる

'''
def countPattern(N):
	M = N-2	# 先頭と末尾は決まっているのでそれ以外の場所の数

	ret = 0
	for i in range(0, M+1, 2):
		t = C(M,i)	# 反転する分も含めた組み合わせ数

		# 反転して同じになるものの数を求める
		j = i//2
		L = M//2
		d = 0
		if 0 < j >= L:
			d = (t - C(L,j)) // 2
		ret += t-d

	return ret

if __name__ == "__main__":
	for line in fileinput.input():
		if not line.strip():
			continue
		N = int(line.strip())
		print(countPattern(N))

解説

この問題は★★★で難しいですが、加えて例が不親切です。
車両の並びに関しては次のような説明がわかりやすいでしょうか。

運転車両は<の次には>が来なければならない。
運転車両の間には客席だけの車両は（全体の長さの範囲内なら）何両あっても良い。

例えば、
「< □ > < >」とか「< □ > □ < >」
はOKです。

考え方

countPattern()に書いてある通りなのでそれ以上の説明はありませんが、もう少し詳しく説明します。
まず、ごく単純に考えるなら<、>、□を全パターン並べてみて、条件に合うものだけを数えることでしょうが計算量が膨大になります。なので動的計画法（メモ化再帰）で効率よくパターンを生成するか、計算だけで結果を求める必要があります
今回、私は計算だけで求めました。

運転車両の向きは考えなくて良い

さて、車両の編成のうち運転席のある車両だけを取り出した場合、問題から運転席のある車両は必ず< > < > …… < >の順で並びます。先頭が<で末尾が>なのは決まっていて、< >のペアでなければならないという条件があるためです。
ということは運転席のある車両の並び順は考えなくて良い（車両のどの位置が運転席のある車両かが決まれば< >の並びは一意に決まる）わけです。

つまり、全車両数-2（先頭と末尾を除いた車両数）から0、2、4、…の場所を選んでその選び方の組み合わせ数が運転席のある車両の位置の組み合わせになります。例えば全部で10両なら先頭と末尾を除いた8両中0、2、4、6、8両が運転車両になる組み合わせを求めれば良いわけです。

実際のコードでは47行目のループが先頭と末尾を除いた車両から0、2、4、…両の運転車両を選ぶループです。そして48行目で組み合わせ数を計算しています。C(n,r)は組み合わせを計算する関数です。

反転しても同じものを除く

上記計算結果には不要なパターンが含まれています。5両の場合の1例を示します。

< □ < > > …(A)
< < > □ > …(B)
< < □ > > …(C)

上のAとBは反転すると同じです。なのでBのパターンを先の計算結果から引かなければなりません。

しかし、AかBのパターン数を直接求める方法は（私には）わかりません。
AとBのパターン数は同数なのは（証明せよと言われるとあれですが）明らかです。そこでC（反転しても同じ編成になる）のパターン数を求め、全体のパターン数からCのパターン数を引き、その半分を求めることにしました。

Cは反転しても同じ（＝左右対称）なので、Cのパターン数は全体の半分だけを考えればわかります。図示します。

< < …(Cの左半分)

これを反転したものを右半分とすればCのパターンになります。

< < > >…(C')

5両なければならないのに4両しかありませんが？問題ありません。全体の車両数が奇数で左右反転しても同じ編成になる場合、真ん中は必ず客車だけの車両になります。なので5両編成の場合C'はCと同じことになります。

以上の考え方からCのパターンは（全体-2）両の半分から0、1、…の場所を選んだ場合の組合せ数の和になります。実際のコードでは51〜55行目で計算しています。55行目のtは全体の組合せ数でC(L,j)が左右対称の編成の組合せ数なのでdがパターンBの組合せ数になります。
56行目で（全体の組合せ数 - パターンBの組合せ数）を計算しています。55行目と56行目の式を展開してしまえば計算量が若干減りますが、後で見てわかりにくくなるので展開していません。

雑感

この問題は漸化式が先に思いついたパターンでした。
ですが、私がCodeIQの問題をやり始めた時点（2016/12頃）から公開されていたにもかかわらず、問題の意味（というかパターン）に理解できない部分があってあっていない問題がなくなるまで放置していました。
問題自体は結構面白いのでもう少し説明を詳しくしてくれたらよかったのにと思います。