本記事は『プログラマを育てる脳トレパズル 遊んでおぼえるPythonプログラミング＆アルゴリズム』の「Q01 ボウリングの点数を計算しよう」と「Q11 効率のよいファミリーレストラン」を抜粋したものです。掲載にあたり一部を編集しています。
回答のコードはPythonで記載していますが、本書の読者特典としてRubyとJavaScriptでの回答も提供しています（SHOEISHA iDへの会員登録が必要です）。
出題：ボウリングの点数を計算しよう
東京オリンピックの追加種目の候補に挙がりながら、落選してしまったボウリング。それでも若い人から年配の人まで、幅広く楽しめるゲームとして人気です。ボウリングでは次のようなスコアがつけられます。
ご存じの通り、「×」のマークに塗りつぶされているのは「ストライク」、「／」のマークに塗りつぶされているのは「スペア」といいます。ストライクの場合、次の2投分の点数を、スペアの場合は次の1投分の点数を加算できます。また、「G」は「ガーター」、「－」は「ミス（ピンに当たらなかった）」を意味し、いずれも0点です。
なお、10フレーム目はストライクやスペアがあれば3回投げられますが、それ以外は2回だけ投げられます。10フレーム目では倒れたピンの数だけがカウントされるため、ストライクが3つの場合は30点です。つまり、すべてストライクの場合は次のようになり、最高点は300点です。
上記の例の場合、次のような2次元のリスト（配列）で各フレームでの点数が与えられるものとします。
例1：[[6, 4], [8, 0], [10], [2, 7], [5, 5], [3, 4], [10], [9, 1], [1, 2], [7, 1]]
例2：[[1, 8], [9, 1], [7, 2], [10], [0, 0], [9, 1], [3, 6], [8, 0], [5, 4], [10, 8, 1]]
例3：[[10], [10], [10], [10], [10], [10], [10], [10], [10], [10, 10, 10]]
問題
次のリストが与えられたとき、その点数を求めてください。
[[9, 1], [8, 2], [10], [5, 0], [3, 6], [4, 2], [7, 3], [6, 3], [10], [9, 1, 9]]
考え方
前のフレームから処理すると、次のフレームの点数がわからないと計算できません。そこで、逆にリストの後ろから計算してみましょう。前のフレームで使うピンの数を変数に入れておくと、簡単な足し算で計算できます。
出題：効率のよいファミリーレストラン
客の人数に合わせてテーブルを動かすファミリーレストランを考えます。例えば、1人客や2人組の客に4人掛けのテーブルを使わせると、残りの席がムダになります。そこで、2人掛けテーブルを組み合わせて、できるだけ効率よくテーブルを配置していきます。
店内にある2人掛けテーブルの数と、店内にいる客の人数がわかっているとき、テーブルの組み合わせ方として考えられるものが何通りあるかを考えます。このとき、どの客がどのテーブルのどこに座っているかは区別せず、テーブルの位置も区別しないものとします。
つまり、以下のような配置はいずれも同じ（1通り）とします。
なお、相席になることはないものとし、1人客でも2人掛けのテーブルを使い、3人客の場合は2人掛けのテーブルを2つ使います。また、空席のテーブルができないように配置します。
例えば、テーブルが3つ、客が5人の場合、次の4通りが考えられます。
問題
テーブルが50個、客が80人の場合、考えられる配置（グループの人数）が何通りあるか求めてください。
考え方
どの客がどのテーブルのどこに座っているかは区別しないので、配置が決まるのは各グループの人数だけです。つまり、グループの人数を少ない方から順に配置していき、すべての客を配置すれば完了です。2人掛けのテーブルなので、テーブルの数の2倍よりも多くの客が残っていると配置できません。
ヒント
グループの人数が着席するのに必要なテーブルの数を1つの式で表現することを考えましょう。規則性としては、1人と2人は1個、3人と4人は2個、5人と6人は3個、というように増えていきます。
解説：ボウリングの点数を計算しよう
答え
127点
STEP1
ストライクやスペアのときは、次のフレームで倒したピンの数がないと計算できないため、後ろのフレームから順に処理することを考えます。このとき、前のフレームで計算するために必要なのは、次のフレームで倒したピンの数です。ただし、ストライクが続いた場合は、2つ後のフレームの値も必要になることがあります。
ここで、ストライクの場合も「次の2つの投球で倒したピンの数がわかればいい」ということに注目します。つまり、用意するのは次の2つの投球で倒したピンの数を保持する変数2つだけです。
Point
計算に必要なのは現在のフレームで倒したピンの数と、その後の投球で倒したピンの数ですが、その後の投球で倒した数は最大2つ保持すればOKです。
STEP2
10フレーム目も特殊な処理が必要で、ストライクやスペアにかかわらず、そのフレーム内で倒したピンの合計本数が10フレーム目での得点です。
その他のフレームでは、ストライクは次の2投球、スペアは次の1投球を加算すると、次のようなプログラムで実装できます。
def calc(score):
result, next1, next2 = 0, 0, 0
while len(score) > 0:
frame = score.pop(-1) # 最後のフレームを取り出し
total = sum(frame)
if len(frame) == 3: # 10フレーム目でスペアやストライク
result += total
elif len(frame) == 1: # ストライクのとき
result += 10 + next1 + next2
next1, next2 = 10, next1
elif total == 10: # スペアのとき
result += 10 + next1
next1, next2 = frame
else:
result += total
next1, next2 = frame
return result
print(calc([
[9, 1], [8, 2], [10], [5, 0], [3, 6],
[4, 2], [7, 3], [6, 3], [10], [9, 1, 9]
]))
解説：効率のよいファミリーレストラン
答え
588,394通り
STEP1
グループの人数を少ない方から順に配置するため、残っているテーブル数と客の人数に加えて、直前に配置した客の人数を引数とした関数を作成します。
テーブルに配置する人数（グループの人数）を直前に配置した人数から順に配置してみて、再帰的に探索します。このとき、人数からテーブルの数を求める式を考えます。
ヒントに書いたように、人数が偶数のときはその人数を2で割って計算できます。奇数のときは人数に1を足して、2で割ると計算できます。そこで、人数に1を足して、2で割った商を使います（偶数のときも商は変わらない）。
STEP2
残っているテーブル数と客数がちょうど0になれば配置終了ですが、テーブルの数が足りなくなったり、残っている客がいなくなったりすると配置失敗です。
Point
同じテーブル数、人数が何度も発生するのでメモ化が必要ですが、キャッシュのサイズに注意。テーブルが50、人数が80なので1000くらいでは不足して時間がかかってしまいます。単純計算で4000以上を指定する必要があります。
from functools import lru_cache
@lru_cache(maxsize=5000)
def search(table, n, pre):
if (table == 0) and (n == 0):
# テーブル数と客数がともに0になれば終了
return 1
if (table <= 0) or (n <= 0) or (table * 2 < n):
# いずれかが0になったり、テーブルの2倍を超えるとNG
return 0
cnt = 0
for i in range(pre, n + 1):
# 配置する人数(グループの人数)でチェック
cnt += search(table - (i + 1) // 2, n - i, i)
return cnt
# 最初はグループの人数を1人からスタート
print(search(50, 80, 1))
