ei1333の日記

ぺこい

Educational DP Contest

えー書きますぜんぶはかきません

J - Sushi

期待値DP

制約より、1個と2個と3個の寿司のそれぞれの皿の枚数を引数にしてDPすればいいことがわかる

F(one, two, three) := 現在1個と2個と3個の寿司のそれぞれの皿の枚数が one, two, three 枚のとき、すべて食べられるまでの回数の期待値とする.

F(one, two, three) = F(one, two+1, three-1) ${\times \frac {three} N}$ + F(one+1, two-1, three) ${\times \frac {two} N}$ + F(one-1, two, three) ${\times \frac {one} N}$ + F(one, two, three) ${\times \frac {N-{three}-{two}-{one}} N}$ + 1 になる.

自分に遷移しているものがあるのでこわれる.

移項すると (1 - ${\frac {N-{three}-{two}-{one}} N}$ ) F(one, two, three) = F(one, two+1, three-1) ${\times \frac {three} N}$ + F(one+1, two-1, three) ${\times \frac {two} N}$ + F(one-1, two, three) ${\times \frac {one} N}$ + 1 となって,

両辺を (1 - ${\frac {N-{three}-{two}-{one}} N}$ ) で割れば自分への遷移が消えるのでうまくDPできる.

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;
const int64 INF = 1LL << 59;
const int mod = 1e9 + 7;


int N;
bool memo[301][301][301];
double dp[301][301][301];


double rec(int a, int b, int c) {
  if(exchange(memo[a][b][c], true)) return dp[a][b][c];
  double ret = 0;

  int64 rest = N - (a + b + c);
  if(rest == N) return 0;

  if(a) ret += rec(a - 1, b, c) * a / N;
  if(b) ret += rec(a + 1, b - 1, c) * b / N;
  if(c) ret += rec(a, b + 1, c - 1) * c / N;

  return dp[a][b][c] = (ret + 1) / ((1.0 - ((double) rest / N)));
}

int main() {
  cin >> N;
  int a = 0, b = 0, c = 0;
  for(int i = 0; i < N; i++) {
    int x;
    cin >> x;
    if(x == 1) ++a;
    else if(x == 2) ++b;
    else ++c;
  }
  cout << fixed << setprecision(10) << rec(a, b, c) << endl;
}

K - Stones

rec(rest) を山の石が残り rest 個のとき勝てるとき true, 負ける時 false と定義するとおわり.

rec(rest - ${a_i}$ ) が false となるものがあれば rec(rest) は true.

#include <bits/stdc++.h>

using namespace std;

int N, K;
int A[100000];
int dp[100001];

bool rec(int rest) {
  if(~dp[rest]) return dp[rest];
  for(int i = 0; i < N; i++) {
    if(rest - A[i] < 0) continue;
    if(!rec(rest - A[i])) return dp[rest] = true;
  }
  return dp[rest] = false;
}

int main() {
  cin >> N >> K;
  for(int i = 0; i < N; i++) cin >> A[i];
  memset(dp, -1, sizeof(dp));
  if(rec(K)) cout << "First\n";
  else cout << "Second\n";
}

L - Deque

rec(l, r) を区間 ${[l, r]}$ の数列が残っていて自分の手番のとき、それ以降で可能な自分-相手の得点の最大値とする.

両端のいずれかをとってみて最大となるほうに遷移すればいいため.

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

int N;
int A[3000];
bool memo[3000][3000];
int64 dp[3000][3000];

int64 rec(int l, int r) {
  if(l > r) return 0;
  if(exchange(memo[l][r], true)) return dp[l][r];
  int64 ret = max(A[r] - rec(l, r - 1), A[l] - rec(l + 1, r));
  return dp[l][r] = ret;
}

int main() {
  cin >> N;
  for(int i = 0; i < N; i++) cin >> A[i];
  cout << rec(0, N - 1) << endl;
}

M - Candies

