ei1333の日記

ぺこい

CSA Round #34 (Div. 2 only)

全完したので書く(ア

csacademy.com

Server Attack

問題概要

 {N(1 \le N \le 1000)} 個のクエリが与えられる.

  1. サーバーを時刻  {T_i} にダウンさせる
  2. サーバーを時刻  {T_i} に起動する.

サーバーがダウンしている時間の和を求めよ.

解法

なんかずっと意味不明誤読をしてて, 50 分くらいかけて解いた.

A 問題なので, はいをすると解ける.

ソース

ぜんぜん もんだいぶんを よんでなかった.

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

int main()
{
  int N, ret = 0;

  bool flag = false;
  int time = 0;

  cin >> N;
  for(int i = 0; i < N; i++) {
    int a, b;
    cin >> a >> b;
    if(a == 1) {
      if(!flag) {
        flag = true;
        time = b;
      }
    } else {
      if(flag) {
        ret += b - time;
        flag = false;
      }
    }
  }
  cout << ret << endl;
}

Choose the Price

問題概要

 {N(1 \le N \le 1000)} 人がいてクッキー  {1} 個ずつを買う.

ただし  {i} 番目の人はクッキーの値段が  {V_i(1 \le V_i \le 10^6)} を上回ると買わない.

クッキーの値段を自由に決められるとき, 売れるクッキーの値段の和の最大値を求めよ.

解法

最適なクッキーの値段の候補は  {N} 個の  {V_i} のなかのいずれかなので, それらを試すとできる.

 {O(N^2)}.

ソース

#include<bits/stdc++.h>

using namespace std;

int main()
{
  int N, A[1000];
  cin >> N;
  for(int i = 0; i < N; i++) cin >> A[i];

  int ret = 0;
  for(int i = 0; i < N; i++) {
    int beet = 0;
    for(int j = 0; j < N; j++) {
      if(A[i] <= A[j]) beet += A[i];
    }
    ret = max(ret, beet);
  }
  cout << ret << endl;
}

Max Or Subarray

問題概要

長さ  {N(1 \le N \le 10^5)} の数列  {A_i(0 \le A_i \lt 2^{30})} が与えられる.

bitwise ORが最大値となる連続部分列のうち, 最小の長さを求めよ.

解法

まあやる.

配列の全体は, bitwise OR の最大の1つ.

連続部分列はこの OR の値になればよくて, これは尺取りで出来るため勝ち.

尺の中の区間のbitごとの合計を持っておけばよい.

 {A_i} が全て  {0} のとき罠. 引っかかった.

ソース

絶対合ってるやろと思って同じソースを出して  {2} WAした(ダメ).

#include<bits/stdc++.h>

using namespace std;

int main()
{
  int N, A[100000];

  cin >> N;
  int ret = 0;
  for(int i = 0; i < N; i++) {
    cin >> A[i], ret |= A[i];
  }

  int sum[30] = {}, tail = 0;

  auto Dec = [&]()
  {
    for(int i = 0; i < 30; i++) {
      if(sum[i] == 0 && (ret >> i) & 1) return (true);
    }
    return (false);
  };

  int ans = N;
  for(int i = 0; i < N; i++) {
    while(tail < N && Dec()) {
      for(int j = 0; j < 30; j++) {
        sum[j] += (A[tail] >> j) & 1;
      }
      ++tail;
    }
    if(Dec()) break;
    ans = min(ans, tail - i);
    for(int j = 0; j < 30; j++) {
      sum[j] -= (A[i] >> j) & 1;
    }
  }
  cout << max(1, ans) << endl;
}

Minimize Max Diff

問題概要

長さ  {N(3 \le N \le 10^5)} の非減少の数列  {A_i(-10^9 \le A_i \le 10^9)} が与えられる.

 {K} 個の要素を削除できるとき, 隣接要素の差の最大値の最小値を求めよ.

解法

直感は二分探索. 差を  {v} 以下にするために必要な要素の削除数が求められれば良い.

消し方について考えると, 途中の要素を削除しても差が増えるだけなので先頭と末尾の連続する要素を削除するべきである.

逆を考えて差が  {v} 以下になる連続部分列の長さの最大値を求めるとえいできる. 貪欲に左から見ていけば良い.

 {O(N \log \max A_i)}.

ソース

なんか微妙に境界部分がバグったため悲しいデバッグをしてた.

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

int main()
{
  int64 N, K, A[100000];
  cin >> N >> K;
  for(int i = 0; i < N; i++) cin >> A[i];

  vector< int64 > sa;
  for(int i = 1; i < N; i++) sa.push_back(A[i] - A[i - 1]);

  int64 ng = -1, ok = 1LL << 40;
  while(ok - ng > 1) {
    int64 mid = (ok + ng) / 2;
    if([&]()
    {
      vector< int > iiyo;
      for(int i = 0; i < sa.size(); i++) {
        if(sa[i] <= mid) iiyo.push_back(i);
      }
      int ret = 0, last = 1;
      for(int i = 1; i < iiyo.size(); i++) {
        if(iiyo[i - 1] + 1 == iiyo[i]) {
          ++last;
        } else {
          ret = max(ret, last);
          last = 1;
        }
      }
      ret = max(ret, last);
      if(iiyo.empty()) return (N - ret <= K);
      return (N - ret - 1 <= K);
    }()) ok = mid;
    else ng = mid;
  }

  cout << ok << endl;
}

Point in Kgon

問題概要

 {N(4 \le N \le 10^5)} 頂点の凸多角形と, それに内包された点  {P} が与えられる.

凸多角形の頂点のうち  {K(3 \le K \lt N)} 個の頂点を選んで凸多角形を作る. このとき点  {P} は内包されている必要がある.

選び方の組み合わせを  {10^9 + 7} で割った余りで求めよ.

解法

内包されない選び方を数えてもよいので, そっちを数えてみる.

ある頂点  {i} を多角形の始点とすることとし, この点と点  {P} を通る直線をひいてみる. すると残りの点はどちらか一方(境界部分の点は両方) の領域に分けられる.

ぐっとにらむと両方の領域の点を同時に使うと点  {P} は多角形に内包されてしまうので, どちらか片側の領域の点のみを使って多角形を構成する必要があることがわかる.

これはがんばって尺取りしたりすると重複しないように数えられるため  {O(N)} で解ける(あんまり考えてなかったためにぶたんして  {O(N \log N)} だけどまあはい) (ccwを考えて, 時計回りと反時計回りの境界部分を探す)

ソース

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

const int mod = 1e9 + 7;

inline int64 modPow(int64 x, int64 n)
{
  if(n == 0) return (1);
  int64 ret = modPow(x, n / 2);
  (ret *= ret) %= mod;
  if(n & 1) (ret *= x) %= mod;
  return (ret);
}

inline int64 modInv(int64 a)
{
  return (modPow(a, mod - 2));
}

inline int64 modCombination(int p, int q)
{
  static int64 fact[202020], rfact[202020];
  if(fact[0] == 0) {
    fact[0] = rfact[0] = 1;
    for(int i = 1; i < 202020; i++) {
      fact[i] = fact[i - 1] * i % mod;
      rfact[i] = modInv(fact[i]);
    }
  }
  if(q < 0 || p < q) return (0);
  return (fact[p] * rfact[q] % mod * rfact[p - q] % mod);
}

struct Point
{
  int64 x, y;

  Point() {}

  Point(int64 x, int64 y) : x(x), y(y) {}


  Point operator-(const Point &p) const
  {
    return (Point(x - p.x, y - p.y));
  }

  int64 norm()
  {
    return (x * x + y * y);
  }
};

int64 cross(const Point &a, const Point &b)
{
  return a.x * b.y - a.y * b.x;
}

int64 dot(const Point &a, const Point &b)
{
  return a.x * b.x + a.y * b.y;
}

int ccw(const Point &a, Point b, Point c)
{
  b = b - a, c = c - a;
  if(cross(b, c) > 0) return +1;
  if(cross(b, c) < 0) return -1;
  if(dot(b, c) < 0) return +2;
  if(b.norm() < c.norm()) return -2;
  return 0;
}

int main()
{
  int64 N, K;
  Point d[100000], p;

  cin >> N >> K;
  for(int i = 0; i < N; i++) {
    cin >> d[i].x >> d[i].y;
  }
  cin >> p.x >> p.y;

  int64 ret = 0;
  for(int i = 0; i < N; i++) {
    int low = i + 1, high = N;
    while(high - low > 0) {
      int mid = (low + high) >> 1;
      if(ccw(d[i], d[mid], p) <= 0) high = mid;
      else low = mid + 1;
    }
    if(low < N) {
      (ret += modCombination(N - low + i, K - 1)) %= mod;
      if(i >= K - 1) {
        (ret += mod - modCombination(i, K - 1)) %= mod;
      }
    }
    low = i, high = N - 1;
    while(high - low > 0) {
      int mid = (low + high + 1) >> 1;
      if(ccw(d[i], d[mid], p) >= 0) low = mid;
      else high = mid - 1;
    }
    if(i < low) {
      (ret += modCombination(low - i, K - 1)) %= mod;
    }
  }

  cout << (modCombination(N, K) - ret + mod) % mod << endl;


}