CADDi 2018 E - Negative Doubling - ferinの競プロ帳

解法

最終的な列はマイナスとプラスが ----/++++ のように並ぶはずである。したがってマイナスとプラスの区切り位置を決めると、+の列/-の列についてそれぞれ考えられる。符号が全て同じであれば4倍する操作を繰り返すと考えればよく、符号を無視できるので嬉しそう。
区間[i,n)を全て+にするときに必要な操作回数を考えるとj=i+1,…,n-1について順番に条件を満たすまで4倍する処理を繰り返せばよい。これを全ての区間に対して行うとO(N^2)かかるので高速化する必要がある。
dp1[i][j] = (A[i]にj回4倍する操作を行い区間[i,n)で条件を満たすような最小の操作回数) としてみる。dp1[i]をdp1[i+1]から高速に求めることができれば嬉しそう。この更新はdp1[i][j] = dp1[i+1][k] + j (kはa[i]*4^j <= a[i+1]*4^k を満たす最小のk) としてdpの遷移を書くことができ高速に求められる。ただしこのdpテーブルを普通に持とうとすると大きすぎてMLEやTLEになる。i番目に操作した回数が15回を超えると必ずmax(a[i])の値を超えることが10^9 < 4^15よりわかる。a[i]が10^9以上であれば[i,n)について隣接する要素が4倍以上離れることはありえない。したがってi番目に操作した回数がj回(j>=16)であればi+1番目以降にj-15回4倍することになる。つまりj>=16ではdp1[i][j] = dp1[i][15] + (j-15)*(n-i-1)として求めることができる。これによってdpテーブルがN*16程度で済むようになり時間内に求められる。
同様にマイナスが並ぶところについて考えるとdp2[i][j] = (A[i]にj回4倍する操作を行ったときの区間[0,i]で条件を満たすような最小の操作回数)とおいてDPをすればよい。dpの遷移はdp2[i][j] = dp2[i-1][k] + j (kはa[i-1]*4^k <= a[i]*4^j) とすればよい。
dpで持っていた値が-2倍ではなく4倍する操作の回数であること、最初に-2倍したことを考慮していないことを直す必要があることに注意する。[0,i]をマイナスに、[i,n)をプラスにしたときの必要な操作回数はmin(dp2[i][j]*2+i+1) + min(dp1[i+1][j]*2)となる。このうち最小のものが答えとなる。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<40;
const ll MOD = 1000000007;

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll n;
  cin >> n;
  vector<ll> a(n);
  REP(i, n) cin >> a[i];

  // dp1[i][j] = dp1[i+1][k] + j (a[i]*4^j <= a[i+1]*4^k を満たす最小のk)
  auto dp1 = make_v<ll>(n, 16);
  REP(i, 16) dp1[n-1][i] = i;
  for(ll i=n-2; i>=0; --i) {
    ll tmp = 1;
    REP(j, 16) {
      ll k = 0, t = 1;
      while(a[i] * tmp > a[i+1] * t) {
        t *= 4;
        k++;
      }
      if(k <= 15) dp1[i][j] = dp1[i+1][k] + j;
      else dp1[i][j] = dp1[i+1][15] + (k - 15) * (n - i - 1) + j;
      tmp *= 4;
    }
  }

  // REP(i, 16) {
  //   REP(j, n) cerr << dp1[j][i] << " ";
  //   cerr << endl;
  // }

  REP(i, n) a[i] *= -2;
  auto dp2 = make_v<ll>(n, 16);
  REP(i, 16) dp2[0][i] = i;
  FOR(i, 1, n) {
    ll tmp = 1;
    REP(j, 16) {
      ll k = 0, t = 1; 
      while(a[i-1] * t > a[i] * tmp) {
        t *= 4;
        k++;
      }
      if(k <= 15) dp2[i][j] = dp2[i-1][k] + j;
      else dp2[i][j] = dp2[i-1][15] + (k - 15) * i + j;
      tmp *= 4;
    }
  }

  // num1[i] = (区間[i,n)で最小の操作回数)
  vector<ll> num1(n, LLINF);
  // num2[i] = (区間[0,i]で最小の操作回数)
  vector<ll> num2(n, LLINF);
  REP(i, n) {
    REP(j, 16) {
      chmin(num1[i], dp1[i][j]*2);
      chmin(num2[i], dp2[i][j]*2+i+1);
    }
  }
  // cerr << num1 << endl << num2 << endl;

  ll ans = LLINF;
  chmin(ans, num1[0]);
  chmin(ans, num2[n-1]);
  REP(i, n-1) chmin(ans, num2[i] + num1[i+1]);
  cout << ans << endl;

  return 0;
}

コンテスト中はa[i]とa[i+1]との差分から必要になる操作回数の分[i+1,n)に操作すればよいと考えて1 5 4 16みたいなケースで16にまで4倍していて終了した…適当な考察をしない
ある条件で値が容易に定まるのでその部分を配列に持つ必要はないみたいなパターン