Codeforces Round #488 by NEAR (Div. 1)

英語読みにくくないですか？僕は読みにくかったです.

A. Two Squares

問題概要

座標軸に平行な正方形と、座標軸を45度傾けたものに平行な正方形が与えられる.

2つの正方形が交差しているか判定せよ.

解法

勇気があるので double で計算した幾何ライブラリを貼って提出できる.

交差する条件は、いずれかの辺同士が交差しているか、ある頂点が他の正方形内に含まれているかの2通り.

ソース

#include <bits/stdc++.h>

using namespace std;

/* 幾何ライブラリは省略 */

int main() {
  Polygon a(4), b(4);
  for(int i = 0; i < 4; i++) cin >> a[i];
  for(int i = 0; i < 4; i++) cin >> b[i];
  a = convex_hull(a);
  b = convex_hull(b);
  for(int i = 0; i < 4; i++) {
    for(int j = 0; j < 4; j++) {
      auto x = Segment(a[i], a[(i + 1) % 4]);
      auto y = Segment(b[j], b[(j + 1) % 4]);
      if(intersect(x, y)) {
        cout << "YES" << endl;
        return 0;
      }
    }
  }
  if(contains(a, b[0]) || contains(b, a[0])) {
    cout << "YES" << endl;
    return 0;
  }
  cout << "NO" << endl;
}

B. Open Communication

わかりません

C. Careful Maneuvering

問題概要

${x = 100}$ の直線上に ${n(1 \le n \le 60)}$ 個の敵がいて, それぞれの ${y}$ 座標は ${y_{1,1}, y_{1,2}, \dots, y_{1,n}}$ である.

また ${x = -100}$ の直線上に ${m(1 \le m \le 60)}$ 個の敵がいて, それぞれの ${y}$ 座標は ${y_{2,1}, y_{2,2}, \dots, y_{2,m}}$ である.

${x = 0}$ の直線上の好きな ${2}$ 箇所に目印を配置できる. それぞれの敵はこの ${2}$ つの目印に向けて同時にレーザーを発射する. レーザーに触れた宇宙船は破壊される.

目印をうまく配置した時, 破壊される敵の個数の最大値を求めよ.

解法

目印を置く候補は, ${x=100}$ の宇宙船のいずれかから ${x=-100}$ の宇宙船のいずれかに向けて結んだ直線の ${nm}$ 通りしかない.

愚直をすると, その目印を 2 つおくのに ${O(nmnm)}$ , それを置いたときに何個破壊されるかの判定に ${O(n+m)}$ かかって全体で ${O(nmnm(n+m))}$ となり微妙にTLEする.

ここで判定を高速化することを考える. それぞれの直線に対し前計算で, そこに目印を置いた時にどの敵が破壊されるかを計算していおく. ${n, m \le 60}$ なので, この情報を bit ごとに long long で格納する.

すると bit 演算で判定できるようになり, ${O(nmnm)}$ .

ソース

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

int main() {
  int N, M, latte[60], malta[60];

  cin >> N >> M;
  for(int i = 0; i < N; i++) cin >> latte[i];
  for(int i = 0; i < M; i++) cin >> malta[i];
  int best = 0;

  int64 aa[60][60] ={{}}, bb[60][60] = {{}};

  for(int i = 0; i < N; i++) {
    for(int j = 0; j < M; j++) {
      for(int m = 0; m < N; m++) {
        int dist1 = latte[m] + (latte[i] + malta[j]) - latte[m] * 2;
        for(int n = 0; n < M; n++) {
          if(dist1 == malta[n]) aa[i][j] |= 1LL << n;
        }
      }
      for(int m = 0; m < M; m++) {
        int dist1 = malta[m] - 2 * malta[m] + (latte[i] + malta[j]);
        for(int n = 0; n < N; n++) {
          if(dist1 == latte[n]) bb[i][j] |= 1LL << n;
        }
      }
    }
  }

  for(int i = 0; i < N; i++) {
    for(int j = 0; j < M; j++) {
      for(int k = 0; k < N; k++) {
        for(int l = 0; l < M; l++) {
          best = max(best, __builtin_popcountll(aa[i][j] | aa[k][l]) + __builtin_popcountll(bb[i][j] | bb[k][l]));
        }
      }
    }
  }

  cout << best << endl;
}

D. Compute Power

問題概要

${n(1 \le n \le 50)}$ 個のタスクがあって, それぞれのタスクの電力消費量は ${a_i(1 \le a_i \le 10^8)}$ , 必要なプロセッサは ${b_i(1 \le b_i \le 100)}$ 個である.

コンピュータが十分な個数あり, それぞれのコンピュータにタスクを 1～2 個割り当てる. ここで電力消費量は 1 個目のタスクよりも 2 個目のタスクが少ない必要がある.

