ei1333の日記

ぺこい

Educational Codeforces Round 15

Codeforces

4つ通して88位.

A. Maximum Increase

問題概要

長さ {n} の数列 {a_i} が与えられる. 増加する連続部分列の最長の長さを求めよ.

解法

{O(N)} の貪欲. 前の数字と今の数字を比べて, 増加しているなら(今の長さ) {+ 1}, 増加していないなら {1} にすればよい.

ソース

#include<bits/stdc++.h>

using namespace std;

int main()
{
  int N;
  scanf("%d", &N);
  int pre = -1, cnt = 0, ret = 0;
  for(int i = 0; i < N; i++) {
    int A;
    scanf("%d", &A);
    if(pre < A) ++cnt;
    else cnt = 1;
    pre = A;
    ret = max(ret, cnt);
  }
  printf("%d\n", ret);
}

B. Powers of Two

問題概要

長さ {n} の数列 {a_i} が与えられる. {i \lt j} を満たすペアのうち, {a_i + a_j = 2^x} ( {x}は任意)となるペアの個数を求めよ.

解法

式を整理すると {a_i = 2^x - a_j}.

{j} 番目の要素を追加することを考える. {i \lt j} を満たす {i} の要素の数字の出現回数を map で保存しておく. {x} は任意なので全通り試すとすると, 整理した式より {a_i} は定数. よって, {a_i} の出現回数をそのまま足せば良い.

{O(N \log^2 {N})}.

ソース

うーlogの2乗だけあってTLEぎりぎり(2.3s).

#include<bits/stdc++.h>

using namespace std;

int main()
{
  int N;
  map< long long, int > cnt;
  long long ret = 0;

  scanf("%d", &N);
  for(int i = 0; i < N; i++) {
    int A;
    scanf("%d", &A);
    long long num = 1;
    for(int j = 0; j < 35; j++) {
      ret += cnt[num - A];
      num *= 2;
    }
    ++cnt[A];
  }
  cout << ret << endl;
}

C. Cellular Network

問題概要

直線上に {n} 個の街があって, それぞれ位置 {a_i} にある. また, 同じ直線上に {m} 個のタワーがあって, それぞれ位置 {b_i} にある. すべてのタワーは, そのタワーから距離 {r} 以内の街にネットワークを供給できる. すべての街にネットワークを供給するとき, {r} の最小値を求めよ.

解法

二分探索. 距離 {r = x} のとき条件を満たせるとき {r \ge x} も同様に満たすので二分探索できる.

距離 {x} のとき満たせるかの判定は尺取りすれば {O(N + M)}. タワーが街を囲む範囲は, タワーの座標が増えるに従って街の座標も単調増加することを考えて雰囲気で書くとよい.

{O((N + M) log N)}.

ソース

#include<bits/stdc++.h>

using namespace std;

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

  scanf("%d %d", &N, &M);
  for(int i = 0; i < N; ++i) {
    scanf("%d", &A[i]);
  }
  for(int i = 0; i < M; ++i) {
    scanf("%d", &B[i]);
  }

  auto able = [&](long long dist)
  {
    int head = 0;
    for(int i = 0; i < M; i++) {
      while(head < N && llabs((long long)B[i] - A[head]) <= dist) ++head;
    }
    return(head == N);
  };

  long long low = 0, high = 1LL << 40;
  while(high - low > 0) {
    long long mid = (low + high) / 2;
    if(able(mid)) high = mid;
    else low = mid + 1;
  }
  cout << low << endl;
}

D. Road to Post Office

問題概要

{d km} 離れた郵便局に向かう. 車を使うと {1 km} 進むのに {a} 秒かかる. {t} 秒ごとに故障する. 故障したら {k} 秒かけて直すことができる. 直したあとまた乗ることができる. 乗らない場合は車を捨てて歩くことになるが {1 km} 進むのに {b (\gt a)} 秒かかる. 最短到着時間を求めよ.

解法

何も考えないと三分探索したくなる.
さらに何も考えないと車を使う距離で三分探索したくなるがこれは多分ダメ. 平たい部分が出てきそう.
そこで, 車を何回修理して乗るかで三分探索する. 修理して乗る回数を決めれば歩く距離も定まり時間も計算できる. これは凸グラフ. 整数の三分探索は微分すると二分探索にできるのでそうする.

{O(log D)}.

ソース

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;

int main()
{
  int64 d, k, a, b, t;
  cin >> d >> k >> a >> b >> t;

  auto calc = [&](int64 value)
  {
    int64 carDist = min(d, value * k);
    int64 carTime = max(0LL, t * (value - 1) + carDist * a);
    int64 walkTime = (d - carDist) * b;
    return(carTime + walkTime);
  };

  int64 low = 0, high = (d + k - 1) / k + 1;
  while(high - low > 1) {
    int64 mid = (low + high) / 2;
    if(calc(mid) - calc(mid - 1) < 0) low = mid;
    else high = mid;
  }
  cout << calc(low) << endl;
}