Codeforces Round #364 (Div. 2)

ABCDを通した. まずまず. 1841 -> 1871(+30).

A. Cards

問題概要

${n (1 \le n \le 100)}$ 枚のカードがあって, ${a_1, a_2, ..., a_n (1 \le a_i \le 100)}$ の数字が書かれている.
${n / 2}$ 人のプレイヤーにカードを ${2}$ 枚ずつ分ける.
すべてのプレイヤーに分けられる ${2}$ 枚のカードの数字の和が等しくなるように分けるとき, そのような分け方を ${1}$ つ出力せよ. そのような分け方があることは保証されている.

解法

${(n}$ 枚のカードの和 ${/ (n / 2))}$ が 1 人に配布するカードの和になる. この和になるものを貪欲に取っていけば良い.

${O(\max(a_i) + N)}$ .

ソース

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

int main()
{
  int N, all = 0;
  vector< int > A[101];
  cin >> N;
  for(int i = 0; i < N; i++) {
    int X;
    cin >> X;
    A[X].push_back(i + 1);
    all += X;
  }
  all = all * 2 / N;
  for(int i = 1; i < 101; i++) {
    while(!A[i].empty()) {
      cout << A[i].back() << " ";
      A[i].pop_back();
      cout << A[all - i].back() << endl;
      A[all - i].pop_back();
    }
  }
}

B. Cells Not Under Attack

問題概要

${n \times n (1 \le n \le 10^5)}$ のチェスボードがある.

最初ボードには何も置かれていない. プレイヤーは ${m(1 \le m \le \min(10^5, n \times n))}$ 個のコマを順番に ${(x_i, y_i)}$ に配置していく.

あるセルに対し, 同じ行あるいは同じ列にコマがあるとき, そのセルが攻撃を受けていると定義する.

$m$ 回の配置の終了後それぞれに対し, まだ攻撃を受けていないセルは何個あるか出力せよ.

解法

ある行, 列が攻撃を受けているかと, 攻撃をされた行, 列の数を保存しておく.

するとあるセル ${(x_i, y_i)}$ にコマを置いた時, ${x_i}$ 方向に攻撃されたセルが増える量を考える.

${x_i}$ がまだ攻撃されていないとき, これは ${N -}$ (既に攻撃された列の数) となる.
${x_i}$ が攻撃済みのとき, 変化なし.

列も同様.

頑張って計算すると ${O(M)}$ .

ソース

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

bool row[100001], col[100001];
int ablecol, ablerow;

int main()
{
  int N, M;
  scanf("%d %d", &N, &M);
  long long null = 1LL * N * N;
  
  for(int i = 0; i < M; i++) {
    int X, Y;
    scanf("%d %d", &X, &Y);

    if(!row[X] && !col[Y]) {
      null -= N;
      null -= N;
      null += 1;
      null += ablerow;
      null += ablecol;
      ++ablerow;
      ++ablecol;
    } else if(!row[X]) {
      null -= N;
      null += ablecol;
      ++ablerow;
    } else if(!col[Y]) {
      null -= N;
      null += ablerow;
      ++ablecol;
    }
    row[X] = col[Y] = true;
    printf("%I64d ", null);
  }
}

They Are Everywhere

問題概要

長さ ${n(1 \le n \le 10^5)}$ のアルファベット小文字と大文字からなる文字列が与えられる. 文字列中に出現する文字の種類をすべて含む部分文字列のうち, 最短の長さを求めよ.

解法

部分文字列の開始始点を ${i}$ とすると, 終了地点は ${j}$ に一意に定まり, これは出現する文字がすべて現れた最初の位置であり ${O(n)}$ で計算できる.

開始地点を ${i + 1}$ とすると, 終了地点は ${k(j \le k)}$ となる. ${i}$ 番目の文字を ${1}$ 個減らして, 終了地点を ${j}$ の位置から再計算すれば良いので尺取りできる.

計算量に気をつけながら尺取りすれば ${O(N)}$ . こういう問題は, 実装によってコーナーケースが現れたりしそうなので注意.

ソース

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

int main()
{
  int N;
  string S;
  bool exist[256] = {};
  int id[256] = {};
  
  cin >> N;
  cin >> S;

  for(char& c : S) exist[c]++;
  int sz = 0;
  for(int i = 0; i < 256; i++) {
    if(exist[i]) id[i] = sz++;
  }

  vector< int > shake(sz, 0);
  int head = 0, pz = 0;
  int ret = 1 << 30;
  for(int i = 0; i < N; i++) {
    while(head < N && pz < sz) {
      const int idx = id[S[head]];
      if(shake[idx] == 0) ++pz;
      ++shake[idx];
      ++head;
    }
    if(pz == sz) ret = min(ret, head - i);
    --shake[id[S[i]]];
    if(shake[id[S[i]]] == 0) --pz;
  }
  cout << ret << endl;
}

D. As Fast As Possible

問題概要

${n(1 \le n \le 10 000)}$ 人が一斉に距離 ${l (1 \le l \le 10^9)}$ 離れた場所に速さ ${v_1}$ で向かう.

${k(1 \le k \le n)}$ 人定員のバスがあってそれぞれの人は高々 ${1}$ 回そのバスに乗って移動することができる. バスの速さは ${v_2 (1 \le v_1 \lt v_2 \le 10^9)}$ . 任意の位置で人を乗降させることができ, また降ろしたあと引き返してまた人を乗せることもできる.

バスを適切に使ったとき, 全員が最短で到着する最短時間を求めよ.

解法

まずバスには全員が乗ったほうが良い. よってバスが人を乗せる回数は ${\lceil n / k \rceil}$ .
最初の軍団をバスに乗せる距離を定めると, 2番目以降に乗る人々がバスに乗る距離が一意に定まる.
そうするとバスの動きがわかるので, シミュレーションする(言葉で説明するのがむずかしい.

兎にも角にもシミュレーションできれば, バスに乗せる距離と到着時間は雰囲気的に凸グラフになっているので三分探索できる.
実際には式を整理すれば ${O(1)}$ で求まるらしい.

ソース

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

int N, L, V1, V2, K;
int kaisu;

double check(double alpha)
{
  double x = 0, y = 0;
  for(int i = 0; i < kaisu; i++) {
    x = (-V2 * x + y - alpha) / (V1 - V2);
    y = V1 * x + alpha;
    if(i + 1 != kaisu) {
      x = (V2 * x + y) / (V1 + V2);
      y = V1 * x;
    }
  }
  if(y > L) return(1e18);
  return(x);
}

int main()
{
  cin >> N >> L >> V1 >> V2 >> K;
  kaisu = (N + K - 1) / K;
  double low = 0, high = 1e18;
  for(int i = 0; i < 400; i++) {
    double left = (low * 2 + high) / 3;
    double right = (low + high * 2) / 3;
    if(check(left) < check(right)) low = left;
    else high = right;
  }
  cout << fixed << setprecision(10) << check(low) << endl;
}

ei1333の日記

ぺこい

Codeforces Round #364 (Div. 2)

A. Cards

問題概要

解法

ソース

B. Cells Not Under Attack

問題概要

解法

ソース

They Are Everywhere

問題概要

解法

ソース

D. As Fast As Possible

問題概要

解法

ソース