1回目のタスクについて、プロセッサあたりの平均電力消費量を最小化せよ. ここで, プロセッサあたりの平均電力は, (電力消費量の和)/(プロセッサの個数の和) である.

解法

平均値の最小化 → 二分探索したくない？したくない？めっちゃしたい

解の二分探索をするとして, 平均値が ${x}$ 以下かどうかを判定できればよい.

${c_i = a_i - b_i x}$ とおく. 平均値が ${x}$ 以下というのは, タスクを割り当てたときに1個目のタスクの ${c_i}$ の和が ${0}$ 以下であることと同値である.

このような割り当て方が存在するかどうかはDPで求めることができる. タスクを事前に ${a_i}$ を昇順に並び替えておく. 状態として, これまでに1個目に割り当てた電力が ${a_i}$ より小さいタスクの個数, 1個目に割り当てた電力が ${a_i}$ と一致するのタスクの個数, 2個目に割り当てたタスクの個数を持っておいて, 最後に電力消費量の和の最小値が ${0}$ 以下であるか判定すれば良い. このDPは $O(n^3)$ なのでまあ余裕.

ソース

よくあるテクの組み合わせで解ける問題.

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

int64 dp[51][51][51];

int main() {
  int64 N, A[51], B[51];
  cin >> N;
  vector< pair< int, int > > vs(N);
  for(int i = 0; i < N; i++) cin >> vs[i].first;
  for(int i = 0; i < N; i++) cin >> vs[i].second;
  sort(begin(vs), end(vs));
  reverse(begin(vs), end(vs));
  for(int i = 0; i < N; i++) tie(A[i], B[i]) = vs[i];
  A[N] = -1;

  int64 low = 0, high = 1000000000000LL;

  auto check = [&](int64 v) {
    vector< int64 > C(N);
    for(int i = 0; i < N; i++) {
      C[i] = A[i] * 1000LL - B[i] * v;
    }
    memset(dp, -1, sizeof(dp));
    function< int64(int, int, int) > rec = [&](int first, int firstsame, int last) {
      int idx = first + firstsame + last;
      if(idx == N) return 0LL;
      if(~dp[first][firstsame][last]) return dp[first][firstsame][last];
      int64 ret = 1LL << 60;
      if(first > last) {
        if(A[idx] != A[idx + 1]) ret = min(ret, rec(first + firstsame, 0, last + 1));
        else ret = min(ret, rec(first, firstsame, last + 1));
      }
      if(A[idx] != A[idx + 1]) ret = min(ret, rec(first + firstsame + 1, 0, last) + C[idx]);
      else ret = min(ret, rec(first, firstsame + 1, last) + C[idx]);
      return dp[first][firstsame][last] = ret;
    };
    return rec(0, 0, 0) <= 0;
  };
  while(high - low > 1) {
    int64 mid = (low + high) / 2;
    if(check(mid)) high = mid;
    else low = mid;
  }
  cout << high << endl;
}

E. Nikita and Order Statistics

問題概要

長さ ${n}$ の数列 ${a_i(-10^9 \le a_i \le 10^9)}$ と定数 ${X(-10^9 \le X \le 10^9)}$ が与えられる.

それぞれの ${k(0 \le k \le n)}$ について, ${X}$ 未満の値がちょうど ${k}$ 個含まれるような連続する部分列の個数を求めよ.

解法

実家っぽくない？実家だね.

まず ${0}$ 個含まれる部分列の個数は自明なので, 別で求めておくこととして, ${1}$ 以上の ${k}$ について考える.

するとここで分割統治したいという感情が突然芽生えるので, 分割統治をする.

すると, 区間 ${[l, r)}$ の部分列の中で, ${m = \frac {l + r} 2}$ を跨ぐものについてだけ考えればよくなる.

${m}$ より左側の各要素は部分列の始点になる. ${X}$ 未満の値の左側につづく ${X}$ 以上の値を持つ位置をみると, そのどこから始めても ${k}$ の個数は変化しないのでその個数 ( ${a_i}$ とする) だけ保存して圧縮できる(伝わって).

${m}$ より右側の各要素は部分列の終点になる. 同様に ${X}$ 未満の値の右側につづく ${X}$ 以上の値を持つ位置をみると, そのどこから始めても ${k}$ の個数は変化しないのでその個数 ( ${b_i}$ とする) だけ保存して圧縮できる.

ここで ${a_i}$ をreverseする. するとこのような圧縮した列は性質がよいことがわかり, その区間で ${m}$ を跨ぎ ${X}$ 未満の値がちょうど ${k}$ 個含む部分列の個数 ${c_k}$ は ${c_k = \sum_{k=i+j} a_{i} b_{j}}$ となる.

