Codeforces Round #780 (Div. 3)

# はじめに

バチャの記録です

記録は $0$ ペナ全完

でもレート下がってしまった悲しい

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/604564/29a22d51-c168-aeb5-9029-f26c5a1cbd3d.png)

# 本文

## [A. Vasya and Coins](https://codeforces.com/contest/1660/problem/A)

### 概要

$1$ 円玉 $a$ 枚 と $2$ 円玉 $b$ 枚がある

ぴったり払うことができない値段の最小値を求めよ

### 解法

$1$ 円玉が $1$ 枚もなければ $1$ 円が作れない

$1$ 枚でもあれば $ {}^\forall n \in [1,a + 2b]$ 円が作れる

```c++
int main() {
  int t; cin >> t;
  while(t--){
    int a, b; cin >> a >> b;
    if(a == 0) cout << 1 << "\n";
    else cout << a + b*2 + 1 << "\n";
  }
}
```

[提出コード](https://github.com/Suu0313/competitive-programing-submissions/blob/main/Codeforces/Div3/780/780_a.cpp)

## [B. Vlad and Candies](https://codeforces.com/contest/1660/problem/B)

### 概要

$n$ 種類の飴がある

残っている数が最も多いものを食べる ということを繰り返してすべての飴を食べるとき, 同じ種類の飴を二回連続で食べないようにすることはできるか

ただし, 残っている数が最も多いもの が複数ある時は好きなものを選んでよい

### 解法

$n = 1$ のときは明らか 以降 $n \ge 2$ とする

残っている数が最も多いもの と 二番目に多いもの の差が $2$ 以上なら明らかに不可能

逆に, そうでなければ交互に食べていくことで連続せずに減らすことができる

```c++
int main() {
  int t; cin >> t;
  while(t--){
    int n; cin >> n;
    vector<int> a(n); for(auto&&e : a) cin >> e;
    sort(rbegin(a), rend(a));
    auto f = [&]{
      if(n == 1) return a[0] <= 1;
      return a[0] <= a[1]+1;
    };
    cout << (f()? "YES" : "NO") << "\n";
  }
}
```

[提出コード](https://github.com/Suu0313/competitive-programing-submissions/blob/main/Codeforces/Div3/780/780_b.cpp)

ソートしたあと後ろに $0$ をくっつけておけば場合分けいらなかったな とこれを書きながら思った

## [C. Get an Even String](https://codeforces.com/contest/1660/problem/C)

### 概要

同じ文字を二つ並べたもの を好きな数連結したものを __Even String__ と呼ぶ

文字列 $s$ を Even String にするために削除しなければいけない文字数の最小値を求めよ

### 解法

逆に, どれだけ長い Even String を作れるか を考える

これは, 前から見て行って貪欲に使えるだけ使うのがいい (スルーすることでより多く使えるようになることはないため)

$26$ 種しかないので int の bit を立ててフラグ管理した

```c++
int main() {
  int t; cin >> t;
  while(t--){
    string s; cin >> s;
    int ans = int(s.size()), pre = 0;

    for(auto&&c : s){
      if(pre >> (c - 'a') & 1) pre = 0, ans -= 2;
      else pre |= 1 << (c - 'a');
    }

    cout << ans << "\n";
  }
}
```

[提出コード](https://github.com/Suu0313/competitive-programing-submissions/blob/main/Codeforces/Div3/780/780_c.cpp)

## [D. Maximum Product Strikes Back](https://codeforces.com/contest/1660/problem/D)

### 概要

長さ $n$ の整数列 $a$ が与えられる 各要素は $|a _ i| \le 2$ である

この数列の連続する部分列のうち, 要素の積が最大となるものを一つ求めよ

ただし, 要素数 $0$ のときは $1$ とする

### 解法

めちゃくちゃめんどくさい

$0$ を使ってしまうと何をしても $0$ なので, $0$ で区切ってそれぞれ考える

符号 と $2$ の数 を保存しておいて, 符号が $+$ なら全部使えばいい

そうでなければ, $-$ であるような要素の中で一番左 or 一番右 までを削る必要がある

ということを尺取りみたいに書けば線形時間で解ける

```c++
int main() {
  int t; cin >> t;
  while(t--){
    int n; cin >> n;
    vector<int> a(n); for(auto&&e : a) cin >> e;
    int ans = 0, x = n, y = 0;
    a.push_back(0);

    for(int l = 0, r = 0; l < n; l = r){
      while(l < n && a[l] == 0) ++l;
      if(l == n) break;
      r = l;
      while(a[r] != 0) ++r;
      int sgn = 1, cnt = 0, ln = -1, rn = -1, cl = 0, cr = 0;

      for(int i = l; i < r; i++){
        if(abs(a[i]) == 2){
          ++cnt;
          if(ln == -1) ++cl;
          ++cr;
        }
        if(a[i] < 0){
          sgn = -sgn;
          if(ln == -1) ln = i;
          rn = i;
          cr = a[i] == -2;
        }
      }

      if(sgn == -1){
        if(cl < cr){
          if(cnt - cl > ans) ans = cnt - cl, x = ln + 1, y = n - r;
        }else{
          if(cnt - cr > ans) ans = cnt - cr, x = l, y = n - rn;
        }
      }else{
        if(cnt > ans) ans = cnt, x = l, y = n - r;
      }
    }

    cout << x << " " << y << "\n";
  }
}
```

[提出コード](https://github.com/Suu0313/competitive-programing-submissions/blob/main/Codeforces/Div3/780/780_d.cpp)

## [E. Matrix and Shifts](https://codeforces.com/contest/1660/problem/E)

### 概要

各要素が $0$ か $1$ であるような $n \times n$ 行列が与えられる

上下左右に巡回シフトする という操作を好きな回数行って $n \times n$ 単位行列にできるだけ一致させるとき, 一致してない要素数の最小値を求めなさい

### 解法

左に $k$ 回シフトする というのは 右に $n - k$ 回シフトする で代用できる 上も下で同様

また, 下に $k$ 回シフトしたときの答え は 左に $k$ 回シフトしたときの答え と同じである

結局, どこか一方向を選んで何回シフトするのかを全通り試せばよい


```c++
int main() {
  int t; cin >> t;
  while(t--){
    int n; cin >> n;
    vector a(n, vector(n, 0));
    int cnt = 0;

    for(int i = 0; i < n; i++){
      string s; cin >> s;
      for(int j = 0; j < n; j++) cnt += a[i][j] = s[j] - '0';
    }
    
    int ans = n + cnt;

    for(int i = 0; i < n; i++){
      int ncnt = 0;
      for(int j = 0; j < n; j++) ncnt += a[j][(i + j)%n];

      ans = min(ans, n + cnt - ncnt * 2);
    }

    cout << ans << "\n";
  }
}
```

[提出コード](https://github.com/Suu0313/competitive-programing-submissions/blob/main/Codeforces/Div3/780/780_e.cpp)

## F. Promising String

F1 と F2 に分かれていますが問題文は同じなのでまとめてあります

### 概要

$+$ と $-$ からなる文字列について, $+$ と $-$ の数が等しいとき その文字列は __balanced__ である と呼ぶ

さらに, 隣接する二つの $-$ を一つの $+$ で置換することでその文字列を balanced にすることができるとき, その文字列は __promising__ である と呼ぶ

長さ $n$ の文字列 $s$ が与えられる

$s$ の部分文字列で promising であるものの数を求めよ

#### [F1. Promising String (easy version)](https://codeforces.com/contest/1660/problem/F1)

- $1 \le t \le 500$
- $1 \le n \le 3000$

#### [F2. Promising String (hard version)](https://codeforces.com/contest/1660/problem/F2)

- $1 \le t \le 10^4$
- $1 \le n \le 2 \cdot 10^5$


### 解法

$+$ を $1$,  $-$ を $-1$ に置き換えた数列を考える

この数列のある連続した部分列が promising であることの必要十分条件を考える

必要条件として, 総和を $x$ としたとき $x \le 0$ かつ $3 \ | \ x$ というものが考えられる

$x > 0$ なら明らかに promising ではなく, 置換を一度すると $-1$ が二つ消えて $1$ が一つ増えるので総和が $3$ 増えるためである


逆に, これを満たすときは必ず promising である

$x = 0$ なら自明として, $x \le -3$ なら $-1$ が $1$ より $3$ つ以上多いがどう並べても $-1$ が隣接する場所ができるので, 置換を行うことができて総和を増やしていけるためである

区間和を累積和で考えると, 数列 $a$ について $a_i \ge a_j$ かつ $a_j-a_i$ が $3$ の倍数であるような $(i, j)$ の個数が分かればよい

これは Binary Indexed Tree を $3$ 本生やせば高速に数えられる

```c++
int main() {
  int t; cin >> t;
  while(t--){
    int n; cin >> n;
    string s; cin >> s;
    int sum = n;
    vector<BIT<int>> fw(3, n*2 + 1);
    fw[n%3].add(n, 1);
    int64_t ans = 0;

    for(auto&&c : s){
      sum += 44 - c;
      ans += fw[sum%3].query(sum, n*2 + 1);
      fw[sum%3].add(sum, 1);
    }

    cout << ans << "\n";
  }
}
```

[提出コード](https://github.com/Suu0313/competitive-programing-submissions/blob/main/Codeforces/Div3/780/780_f.cpp)

# おわりに

無駄に時間かかってしまったところも多かったけど実力的にそんなもんな気がする

証明ちゃんとしないで直感で投げてるのでそのうち痛い目を見そう