More than 3 years have passed since last update.

Codeforces Round #776 (Div. 3)

Posted at 2022-03-19

はじめに

バチャの記録です

記録は $0$ ペナ全完結構実装沼ってしまった

本文

A. Deletions of Two Adjacent Letters

概要

奇数長の文字列 $s$ と文字 $c$ が与えられる

$s$ の隣接する二文字を削除するという操作を繰り返して $c$ だけが残るようにできるか判定しなさい

解法

偶数長の区間は消すことができる

$s$ に含まれる $c$ のうち, 左右のゴミの長さが偶数長のものが存在するかを判定すればよい

文字列は奇数長なので左側だけで十分

string s; cin >> s;
char c; cin >> c;
int n = int(s.size());

for(int i = 0; i < n; i += 2)
  if(s[i] == c) return true;

return false;

提出コード

B. DIV + MOD

概要

整数 $a$ が与えられる

関数 $f_a(x)$ を

$$ f_a(x) = \left\lfloor\dfrac{x}{a}\right\rfloor + (x \bmod a) $$

としたとき,

$$ \max_{x\in [l, r]\cap\mathbb{Z}} f_a(x) $$

を求めなさい

解法

明らかに $(x \bmod a)$ のほうを大きくしたい

$(x \bmod a) = a-1$ となるような $r$ 以下で最大の数が答え

しかしそのような $x$ が区間内に存在しない場合もある

その場合は単純に $f_a(r)$ が答え

int l, r, a; cin >> l >> r >> a;
auto f = [&](int x){ return x/a + x%a; };

cout << max(f(r), f(max(l, (r+1)/a * a - 1))) << "\n";

提出コード

C. Weight of the System of Nested Segments

概要

数直線上の点が $m$ 個与えられる

それぞれの点は異なる座標 $x_i$ に存在し, 重み $w_i$ を持っている

この中から $2n$ 個の点を選び, $n$ 個のペアを作る

$0 \le i < j < n$ で, 任意のペアの組 $(i_l, i_r), (j_l, j_r)$ について $[x_{i_l}, x_{i_r}] \supsetneq [x_{j_l}, x_{j_r}]$ が成立するようにペアを選ぶ

このとき, 選んだ点の重みの和の最小値を求めなさい

解法

難しそうなことを言っているが, これはギャグ

どんな $2n$ 個の点を選んでも, 条件を満たすペアを作れる

重みの小さいほうから貪欲に $2n$ 個の点を選んで, 端っこ同士を対応させていけばよい

キレイな実装が思いつかなかった

int n, m; cin >> n >> m;
vector<int> x(m), w(m), idx(m); iota(begin(idx), end(idx), 0);
for(int i = 0; i < m; ++i) cin >> x[i] >> w[i];

sort(begin(idx), end(idx), [&](int i, int j){ return w[i] < w[j]; });
sort(begin(w), end(w)); w.resize(n * 2); idx.resize(n * 2);
sort(begin(idx), end(idx), [&](int i, int j){ return x[i] < x[j]; });

cout << accumulate(begin(w), end(w), 0ll) << "\n";
for(int i = 0; i < n; ++i) cout << idx[i]+1 << " " << idx[n*2-i-1]+1 << "\n";
cout << "\n";

提出コード

D. Twist the Permutation

概要

数列 $a = (1, 2, \ldots, n)$ に対し, $n$ 回の操作をする

$i$ 回目の操作では, $[0, i]$ に対して任意のシフト幅で循環シフトをする

$n$ 回操作後の数列 $a$ が与えられるので, 対応する $n$ 回の操作を復元しなさい

解法

$i$ 回目の操作より前では $i$ 番目の要素を操作することができない

よって, 操作を後ろから見て, 毎回一番後ろの要素を合わせに行けばよい

int n; cin >> n;
vector<int> a(n);
for(auto&e : a){ cin >> e; --e; };
vector<int> res(n);

for(int i = n-1; i >= 0; --i){
  int j = 0;
  while(a[j] != i) ++j;

  res[i] = (j + 1) % (i + 1);
  if(res[i]) rotate(begin(a), begin(a)+j+1, begin(a)+i+1);
}
for(auto&e : res) cout << e << " ";
cout << "\n";

提出コード

E. Rescheduling the Exam

概要

今日から $d$ 日間のうち, $n$ 回テストがある

一つだけテストの日付をずらせるとき, テストとテストの間隔の最小値を最大化してください

ただし, ずらす先は $d$ 日間のどれかで, 他のテストとかぶせてはいけません

解法

明らかに, 間が一番詰まっている区間の両端のうちのどちらかを一番開いているところに入れるのが最適

両方試せばよい

int n, d; cin >> n >> d;
vector<int> a(n); for(auto&e : a) cin >> e;

auto f = [&](int i){
  if(i == -1) return 0;
  int x = a[i]; a.erase(begin(a) + i);

  valarray<int> ds(n-1); ds[0] = a[0] - 1;

  for(int i = 1; i < n-1; ++i) ds[i] = a[i] - a[i-1] - 1;
  int mx = max((ds.max() - 1)/2, d - a.back() - 1);

  a.insert(begin(a)+i, x);
  return min(mx, ds.min());
};

int mn = a[0], p = 0;
for(int i = 1; i < n; ++i){
  if(mn > a[i] - a[i-1]){
    mn = a[i] - a[i-1];
    p = i;
  }
}

cout << max(f(p), f(p-1)) << "\n";