これはどうみても畳み込みなのでFFTをすればよい.

${O(n \log^2 n)}$ .

ソース

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

struct FastFourierTransform {
  using C = complex< double >;

  const double PI = acos(-1);
  vector< vector< C > > rts, rrts;

  void ensure_base(int N) {
    if(rts.size() >= N) return;
    rts.resize(N), rrts.resize(N);
    for(int i = 1; i < N; i <<= 1) {
      if(rts[i].size()) continue;
      rts[i].resize(i), rrts[i].resize(i);
      for(int k = 0; k < i; k++) {
        rts[i][k] = polar(1.0, PI / i * k);
        rrts[i][k] = polar(1.0, -PI / i * k);
      }
    }
  }

  void DiscreteFourierTransform(vector< C > &F, bool rev) {
    const int N = (int) F.size();
    auto &r = rev ? rrts : rts;

    for(int i = 0, j = 1; j + 1 < N; j++) {
      for(int k = N >> 1; k > (i ^= k); k >>= 1);
      if(i > j) swap(F[i], F[j]);
    }
    ensure_base(N);
    C s, t;
    for(int i = 1; i < N; i <<= 1) {
      for(int j = 0; j < N; j += i * 2) {
        for(int k = 0; k < i; k++) {
          s = F[j + k];
          t = C(F[j + k + i].real() * r[i][k].real() - F[j + k + i].imag() * r[i][k].imag(),
                F[j + k + i].real() * r[i][k].imag() + F[j + k + i].imag() * r[i][k].real());
          F[j + k] = s + t, F[j + k + i] = s - t;
        }
      }
    }
    if(rev) for(int i = 0; i < N; i++) F[i] /= N;
  }

  vector< long long > Multiply(const vector< int > &A, const vector< int > &B) {
    int sz = 1;
    while(sz < A.size() + B.size() - 1) sz <<= 1;
    vector< C > F(sz), G(sz);
    for(int i = 0; i < A.size(); i++) F[i] = A[i];
    for(int i = 0; i < B.size(); i++) G[i] = B[i];
    DiscreteFourierTransform(F, false);
    DiscreteFourierTransform(G, false);
    for(int i = 0; i < sz; i++) F[i] *= G[i];
    DiscreteFourierTransform(F, true);
    vector< long long > X(A.size() + B.size() - 1);
    for(int i = 0; i < A.size() + B.size() - 1; i++) X[i] = F[i].real() + 0.5;
    return (X);
  }
};

using int64 = long long;

vector< pair< int, int > > S;
FastFourierTransform fft;
int rest[200005];
int64 ans[200005];


void rec(int left, int right) {
  if(left + 1 >= right) {
    return;
  }
  int mid = (left + right) / 2;
  rec(left, mid);
  rec(mid, right);
  vector< int > latte(mid - left), malta(right - mid);
  for(int i = left; i < mid; i++) {
    latte[i - left] = rest[S[i].second];
  }
  reverse(begin(latte), end(latte));
  for(int i = mid; i < right; i++) {
    malta[i - mid] = S[i].first;
  }
  auto beet = fft.Multiply(latte, malta);
  for(int i = 0; i < beet.size(); i++) {
    ans[i + 2] += beet[i];
  }
}

int main() {
  int N, X, A[200000];

  cin >> N >> X;
  for(int i = 0; i < N; i++) {
    int x;
    cin >> x;
    A[i] = x < X;
  }


  for(int i = 0; i < N; i++) {
    int x = 0;
    for(int j = i; j < N; j++) {
      x += A[j];
    }
  }

  int pv = 0;
  for(int i = N - 1; i >= 0; i--) {
    ++pv;
    if(A[i] == 1) {
      S.emplace_back(pv, i);
      pv = 0;
    }
  }
  reverse(begin(S), end(S));

  pv = 0;
  for(int i = 0; i < N; i++) {
    ++pv;
    if(A[i] == 0) {
      ans[0] += pv;
    } else if(A[i] == 1) {
      rest[i] = pv;
      pv = 0;
    }
  }

  if(S.size()) {
    rec(0, S.size());
    for(int i = 0; i < S.size(); i++) {
      ans[1] += 1LL * S[i].first * rest[S[i].second];
    }
  }
  for(int i = 0; i <= N; i++) cout << ans[i] << " ";
  cout << endl;
}

ei1333の日記

ぺこい

Codeforces Round #488 by NEAR (Div. 1)

A. Two Squares

問題概要

解法

ソース

B. Open Communication

C. Careful Maneuvering

問題概要

解法

ソース

D. Compute Power

問題概要

解法

ソース

E. Nikita and Order Statistics

問題概要

解法

ソース