dp[idx][rest] := idx番目までに飴をrest個配り終えるわけかたとする.

idx+1番目を加える時、それぞれの dp[idx][i] を、dp[idx+1][i]～dp[idx+1][i+A[i]] に一様加算するみたいになっているのでいもす法で高速化する.

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;

int main() {
  int N, K;
  cin >> N >> K;
  vector< int > dp(K + 2);
  dp[0] = 1;
  for(int i = 0; i < N; i++) {
    vector< int > add_dp(K + 2);
    int x;
    cin >> x;
    for(int j = K; j >= 0; j--) {
      (add_dp[min(j + x + 1, K + 1)] += mod - dp[j]) %= mod;
      (add_dp[j] += dp[j]) %= mod;
    }
    for(int j = 1; j <= K; j++) {
      (add_dp[j] += add_dp[j - 1]) %= mod;
    }
    dp.swap(add_dp);
  }
  cout << dp[K] << endl;
}

N - Slimes

rec(l, r) を区間 l, r を1つにするための最小コストとする

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;
const int64 INF = 1LL << 59;

int64 N, A[401];
int64 dp[400][400];

int64 rec(int l, int r) {
  if(l == r) return 0;
  if(~dp[l][r]) return dp[l][r];
  int64 ret = INF;
  for(int i = l + 1; i <= r; i++) ret = min(ret, rec(l, i - 1) + rec(i, r) + A[r + 1] - A[l]);
  return dp[l][r] = ret;
}

int main() {
  cin >> N;
  for(int i = 0; i < N; i++) cin >> A[i + 1];
  for(int i = 1; i <= N; i++) A[i] += A[i - 1];
  memset(dp, -1, sizeof(dp));
  cout << rec(0, N - 1) << endl;
}

O - Matching

bitdp.

i人目をみるとき popcount が i-1 個たっているbitについてみればよい.

すると, それぞれみられるbitは1回なので ${O(n 2^n)}$ .

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

const int mod = 1e9 + 7;

int main() {
  int N, A[21][21];
  cin >> N;
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      cin >> A[i][j];
    }
  }
  vector< int64 > dp(1 << N);
  dp[0] = 1;
  vector< int > pop[22];
  for(int i = 0; i < (1 << N); i++) {
    pop[__builtin_popcount(i)].emplace_back(i);
  }
  for(int i = 0; i < N; i++) {
    for(auto &p : pop[i]) {
      for(int k = 0; k < N; k++) {
        if((p >> k) & 1) continue;
        if(A[i][k] == 0) continue;
        (dp[p | (1 << k)] += dp[p]) %= mod;
      }
    }
  }
  cout << dp.back() << endl;
}

P - Independent Set

木DPをすればいいため

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

const int mod = 1e9 + 7;

int N;
vector< int > g[100000];
int64 dp[100000][2];

void dfs(int idx, int par) {
  int64 latte = 1, malta = 1;
  for(auto &to : g[idx]) {
    if(to == par) continue;
    dfs(to, idx);
    (latte *= (dp[to][0] + dp[to][1]) % mod) %= mod;
    (malta *= dp[to][0]) %= mod;
  }
  dp[idx][0] = latte;
  dp[idx][1] = malta;
}

int main() {
  cin >> N;
  for(int i = 1; i < N; i++) {
    int x, y;
    cin >> x >> y;
    --x, --y;
    g[x].emplace_back(y);
    g[y].emplace_back(x);
  }
  dfs(0, -1);
  cout << (dp[0][0] + dp[0][1]) % mod << endl;
}

Q - Flowers

LISをすればいいため

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

const int mod = 1e9 + 7;

template< class T >
struct BinaryIndexedTree {
  vector< T > data;

  BinaryIndexedTree(int sz) {
    data.assign(++sz, 0);
  }

  T sum(int k) {
    T ret = 0;
    for(++k; k > 0; k -= k & -k) ret = max(ret, data[k]);
    return (ret);
  }

