競技プログラミング日記

主に AtCoder の記事です

AtCoder Regular Contest 158A

ARC158A

操作の言い換え,不変量
等しい値にする事だけが重要なので,差を考えたほうが楽. \(+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"

int main() {
  ll t; cin >> t;
  rep(ti,t){
    vll a(3);
    cinv(a);

    ll s = 0;
    rep(i,3){
      s += a[i];
    }

    bool f = true;
    if(s % 3 != 0){
      f = false;
    }

    s /= 3;
    ll ma = -INFL;
    rep(i,3){
      ll d = abs(a[i] - s);
      chmax(ma, d);
      if(d % 2 != 0){
        f = false;
      }
    }

    ll ans = ma/2;

    if(!f) ans = -1;
    cout << ans << endl;
  }

  return 0;
}