競技プログラミング日記

主に AtCoder の記事です

AtCoder Regular Contest 135B

 

ARC135B

まず,漸化式に出てくる項を減らしたい.

\(a_{i} \geq 0\) の条件を無視する. \(S_{i}, S_{i+1}\) の変化を調べると, \(a_{i}, a_{i+3}\)だけが異なり,\(a_{i+1}, a_{i+2}\) は共通している. 式 \(-a_{i} + a_{i+3} = - S_{i} + S_{i+3}\) を得るので, 3つおきに \(a\) が決まることが分かる. \(a_{i}\) たちは, 基本的に\(i \ mod \ 3\) で分けて考えてよさそうで, \(a_{i}, i \ \in \ 3\) だけ決めれば残りは \(S\) から一意に決まる.

次に \(a_{i} \geq 0\) の条件を考える. \(a_{j}, j \ \in \ 3\) を決めると,
\(x_{j} := [ a_{j+k} \vert \ (k = 0, 3, 6, \cdots) ] \)
が決まるので, \(a_{j}\) を水増しして \(a_{j+k}\) が \(0\) 以上になるように 調整する. 暫定的に \(a_{j} = 0\) としてしまい, \(a_{j}\) を \(min(x_{j})\) で取り直せばよい.
ただし, \(a_{0} + a_{1} + a_{2} = S_{0}\) にしないといけないので, \(a_{0}, a_{1}\) を上の決め方をして, \(a_{2} := S_{0} - (a_{0} + a_{1})\) とする. ここで \(a_{2} \geq 0\) を満たしているのが, 条件を満たす \(a\) が取れる必要十分条件

使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {
  ll n;
  cin >> n;
  vll s(n);
  cinv(s);

  vll a(n+2);
  vll c(3);

  auto f = [&](vll sta) -> void {
    rep(j,3){
      ll mi;
      mi = a[j] = sta[j];
      for(ll i = 0; i+j+3 < n+2; i += 3){
        ll k = j + i;
        a[k+3] = a[k] - s[k] + s[k+1];
        chmin(mi, a[k+3]);
      }
      c[j] = max(0LL, -mi);
    }
   
  };
 
  f(c); // c = {0,0,0}

  ll sum = 0;
  rep(j,3){
    sum += c[j];
  }

  if(sum > s[0]){
    cout << "No" << endl;
    return 0;
  }else{
    c[2] = s[0] - (c[0] + c[1]);
    cout << "Yes" << endl;

    // 下駄cだけ求まれば,aは計算しなおす必要がない.
    rep(i,n+2){
      cout << a[i] + c[i%3] << " ";
    }

  }

  return 0;
}