Pythonで暗号コードを解読するプログラム｜循環配列の復号アルゴリズムを解説

問題の概要

爆弾を解除しなければならない場面を想像してください。残り時間はわずか！あなたの手元には、長さ n の循環配列 code と整数の鍵 k が渡されています。コードを解読するには、すべての数値を次のルールに従って同時に置き換えなければなりません。

• k > 0 の場合：i 番目の数値を「次の k 個の数値の合計」で置き換えます。

• k < 0 の場合：i 番目の数値を「前の k 個の数値の合計」で置き換えます。

• k = 0 の場合：i 番目の数値を 0 で置き換えます。

配列は循環しているため、code[n-1] の次の要素は code[0]、code[0] の前の要素は code[n-1] として扱います。最終的に、解読後のコードを返すことがゴールです。

具体例

入力が code = [8,2,3,5]、k = 3 の場合を考えてみましょう。このとき出力は [10, 16, 15, 13] になります。各要素を「自分の次の 3 要素の合計」で置き換えるためです。

• code[0] = 8 → 2 + 3 + 5 = 10
• code[1] = 2 → 3 + 5 + 8 = 16
• code[2] = 3 → 5 + 8 + 2 = 15
• code[3] = 5 → 8 + 2 + 3 = 13

解き方のアプローチ

この問題は、モジュロ演算（%）を活用すればシンプルに解けます。手順は以下の通りです。

1. 結果を格納する空のリスト decode を用意します。
2. i を 0 から code の長さ - 1 まで順に処理します。
3. k > 0 の場合は、j = i+1 から始めて k 回だけ code[j % len(code)] を加算し、その合計を decode に追加します。
4. k = 0 の場合は、0 をそのまま decode に追加します。
5. k < 0 の場合は、j = i-1 から始めて逆方向に k 回加算します（カウンター m を 0 に向かって増やしながらループします）。
6. すべての要素を処理したら decode を返します。

Pythonでの実装例

理解を深めるために、実際の実装を見てみましょう。

def solve(code, k):
    decode = []
    for i in range(len(code)):
        if k > 0:
            total = 0
            j = i + 1
            m = k
            while m:
                total += code[j % len(code)]
                m -= 1
                j += 1
            decode.append(total)
        elif k == 0:
            decode.append(0)
        else:
            total = 0
            j = i - 1
            m = k
            while m:
                total += code[j % len(code)]
                m += 1
                j -= 1
            decode.append(total)
    return decode

code = [8, 2, 3, 5]
k = 3
print(solve(code, k))

入力

[8,2,3,5], 3

出力

[10, 16, 15, 13]

計算量について

この実装の時間計算量は O(n × |k|) です。各要素ごとに最大 |k| 個の要素を参照するためです。空間計算量は、結果を保存するための O(n) となります。なお、累積和（スライディングウィンドウ）の考え方を応用すれば O(n) まで高速化できるため、大規模な入力を扱う場合はその最適化も検討するとよいでしょう。