  void add(int k, T x) {
    for(++k; k < data.size(); k += k & -k) data[k] = max(data[k], x);
  }
};

int main() {
  int N, H[200000];
  cin >> N;
  vector< int > ex;
  for(int i = 0; i < N; i++) {
    cin >> H[i];
    ex.emplace_back(H[i]);
  }
  sort(begin(ex), end(ex));
  ex.erase(unique(begin(ex), end(ex)), end(ex));
  BinaryIndexedTree< int64 > bit(ex.size());
  int64 latte = 0;
  for(int i = 0; i < N; i++) {
    int c;
    cin >> c;
    H[i] = lower_bound(begin(ex), end(ex), H[i]) - begin(ex);
    auto ret = bit.sum(H[i] - 1) + c;
    latte = max(latte, ret);
    bit.add(H[i], ret);
  }
  cout << latte << endl;
}

R - Walk

隣接行列の ${K}$ 乗が答えなので

ライブラリは省略

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

const int mod = 1e9 + 7;

using modint = ModInt< mod >;

int main() {
  int N;
  int64 K;
  cin >> N >> K;
  Matrix< modint > mat(N);
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      cin >> mat[i][j];
    }
  }
  mat ^= K;
  modint uku(0);
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      uku += mat[i][j];
    }
  }
  cout << uku << endl;
}

S - Digit Sum

桁DPをすればいいため

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

const int mod = 1e9 + 7;

string K;
int D;

int64 dp[10000][100][2];

int64 rec(int idx, bool free, int sum) {
  if(idx == K.size()) return sum == 0;
  if(~dp[idx][sum][free]) return dp[idx][sum][free];
  int64 ret = 0;
  for(int i = free ? K[idx] - '0' : 9; i >= 0; i--) {
    ret += rec(idx + 1, free & (i == K[idx] - '0'), (sum + i) % D);
    ret %= mod;
  }
  return dp[idx][sum][free] = ret;
}

int main() {
  memset(dp, -1, sizeof(dp));
  cin >> K >> D;
  cout << (rec(0, true, 0) + mod - 1) % mod << endl;
}

T - Permutation

これむずかしくない？　むずかしいね

dp[idx][i] := idx番目まで決めたときに, idx番目の値より小さい値が ${i}$ 個残っている順列の個数とする. このとき idx番目の値より大きい値は (N-idx)- ${i}$ 個である.

いま idx+1番目の値を決めたいとする.

'<' のとき, idx番目の値より大きい値を使う必要があるので, dp[idx][i]についてのこっている (N-idx)- ${i}$ 個のうちいずれかの値を選ぶ. ここで ${j}$ 番目に大きい値を選んだ時, ${j}$ より小さい値の個数は ${i+j-1}$ 個みたいな感じになるので, dp[idx][i+j-1] に dp[i] を足せばよい.

'>' のときも同様.

これだと ${O(N^3)}$ になるんですが, M - Candies と同じ考え方でいもす法による加速が可能.

下の本番のコードは🐮ろからやってます.

#include<bits/stdc++.h>

using namespace std;

using int64 = long long;
const int INF = 1 << 30;
const int mod = 1e9 + 7;

int main() {
  int N;
  string S;
  cin >> N;
  cin >> S;
  vector< int > dp(N + 1);
  for(int i = N - 1; i >= 0; i--) dp[i] = 1;

  for(int i = N - 1; i > 0; i--) {
    vector< int > dp2(i + 5);
    for(int j = 0; j <= i; j++) {
      int up_count = j, down_count = i - j;
      if(S[i - 1] == '<') {
        (dp2[0] += dp[j]) %= mod;
        (dp2[up_count] += mod - dp[j]) %= mod;
      } else {
        (dp2[up_count] += dp[j]) %= mod;
        (dp2[up_count + down_count] += mod - dp[j]) %= mod;
      }
    }
    for(int j = 1; j < dp2.size(); j++) (dp2[j] += dp2[j - 1]) %= mod;
    dp.swap(dp2);
  }
  cout << accumulate(begin(dp), end(dp), 0LL) % mod << endl;
}

