AtCoder 勉強記録[C++] その55

AtCoderで入茶を目指して勉強しています。
勉強を継続するために投稿を始めました。
もともとアカウントを作成していましたが、今年の4月から本格的に勉強を始めました。
一応自分用に解法を書いていますが雑です、自分で読み返して困ったら修正します。
[私のアカウント](https://atcoder.jp/users/nanami_brother)
[解いた問題](https://kenkoooo.com/atcoder/#/table/nanami_brother)
# 本日解いた問題
## B - Qualification Contest
[B - Qualification Contest](https://atcoder.jp/contests/abc288/tasks/abc288_b)
解答
```c++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define mod 998244353

int main() {
  ll n, k;
  cin >> n >> k;
  vector<string> s(n);
  rep(i, n) cin >> s[i];
  vector<string> res(k);
  for(int i = 0; i < k; i++){
    res[i] = s[i];
  }
  sort(res.begin(), res.end());
  rep(i, k) cout << res[i] << endl;
}
```
### 解法
`S`の要素を先頭から`K`個集めた配列を作成し、降順にソートすることで結果が求まる。
## B - レ
[B - レ](https://atcoder.jp/contests/abc289/tasks/abc289_b)
```c++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define mod 998244353

int main() {
  ll n, m;
  cin >> n >> m;
  vec a(m);
  rep(i, m) cin >> a[i];
  vector<bool> re(n+1, false);
  vec res;
  rep(i, m) re[a[i]] = true;
  for(int i = 1, j = 1; i <= n; i = ++j){
    while(re[j]) j++;
    for(int k = j; k >= i; k--){
      res.push_back(k);
    }
  }
  for(int x:res) cout << x << " ";
}
```
### 解法
レが挟まれている箇所を上手く逆順に出力することで結果が求まる。
## B - Qual B
[B - Qual B](https://atcoder.jp/contests/abc290/tasks/abc290_b)
解答
```c++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define mod 998244353

int main() {
  ll n, k;
  string s;
  cin >> n >> k >> s;
  ll cnt = 0;
  for(int i = 0; i < n; i++){
    if(cnt < k){
      if(s[i]=='o') cnt++;
    } else {
      if(s[i]=='o') s[i] = 'x';
    }
  }
  cout << s << endl;
}
```
### 解法
`S`に含まれる`o`の数をカウントし、3個以上の場合は`o`を`x`に置き換える。
## B - Trimmed Mean
[B - Trimmed Mean](https://atcoder.jp/contests/abc291/tasks/abc291_b)
解答
```c++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define mod 998244353

int main() {
  double n;
  cin >> n;
  vector<double> x(5*n);
  for(int i = 0; i < 5*n; i++){
    cin >> x[i];
  }
  sort(x.begin(), x.end());
  double avg = 0;
  for(int i = n; i < 4*n; i++){
    avg += x[i];
  }
  avg /= 3*n;
  cout << fixed << setprecision(15) << avg << endl;
}
```
### 解法
`X`の要素のうち、`N`から`4N`までの平均を求めることで結果が求まる。
## B - Yellow and Red Card
[B - Yellow and Red Card](https://atcoder.jp/contests/abc292/tasks/abc292_b)
解答
```c++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define mod 998244353

int main() {
  ll n, q;
  cin >> n >> q;
  vector<ll> pl(n+1, 0);
  for(int i = 0; i < q; i++){
    ll eve, x;
    cin >> eve >> x;
    if(eve == 1) pl[x]++;
    else if(eve == 2) pl[x] += 2;
    else {
      if(pl[x] >= 2) cout << "Yes" << endl;
      else cout << "No" << endl;
    }
  }
}
```
### 解法
選手に与えられたカードの数を入れておく配列`PL`を用意する。イベント1の場合は`PL[x]`の値を1つ増やす。イベント2の場合は`PL[x]`の値を2つ増やす。イベント3の場合は`PL[x]`の値が2以上の場合`Yes`を出力する。
## B - Call the ID Number
[B - Call the ID Number](https://atcoder.jp/contests/abc293/tasks/abc293_b)
解答
```c++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define mod 998244353

int main() {
  ll n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];
  vector<bool> ok(n, false);
  for(int i = 0; i < n; i++){
    if(!ok[i]) ok[a[i]-1] = true;
  }
  vector<ll> res;
  for(int i = 0; i < n; i++){
    if(!ok[i]) res.push_back(i+1);
  }
  cout << res.size() << endl;
  for(int x : res) cout << x << " ";
}
```
### 解法
生徒が呼ばれたかを判定するbool型配列を用意する。呼ばれた生徒を`True`としていき、最後にfalseの生徒と数をすべて出力することで結果が求まる。
## C - Index × A(Continuous ver.)
[C - Index × A(Continuous ver.)](https://atcoder.jp/contests/abc267/tasks/abc267_c)
解答
```c++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vec = vector<ll>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define mod 998244353

int main() {
  ll n, m;
   cin >> n >> m;
   vec a(n);
   rep(i, n) cin >> a[i];
   ll res = LLONG_MIN;
   vec sum(n+1,0);
   for(int i = 1; i <= n; i++){
     sum[i] = sum[i-1] + a[i-1];
   }
   vec sumb(n-m+1);
   ll tmp = 0;
   for(int i = 0; i < m; i++) tmp += a[i]*(i+1);
   sumb[0] = tmp;
   for(int i = 1; i <= n-m; i++){
     sumb[i] = sumb[i-1] + a[m+i-1]*m - (sum[m+i-1] - sum[i-1]);
   }
   for(int i = 0; i <= n-m; i++) res = max(res, sumb[i]);
   cout << res << endl;
}
```
### 解法
愚直に計算を行うと`O(MN)`となってしまい、実行時間オーバーとなってしまう。そのため、[解答](https://atcoder.jp/contests/abc267/editorial/4727)の式変形を用いることで結果が求まる。