操作の言い換え,不変量
等しい値にする事だけが重要なので,差を考えたほうが楽. \(+3, +5, +7\) の操作は \(-2, 0, +2\) と言い換えても良い. 言い換えた操作では, vector \(x\) の値は不変. よって,もし等しい値 \(s\) にできるのであれば, \(s = \) 初期状態の \(x\) 和/3 が必要.これが整数になる必要がある. また, \(-2, 0, +2\) を置換したものと \((0,0,0)\) も含めると, 操作全体は群になる.
最終形
操作が可能な場合の最終形が確定したので, 次にそこに辿り着く方法を考える. 任意の \(i \in 3\) に対して \(d_{i} := abs(s-a[i])\) は偶数である必要がある.
最適戦略
次に,最適戦略の特徴を考える. \begin{align} (+2, 0, -2) \\ (-2, +2, 0) \end{align} の操作は, \((0,+2, -2)\) と言い換えてよい. また, \begin{align} (+2, 0, -2) \\ (-2, 0, +2) \end{align} の操作は, \((0,0,0)\) と言い換えてよい. 第一成分に注目すれば, ある最適解であって, 同じ成分に \(+2,-2\) の両方の操作はしないものが存在する, という事になる.
よって各成分に対して, \(+2\) or \(-2\) を何回か施したものと考えればよい. これで操作の最小回数が分かる.
以上をまとめてコードにする.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"