この問題は 動的計画法 (DP) により解くことができます．

\(A\) に対して \(k\) 回操作を繰り返した列を \(A^{(k)}=(A_1^{(k)},\dots,A_{3^{N-k}}^{(k)})\) とします．\(A^{(k)}\) は問題文の操作を愚直に実行することで求めることができます． \(A^{(k)}_i \; (i=1,\dots,3^{N-k})\) の値を反転させるために \(A\) で変更する必要のある要素の個数の最小値を \(f(k,i)\) とします．\(f(N,1)\) が求める答えです．

まず，\(k=0\) については明らかに \(f(0,i)=1 \; (i=1,\dots,3^N)\) です．

\(k \geq 1\) のときを考えます．\(A_i^{(k)}\) は \(A^{(k-1)}_{3i-2},A^{(k-1)}_{3i-1},A^{(k-1)}_{3i}\) の過半数を占める値です．\(A^{(k-1)}_{3i-2},A^{(k-1)}_{3i-1},A^{(k-1)}_{3i}\) の中に \(A_i^{(k)}\) と同じ値のものは \(2\) 個か \(3\) 個あります．この個数に関して場合分けをします．

• 同じ値のものが \(3\) 個あるとき：\(A^{(k)}_i\) の値を反転させるためには， \(A^{(k-1)}_{3i-2},A^{(k-1)}_{3i-1},A^{(k-1)}_{3i}\) のうち \(2\) つを反転させる必要があります．よって，\(f(k,i)\) は \(f(k-1,3i-2),f(k-1,3i-1),f(k-1,3i)\) で小さい方から \(2\) つの和です．
• 同じ値のものが \(2\) 個あるとき：一般性を失わず \(A^{(k)}_i=A^{(k-1)}_{3i-2}=A^{(k-1)}_{3i-1}\) とします．このとき，\(A^{(k-1)}_{3i}\) を反転させる必要はなく，\(A^{(k-1)}_{3i-2},A^{(k-1)}_{3i-1}\) の一方を反転させればよいです．\(f(k-1,3i-2),f(k-1,3i-1)\) の小さい方を反転させればよいので，\(f(k,i)=\min\{f(k-1,3i-2),f(k-1,3i-1)\}\) です．

以上より，\(k\) が小さい方から順番に求めていくことで，すべての \(f(k,i)\) を求めることができます．時間計算量は \(O(3^N)\) です．

実装は，再帰関数を用いるのが簡便です．

実装例 (Python)