PythonでXORエンコードされた配列から元の配列を復元するプログラム

問題の概要

非負の整数n個からなる隠し配列 arr があるとします。この配列は、長さ n-1 の別の配列 enc にエンコードされており、その規則は次の通りです。

enc[i] = arr[i] XOR arr[i+1]

ここで、エンコード済みの enc 配列と、元の配列の最初の要素を表す整数 first が与えられたとき、元の配列全体を復元することが目標となります。

例えば、入力が enc = [8,3,2,7]、first = 4 の場合、出力は [4, 12, 15, 13, 10] になります。

解法のポイント：XORの性質

この問題は、XOR演算の以下の性質を利用すると簡単に解けます。

• 自己消去： a XOR a = 0（同じ値同士のXORは0になる）
• 単位元： a XOR 0 = a（0とのXORでは値が変わらない）
• 可逆性： (a XOR b) XOR b = a（同じ値で2回XORすると元に戻る）

関係式 enc[i] = arr[i] XOR arr[i+1] の両辺に arr[i] をXORすると、次のように変形できます。

arr[i] XOR enc[i] = arr[i] XOR arr[i] XOR arr[i+1] = 0 XOR arr[i+1] = arr[i+1]

つまり、「前の要素」と「エンコード値」のXORを取ることで、次の要素が一意に求まります。この計算を先頭から順に繰り返せば、first を起点として配列全体を復元できるのです。

アルゴリズムの手順

• arr を first のみを含む配列として初期化する
• i を 0 から enc のサイズ - 1 まで繰り返す：
  • arr[i] XOR enc[i] の結果を arr の末尾に追加する
• arr を返す

Pythonでの実装例

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

def solve(enc, first):
    arr = [first]
    for i in range(0, len(enc)):
        arr.append(arr[i] ^ enc[i])
    return arr

enc = [8,3,2,7]
first = 4
print(solve(enc, first))

入力

[8,3,2,7], 4

出力

[4, 12, 15, 13, 10]

計算量の評価

このアルゴリズムは配列を一度だけ走査するため、時間計算量は O(n) です。また、結果を格納するために O(n) の追加メモリを使用します。エンコード値から各要素が一意に決まるため、これ以上効率化の余地はなく、本質的に最適な解法と言えます。