Codeforces Round #776 (Div. 3)

# はじめに

バチャの記録です

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

# 本文

## [A. Deletions of Two Adjacent Letters](https://codeforces.com/contest/1650/problem/A)

### 概要

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

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

### 解法

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

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

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

```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;
```

[提出コード](https://codeforces.com/contest/1650/submission/150089960)

## [B. DIV + MOD](https://codeforces.com/contest/1650/problem/B)

### 概要

整数 $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)$ が答え

```c++
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";
```

[提出コード](https://codeforces.com/contest/1650/submission/150044890)

## [C. Weight of the System of Nested Segments](https://codeforces.com/contest/1650/problem/C)

### 概要

数直線上の点が $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$ 個の点を選んで, 端っこ同士を対応させていけばよい

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

```c++
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";
```

[提出コード](https://codeforces.com/contest/1650/submission/150093783)

## [D. Twist the Permutation](https://codeforces.com/contest/1650/problem/D)

### 概要

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

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

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

### 解法

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

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

```c++
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";
```

[提出コード](https://codeforces.com/contest/1650/submission/150046626)

## [E. Rescheduling the Exam](https://codeforces.com/contest/1650/problem/E)

### 概要

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

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

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

### 解法

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

両方試せばよい

```c++
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";
```

[提出コード](https://codeforces.com/contest/1650/submission/150095374)

## [F. Vitaly and Advanced Useless Algorithms](https://codeforces.com/contest/1650/problem/F)

### 概要

$n$ 個のタスクがあり, それぞれ締め切りが決まっている

$m$ 個のオプションがあり, それぞれ $t$ 時間かけて $e$ 番目のタスクを $p$ % 進めることができる

好きなオプションを好きな順番で選ぶとき, すべてのタスクを締め切りに間に合わせることができるか判定し, 可能ならその方法を答えなさい

ただし, 同じタスクは高々一回しか選べない

### 解法

オプションがタスクごとに独立しているので, それぞれについて貪欲に最速で終わらせに行けばよい

タスクごとに $dp$ をして最小値を求める

復元が必要なせいで実装がめちゃくちゃ沼った

[提出コード](https://codeforces.com/contest/1650/submission/150053060)

## [G. Counting Shortcuts](https://codeforces.com/contest/1650/problem/G)

### 概要

$n$ 頂点 $m$ 辺の連結な単純無向グラフが与えられる

$s$ から $t$ へのパスのうち, 最短パスと距離の差が $1$ 以下であるものの数を求めなさい

### 解法

最短パスより短いなんてことはあり得ないので, 等しいか $+1$

頂点を倍化したグラフで bfs しながら数え上げればよい

[提出コード](https://codeforces.com/contest/1650/submission/150055399)

# おわりに

F で $dp$ を復元する必要があるのに in-place な書き方をしようとして無事死亡した

ペナこそなかったものの全体的に実装に時間をかけすぎた