次の貪欲なアルゴリズムによって、この問題に正解できます。

• まず、スパイスを値段の昇順にソートします。つまり、\(c_{p_1} \leq c_{p_2} \leq \cdots \leq c_{p_{2^N-1}}\) となるように \((1, 2, \ldots, 2^N-1)\) の順列 \((p_1, p_2, \ldots, p_{2^N-1})\) を定めます。

• また、\(S\) を空集合とします。

• その後、\(i = 1, 2, \ldots, 2^N-1\) の順に、次を行います：

  • \(S\) の要素から辛さ \(p_i\) を作れるか、つまり、\(p_i = x_1 \oplus x_2 \oplus \cdots \oplus x_m\) となる \(x_1, x_2, \ldots, x_m \in S\) が存在するかを判定します。
  • \(S\) の要素から \(p_i\) を作れない場合は、\(S\) に \(p_i\) を追加します。

• 最後に、\(C(S) := \sum_{i \in S} c_i\) を答えとして出力します。

\(S\) の要素から \(p_i\) を作れるかの判定には、\(1, 2, \ldots, 2^N-1\) それぞれについて

\(b[i] := \) ( \(S\) に現在含まれる要素から辛さ \(i\) が作れるか？ true / false)

を保持し、\(S\) に要素を追加するたびに \(\mathrm{O}(2^N)\) 時間で \(b\) を更新していけば良いです。

また、\(S\) から \(m\) 種類の辛さ \(a_1, a_2, \ldots, a_m\) を作れるとき、 上記のアルゴリズムで \(S\) に \(x\) が追加されると、新たに \(m+1\) 種類の辛さ \(x, x \oplus a_1, x \oplus a_2, \ldots, x \oplus a_m\) が作れるようになり、\(S \cup \lbrace x\rbrace\) からは \(2m+1\) 種類の辛さを作れるようになります。 \(S\) に要素を追加するたびに、作れる辛さの種類は元の \(m\) 種類から \(2m+1\) 種類に増えるので、上記のアルゴリズムで \(S\) にスパイスを追加する回数は \(N\) 回です。

以上より、この問題を \(\mathrm{O}(N\cdot 2^N)\) 時間で解くことができます。

アルゴリズムの正当性

上記のアルゴリズムで正しい答えが求められることを以下で示します。

\(S\) の要素から \(1, 2, \ldots, 2^N-1\) をすべて作れるとき、\(S\) を良い集合ということにします。

上記のアルゴリズムで、\(p_1, p_2, \ldots, p_{i-1}\) については \(S\) に追加するかをすでに決定済みで、\(p_i\) を \(S\) に追加するかをこれから決める場面を考えます。次の \(2\) つを示します。

1. \(S\) にすでに含まれる要素から \(p_i\) を作れるときは、\(p_i\) を \(S\) に追加しなくてもよい
2. \(S\) にすでに含まれる要素から \(p_i\) を作れないときは、\(p_i\) を \(S\) に追加しても損をしない

1. の証明

ある \(x_1, x_2, \ldots, x_m \in S\) によって、\(p_i = x_1 \oplus x_2 \oplus \cdots \oplus x_m\) と表されるとします。 もし仮にその場で \(p_i\) を \(S\) に追加し、さらにその後 \(p_{i+1}, p_{i+2}, \ldots, p_{2^N-1}\) のうちのいくつかが \(S\) に追加されて良い集合 \(\hat{S}\) が完成したとします。

\(\hat{S}\) は良い集合なので、任意の \(z = 1, 2, \ldots, 2^N-1\) に対して、 ある \(y_1, y_2, \ldots, y_n \in \hat{S}\) が存在して、\(z = y_1 \oplus y_2 \oplus \cdots \oplus y_n\) と表せます。 ここでもし、\(y_1, y_2, \ldots, y_n\) の中に \(p_i\) があったとしても（一般性を失うことなく \(y_1 = p_i\) とする）、

\[z = p_i \oplus y_2 \oplus \cdots \oplus y_n = x_1 \oplus x_2 \oplus \cdots \oplus x_m \oplus y_2 \oplus y_3 \oplus y_n\]

となり、\(p_i\) を用いずに \(S \setminus \lbrace p_i \rbrace\) の要素だけから \(z\) を作ることができます。 つまり、\(\hat{S} \setminus \lbrace p_i \rbrace\) も良い集合です。

よって、\(S\) にすでに含まれる要素から \(p_i\) を作れるときは、\(p_i\) を \(S\) に追加しなくてもよいことがわかります。

2. の証明

\(S\) の要素から \(p_i\) を作れないと仮定します。 もし仮に \(p_i\) を \(S\) に追加しないことにし、さらにその後 \(p_{i+1}, p_{i+2}, \ldots, p_{2^N-1}\) のうちのいくつかが \(S\) に追加されて、良い集合 \(\hat{S}\) が完成したとします。

\(\hat{S}\) は良い集合なので、ある \(x_1, x_2, \ldots, x_m \in \hat{S}\) によって、 \(p_i = x_1 \oplus x_2 \oplus \cdots \oplus x_m\) と表せます。 このとき、

\[x_1 = p_1 \oplus x_2 \oplus x_3 \oplus \cdots \oplus x_m \]

が成り立ちます。

また、\(p_i\) は \(S\) の要素からは作れないと仮定したので、 \(x_1, x_2, \ldots, x_m\) のうち少なくとも一つは \(S\) に含まれません。 一般性を失わず \(x_1 \not\in S\) とします。

\(\hat{S}\) は良い集合なので、任意の \(z = 1, 2, \ldots, 2^N-1\) に対して、 ある \(y_1, y_2, \ldots, y_n \in \hat{S}\) が存在して、\(z = y_1 \oplus y_2 \oplus \cdots \oplus y_n\) と表せます。 ここでもし、\(y_1, y_2, \ldots, y_n\) の中に \(x_1\) があったとしても（一般性を失うことなく \(y_1 = x_1\) とする）、

\[z = x_1 \oplus y_2 \oplus \cdots \oplus y_n = p_i \oplus x_2 \oplus \cdots \oplus x_m \oplus y_2 \oplus y_3 \oplus y_n\]

となり、\((\hat{S} \cup \lbrace p_i \rbrace) \setminus \lbrace x_1 \rbrace\) の要素だけで \(z\) を作ることができます。 つまり、\((\hat{S} \cup \lbrace p_i \rbrace) \setminus \lbrace x_1 \rbrace\) も良い集合です。

また、\(x_1 \not\in S\) より \(c_{p_i} \leq c_{x_1}\) が成り立つので、 \(C((\hat{S} \cup \lbrace p_i \rbrace) \setminus \lbrace x_1 \rbrace) \leq C(\hat{S})\) です。

したがって、\(S\) にすでに含まれる要素から \(p_i\) を作れないときは、\(p_i\) を \(S\) に追加しても損をしないことがわかります。