Codeforces Round #353 Div2 C, D

C. Money Transfers

Problem - C - Codeforces

解法

合計すると0になる連続部分列をできるだけ多くすれば良い。

コード

#include <bits/stdc++.h>
using namespace std;

template <class T, class U>
void chmax(T &t, U f) {
  if (t < f) t = f;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector<int64_t> a(N);
  for (int i = 0; i < N; ++i) cin >> a[i];
  map<int64_t, int> dp;
  int64_t x = 0;
  for (int i = 0; i < N; ++i) {
    x += a[i];
    dp[x]++;
  }

  int ans = 0;
  for (const auto &p : dp) chmax(ans, p.second);
  cout << (N - ans) << endl;
}

D. Tree Construction

Problem - D - Codeforces

解法

すでにツリーに含まれる数字の中でa[i]より大きい最小の数字rとa[i]より小さい最大の数字lを取り出すと、a[i]の親はどちらか一方に必ず定まる。これはrがrより小さい子を持っているか、あるいはlがlより大きい子を持っているかによる。（必ずどちらか一方が成り立つ）

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i = 0; i < N; ++i) cin >> a[i];

  set<int> s;
  s.insert(a[0]);
  s.insert(a[1]);
  map<int, int> parent;
  parent[a[1]] = a[0];
  map<int, pair<int, int>> children;
  if (a[0] > a[1])
    children[a[0]] = {a[1], -1};
  else
    children[a[0]] = {-1, a[1]};

  for (int i = 2; i < N; ++i) {
    auto it = s.lower_bound(a[i]);
    if (it == s.begin()) {
      int r = *it;
      if (!children.count(r)) children[r] = {-1, -1};
      children[r].first = a[i];
      parent[a[i]] = r;
    } else if (it == s.end()) {
      it--;
      int l = *it;
      if (!children.count(l)) children[l] = {-1, -1};
      children[l].second = a[i];
      parent[a[i]] = l;
    } else {
      int r = *it;
      it--;
      int l = *it;
      if (children.count(l) && children[l].second != -1) {
        if (!children.count(r)) children[r] = {-1, -1};
        children[r].first = a[i];
        parent[a[i]] = r;
      } else if (children.count(r) && children[r].first != -1) {
        if (!children.count(l)) children[l] = {-1, -1};
        children[l].second = a[i];
        parent[a[i]] = l;
      } else {
        cerr << i << endl;
        assert(false);
      }
    }
    s.insert(a[i]);
  }
  for (int i = 1; i < N; ++i) {
    if (i > 1) cout << " ";
    cout << parent[a[i]];
  }
  cout << endl;
}