U - Grouping

制約を読むと ${O(3^N)}$ のDPをしなさいと書いてあるのでします.

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;
const int64 INF = 1LL << 60;

const int mod = 1e9 + 7;

int64 A[16][16];
int64 cost[1 << 16];
int64 dp[1 << 16];
bool memo[1 << 16];

int64 rec(int bit) {
  if(exchange(memo[bit], true)) return dp[bit];
  int64 ret = cost[bit];
  for(int i = bit; i > 0; i = (i - 1) & bit) {
    if(i == bit) continue;
    int other = i ^bit;
    ret = max(ret, rec(i) + rec(other));
  }
  return dp[bit] = ret;
}

int main() {
  int N;
  cin >> N;
  for(int i = 0; i < N; i++) {
    for(int j = 0; j < N; j++) {
      cin >> A[i][j];
    }
  }
  for(int i = 0; i < (1 << N); i++) {
    for(int j = 0; j < N; j++) {
      for(int k = j; k < N; k++) {
        if((i >> j) & 1 && (i >> k) & 1) cost[i] += A[j][k];
      }
    }
  }
  cout << rec((1 << N) - 1) << endl;
}

V - Subtree

ei1333.hateblo.jp

を貼ります.

逆元で閉じていない場合は, いつものアレじゃできなくて, こっちを使う必要があるんでつね.

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;
const int64 INF = 1LL << 60;

const int mod = 1e9 + 7;

template< typename Data, typename T >
struct ReRooting {

  struct Node {
    int to, rev;
    Data data;
  };

  using F1 = function< T(T, T) >;
  using F2 = function< T(T, int, int, Data) >; // ret, src, to, data

  vector< vector< Node > > g;
  vector< vector< T > > ldp, rdp;
  vector< int > lptr, rptr;
  const F1 f1;
  const F2 f2;
  const T ident;

  ReRooting(int n, const F1 &f1, const F2 &f2, const T &ident) :
      g(n), ldp(n), rdp(n), lptr(n), rptr(n), f1(f1), f2(f2), ident(ident) {}

  void add_edge(int u, int v, const Data &d) {
    g[u].emplace_back((Node) {v, (int) g[v].size(), d});
    g[v].emplace_back((Node) {u, (int) g[u].size() - 1, d});
  }

  T dfs(int idx, int par) {

    while(lptr[idx] != par && lptr[idx] < g[idx].size()) {
      auto &e = g[idx][lptr[idx]];
      ldp[idx][lptr[idx] + 1] = f1(ldp[idx][lptr[idx]], f2(dfs(e.to, e.rev), idx, e.to, e.data));
      ++lptr[idx];
    }
    while(rptr[idx] != par && rptr[idx] >= 0) {
      auto &e = g[idx][rptr[idx]];
      rdp[idx][rptr[idx]] = f1(rdp[idx][rptr[idx] + 1], f2(dfs(e.to, e.rev), idx, e.to, e.data));
      --rptr[idx];
    }
    if(par < 0) return rdp[idx][0];
    return f1(ldp[idx][par], rdp[idx][par + 1]);
  }

  vector< T > solve() {
    for(int i = 0; i < g.size(); i++) {
      ldp[i].assign(g[i].size() + 1, ident);
      rdp[i].assign(g[i].size() + 1, ident);
      lptr[i] = 0;
      rptr[i] = (int) g[i].size() - 1;
    }
    vector< T > ret;
    for(int i = 0; i < g.size(); i++) {
      ret.push_back(dfs(i, -1));
    }
    return ret;
  }
};

