Pythonで解く「不器用な階乗（Clumsy Factorial）」問題 ― スタックを使った実装方法

正の整数 n の階乗とは、n 以下のすべての正の整数を掛け合わせた値のことです。たとえば factorial(10) = 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 となります。

本記事で扱うのは、この階乗をもじった「不器用な階乗（Clumsy Factorial）」という問題です。整数を降順に並べながら、演算子を「掛け算（*）→ 割り算（/）→ 足し算（+）→ 引き算（-）」という固定の順序で循環的に差し替えて計算します。

たとえば clumsy(10) は次のように表されます。

clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1

ただし、演算は通常の数学の優先順位に従って適用されます。つまり、足し算・引き算よりも先にすべての掛け算・割り算を実行し、掛け算・割り算同士は左から右へ処理します。さらに、ここでの割り算は切り捨て除算（floor division）であり、10 * 9 / 8 は 11 になります。このルールにより、結果は必ず整数になります。

たとえば入力が 10 の場合、出力は 12 になります。これは 12 = 10 * 9 / 8 + 7 − 6 * 5 / 4 + 3 − 2 * 1 となるためです。

解法のアプローチ

この問題はスタック（stack）を使うことで効率よく解けます。具体的な手順は以下の通りです。

• 演算子の配列 operations を定義し、「*」「/」「+」「-」を格納します。空のスタックを作成し、N をプッシュします。
• index := 0 と初期化します。
• N を 1 減らします。
• N が 0 になるまで以下を繰り返します。
  • operations[index] が「*」の場合：スタックの先頭要素が 0 以上なら top_element := N * top_element で更新します。負の場合は stack[-1] := -1 * |N * stack[-1]| とします。
  • operations[index] が「/」の場合：スタックの先頭要素が 0 以上なら top_element := top_element / N で更新します。負の場合は stack[-1] := -1 * |stack[-1] / N| とします。
  • operations[index] が「+」の場合：N をそのままスタックに挿入します。
  • それ以外（「-」）の場合：(-1 * N) をスタックに挿入します。
• index := (index + 1) mod 演算配列の長さ として更新し、N を 1 減らします。
• 最後に、スタック内の全要素の合計を返します。

アルゴリズムのポイント

この手法の鍵は、引き算（-）が出現した時点で新しい計算ブロックが始まるという点にあります。「*」と「/」は直前の値に対して連続して適用されるため、スタックの先頭要素を直接書き換えます。一方、「+」は新しい数をスタックに積み、「-」は符号を反転した数を積むことで、最終的な合計が式全体の値と一致する仕組みになっています。

また、負の数に対する切り捨て除算の扱いにも注意が必要です。Python の「//」は床除算のため、負の数では意図しない方向に丸められることがあります。そこで、絶対値で計算してから符号を付け直すことで、正しい結果を得られるようにしています。

実装例

以下のコードで実際の動作を確認してみましょう。

class Solution(object):
    def clumsy(self, N):
        operations = ["*","/","+","-"]
        stack = []
        index = 0
        stack.append(N)
        N-=1
        while N:
            if operations[index] == "*":
                if stack[-1]>=0:
                    stack[-1] *=N
                else:
                    stack[-1] = -1*(abs(stack[-1])*N)
            elif operations[index] == "/":
                if stack[-1]>=0:
                    stack[-1] //=N
                else:
                    stack[-1] = -1*(abs(stack[-1])//N)
            elif operations[index] == "+":
                stack.append(N)
            else:
                stack.append(-1*N)
            index = (index+1) % len(operations)
            N-=1
        return sum(stack)
ob = Solution()
print(ob.clumsy(10))

入力

10

出力

12