int main() {
  int N, M;
  cin >> N >> M;
  auto f1 = [&](int64 a, int64 b) {
    return a * b % M;
  };
  auto f2 = [&](int64 a, int64 b, int c, int64 d) {
    return (a + 1) % M;
  };
  ReRooting< int64, int64 > tap(N, f1, f2, 1);
  for(int i = 1; i < N; i++) {
    int x, y;
    cin >> x >> y;
    --x, --y;
    tap.add_edge(x, y, 1);
  }
  auto ret = tap.solve();
  for(auto &p :ret) cout << p << endl;
}

W - Intervals

実　家　の　よ　う　な　安　心　感

とりあえず区間はその区間の右端で処理することにすると, 左から見ていった時に最後に現れた 1 の場所が分かればよさげなことがわかる.

dp[idx][last] を idx番目まで文字列を決めたとき, 最後に現れた 1 の場所が last のときのスコアの最大値とする.

idx番目での処理としては, 1を使う時には dp[idx-1][0]～dp[idx][idx-1] の最大値, 0を使うときには dp[idx-1][i] の値をそのまま dp[idx][i] に持ってこればよい.

次に idxを右端とする区間 [l,idx] それぞれについて, dp[idx][l]～dp[idx][idx] にその区間のコストを加算する.

えー区間加算と区間maxができるセグメント木があればよいので

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;
const int64 INF = 1LL << 58;

template< typename Monoid, typename OperatorMonoid = Monoid >
struct LazySegmentTree {
  using F = function< Monoid(Monoid, Monoid) >;
  using G = function< Monoid(Monoid, OperatorMonoid) >;
  using H = function< OperatorMonoid(OperatorMonoid, OperatorMonoid) >;
  using P = function< OperatorMonoid(OperatorMonoid, int) >;

  int sz;
  vector< Monoid > data;
  vector< OperatorMonoid > lazy;
  const F f;
  const G g;
  const H h;
  const P p;
  const Monoid M1;
  const OperatorMonoid OM0;


  LazySegmentTree(int n, const F f, const G g, const H h, const P p,
                  const Monoid &M1, const OperatorMonoid OM0)
      : f(f), g(g), h(h), p(p), M1(M1), OM0(OM0) {
    sz = 1;
    while(sz < n) sz <<= 1;
    data.assign(2 * sz, M1);
    lazy.assign(2 * sz, OM0);
  }

  void set(int k, const Monoid &x) {
    data[k + sz] = x;
  }

  void build() {
    for(int k = sz - 1; k > 0; k--) {
      data[k] = f(data[2 * k + 0], data[2 * k + 1]);
    }
  }

  void propagate(int k, int len) {
    if(lazy[k] != OM0) {
      if(k < sz) {
        lazy[2 * k + 0] = h(lazy[2 * k + 0], lazy[k]);
        lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]);
      }
      data[k] = g(data[k], p(lazy[k], len));
      lazy[k] = OM0;
    }
  }

  Monoid update(int a, int b, const OperatorMonoid &x, int k, int l, int r) {
    propagate(k, r - l);
    if(r <= a || b <= l) {
      return data[k];
    } else if(a <= l && r <= b) {
      lazy[k] = h(lazy[k], x);
      propagate(k, r - l);
      return data[k];
    } else {
      return data[k] = f(update(a, b, x, 2 * k + 0, l, (l + r) >> 1),
                         update(a, b, x, 2 * k + 1, (l + r) >> 1, r));
    }
  }

  Monoid update(int a, int b, const OperatorMonoid &x) {
    return update(a, b, x, 1, 0, sz);
  }


  Monoid query(int a, int b, int k, int l, int r) {
    propagate(k, r - l);
    if(r <= a || b <= l) {
      return M1;
    } else if(a <= l && r <= b) {
      return data[k];
    } else {
      return f(query(a, b, 2 * k + 0, l, (l + r) >> 1),
               query(a, b, 2 * k + 1, (l + r) >> 1, r));
    }
  }

  Monoid query(int a, int b) {
    return query(a, b, 1, 0, sz);
  }

  Monoid operator[](const int &k) {
    return query(k, k + 1);
  }
};


int main() {
  int N, M;
  cin >> N >> M;
  vector< pair< int, int > > ev[200001];

  for(int i = 0; i < M; i++) {
    int l, r, x;
    cin >> l >> r >> x;
    --l;
    --r;
    ev[r].emplace_back(l, x);
  }

  auto f = [](int64 a, int64 b) { return max(a, b); };
  auto g = [](int64 a, int64  b) { return a + b; };
  auto p = [](int64 a, int p) { return a; };

  LazySegmentTree< int64 > seg(N+1, f, g, g, p, 0, 0);
  for(int i = 0; i < N; i++) {
    seg.update(i, i + 1, seg.query(0, i));
    for(auto &p : ev[i]) seg.update(p.first, i + 1, p.second);
  }
  cout << seg.query(0, N+1) << endl;
}

X - Tower

まずソートをします(ソートしないと解けないため). 比較関数は, それっぽいやつを全探索で良い気がする.

あとは順番を木にせずに前からDPすればよくて, dp[重さの総和] := 総和の最大値.

#include<bits/stdc++.h>

using namespace std;

using int64 = long long;
const int INF = 1 << 30;

int main() {
  int N;

  cin >> N;
  vector< pair< pair< int, int >, int > > st(N);
  for(int i = 0; i < N; i++) {
    cin >> st[i].first.second >> st[i].first.first >> st[i].second;
  }
  sort(begin(st), end(st), [&](auto x, auto y) {
    return (x.first.first - y.first.second < y.first.first - x.first.second);
  });


  vector< int64 > dp(10002);
  int ret = 0;
  for(int i = 0; i < N; i++) {
    for(int j = st[i].first.first; j >= 0; j--) {
      int idx = min(j + st[i].first.second, 10001);
      dp[idx] = max(dp[idx], dp[j] + st[i].second);
    }
  }

  cout << *max_element(begin(dp), end(dp)) << endl;
}

Y - Grid 2

えーこれ教科書に載ってなかったっけ. ${O(N^2)}$ をします.

包除原理を考えると, 壁を偶数個通る経路-奇数個通る経路が答えです.

このような経路数はXでソート(Xが同じときはYでソート)すれば, 二項係数より求まるのでうしちゃん.

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;

template< int mod >
struct Combination {
  vector< int64_t > mfact, rfact;

  Combination(int sz) : mfact(sz + 1), rfact(sz + 1) {
    mfact[0] = 1;
    for(int i = 1; i < mfact.size(); i++) {
      mfact[i] = mfact[i - 1] * i % mod;
    }
    rfact[sz] = inv(mfact[sz]);
    for(int i = sz - 1; i >= 0; i--) {
      rfact[i] = rfact[i + 1] * (i + 1) % mod;
    }
  }

  int64_t fact(int k) const {
    return (mfact[k]);
  }

  int64_t pow(int64_t x, int64_t n) const {
    int64_t ret = 1;
    while(n > 0) {
      if(n & 1) (ret *= x) %= mod;
      (x *= x) %= mod;
      n >>= 1;
    }
    return (ret);
  }

  int64_t inv(int64_t x) const {
    return (pow(x, mod - 2));
  }

  int64_t P(int n, int r) const {
    if(r < 0 || n < r) return (0);
    return (mfact[n] * rfact[n - r] % mod);
  }

  int64_t C(int p, int q) const {
    if(q < 0 || p < q) return (0);
    return (mfact[p] * rfact[q] % mod * rfact[p - q] % mod);
  }

  int64_t H(int n, int r) const {
    if(n < 0 || r < 0) return (0);
    return (r == 0 ? 1 : C(n + r - 1, r));
  }
};

int main() {
  int H, W, N;
  cin >> H >> W >> N;
  vector< pair< int, int > > ev;
  Combination< mod > uku(H + W);
  ev.emplace_back(0, 0);
  for(int i = 0; i < N; i++) {
    int y, x;
    cin >> y >> x;
    --y, --x;
    ev.emplace_back(y, x);
  }
  ev.emplace_back(H - 1, W - 1);

  sort(begin(ev), end(ev));
  N += 2;
  vector< int64 > dp1(N);
  vector< int64 > dp2(N);
  dp2[0] = 1;
  for(int i = 1; i < N; i++) {
    for(int j = i - 1; j >= 0; j--) {
      if(ev[i].second >= ev[j].second) {
        auto c = uku.C(ev[i].first - ev[j].first + ev[i].second - ev[j].second, ev[i].first - ev[j].first);

        dp1[i] += dp2[j] * c % mod;
        dp2[i] += dp1[j] * c % mod;
        dp1[i] %= mod;
        dp2[i] %= mod;
      }
    }
  }

  cout << (dp1.back() + mod - dp2.back()) % mod << endl;
}

Z - Frog 3

問題文にCHTをしなさいと書いてあるので, CHTをします.

${(h_j - h_i)^2 + C}$ を展開すると, ${-2 h_i h_j + h_j^2 + h_i^2 + C}$ になります.

この形をみると一次式になっていて, おわりなので.

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;
const int64 INF = 1LL << 60;

const int mod = 1e9 + 7;

template< class T >
struct ConvexHullTrickAddQueryMonotone {
  deque< pair< T, T > > L;
  int isdec;

  ConvexHullTrickAddQueryMonotone() : isdec(-1) {}

  inline T getX(const pair< T, T > &a, const T &x) {
    return (a.first * x + a.second);
  }

  inline bool check(const pair< T, T > &a, const pair< T, T > &b, const pair< T, T > &c) {
    return ((b.first - a.first) * (c.second - b.second) >= (b.second - a.second) * (c.first - b.first));
  }

  inline bool empty() { return (L.empty()); }

  void add(T a, T b) {
    pair< T, T > line(a, b);

    if(isdec == -1 && !L.empty()) {
      if(a < L[0].first) isdec = 1;
      else if(a > L[0].first) isdec = 0;
    }

    if(isdec == 1) {
      if(!L.empty() && L.back().first == a) {
        line.second = min(line.second, L.back().second);
        L.pop_back();
      }
      while(L.size() >= 2 && check(L[L.size() - 2], L.back(), line)) L.pop_back();
      L.emplace_back(line);
    } else {
      if(!L.empty() && L.front().first == a) {
        line.second = min(line.second, L.front().second);
        L.pop_front();
      }
      while(L.size() >= 2 && check(line, L[0], L[1])) L.pop_front();
      L.emplace_front(line);
    }
  }

  T getMinimumQuery(T x) {
    int low = -1, high = (int) L.size() - 1;
    while(high - low > 1) {
      int mid = (low + high) >> 1;
      if((getX(L[mid], x) >= getX(L[mid + 1], x))) low = mid;
      else high = mid;
    }
    return (getX(L[high], x));
  }

  T getMinimumQueryMonotone(T x) {
    while(L.size() >= 2 && getX(L[0], x) >= getX(L[1], x)) {
      L.pop_front();
    }
    return (getX(L[0], x));
  }
};


int main() {
  int N;
  int64 C;
  int64 H[200000];

  scanf("%d %lld", &N, &C);
  for(int i = 0; i < N; i++) scanf("%lld", &H[i]);
  ConvexHullTrickAddQueryMonotone< int64 > conv;
  conv.add(-2 * H[0], H[0] * H[0]);
  for(int i = 1; i < N; i++) {
    int64 uku = conv.getMinimumQueryMonotone(H[i]) + H[i] * H[i] + C;
    if(i + 1 == N) printf("%lld\n", uku);
    else conv.add(-2 * H[i], uku + H[i] * H[i]);
  }
}