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

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

int main() {
  ll n;
  cin >> n;
  string s;
  cin >> s;
  vector<pair<ll,char>> w(n);
  ll res = 0;
  rep(i, n) {
    cin >> w[i].first;
    w[i].second = s[i];
    if(s[i]=='1')  res++;
  }
  sort(w.begin(), w.end());
  ll x = res;
  for(int i = 0; i < n; i++){
    if(w[i].second=='1') x--;
    else x++;
    if(i<n-1){
      if(w[i].first!=w[i+1].first) res = max(res, x);
    }
    else res = max(res, x);
  }
  cout << res << endl;
}
```
### 解法
体重を昇順に並べ、初めは全ての人間を大人と判別する。昇順に左から右に子供と判別する人数を増やしていき、正しく判別できている人数で最大のものを出力する。
## C - Rotation
[C - Rotation](https://atcoder.jp/contests/abc258/tasks/abc258_c)
解答
```c++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vec = vector<int>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define mod 998244353

int main() {
  ll n, q;
  string s;
  cin >> n >> q >> s;
  ll t, x;
  ll sta = 0;
  for(int i = 0; i < q; i++){
    cin >> t >> x;
    if(t == 1) {
      sta -= x;
      if(sta < 0) sta += n;
    } else{
      ll tmp = sta+x-1;
      if(tmp >= n) tmp -= n;
      cout << s[tmp] << endl;
    }
  }
}
```
### 解法
愚直に文字列操作を行った場合計算量がオーバーしてしまう。そのため、文字列がループしていことに注目して、クエリ1の操作を行った際は文字列のスタート位置を変化させていると考える。クエリ2の場合に変化したスタート位置から考えて`x`番目の文字を出力することで正しい結果が得られる。
## C - XX to XXX
[C - XX to XXX](https://atcoder.jp/contests/abc259/tasks/abc259_c)
解答
```c++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vec = vector<int>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define mod 998244353

int main() {
  string s, t;
  cin >> s >> t;
  vector<pair<char, int>> ls;
  vector<pair<char, int>> lt;
  int cnt = 1;
  for(int i = 1; i < s.size();i++){
    if(s[i]!=s[i-1]){
      ls.push_back({s[i-1], cnt});
      cnt = 0;
    }
    cnt++;
  }
  ls.push_back({s.back(), cnt});
  cnt = 1;
  for(int i = 1; i < t.size();i++){
    if(t[i]!=t[i-1]){
      lt.push_back({t[i-1], cnt});
      cnt = 0;
    }
    cnt++;
  }
  lt.push_back({t.back(), cnt});
  if(ls.size() != lt.size()){
    cout << "No" << endl;
    exit(0);
  }
  bool jud = true;
  for(int i = 0; i < ls.size(); i++){
    if(ls[i].first != lt[i].first) jud = false;
    if(ls[i].second > 1 && lt[i].second <= 1) jud = false;
    if(lt[i].second > 1 && ls[i].second <= 1) jud = false;
    if(ls[i].second > lt[i].second) jud = false;
  }
  if(jud) cout << "Yes" << endl;
  else cout << "No" << endl;
}
```
### 解法
ランレングス圧縮を用いて、`S`と`T`を圧縮することで`S=T`とすることができるかを判別することができる。今回の問題では`S[i].second > T[i].second`という条件を満たす必要があるが、この条件を見落としていた。
## C - Changing Jewels
[C - Changing Jewels](https://atcoder.jp/contests/abc260/tasks/abc260_c)
解答
```c++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vec = vector<int>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define mod 998244353

int main() {
  ll n, x, y;
  cin >> n >> x >> y;
  if(n < 2) {
    cout << 0 << endl;
    exit(0);
  }
  pair<ll, ll> r(n-1, 1);
  pair<ll, ll> b(n, x);
  while(b.first > 1){
    b.first--;
    r.second += b.second;
    b.second *= y;
    if(r.first > 1){
      r.first--;
      b.second += r.second * x;
    }
  }
  cout << b.second << endl;
}
```
### 解法
`pair`型変数を赤い宝石、青い宝石に用意しておく。変数はともに1つ目が宝石のレベル、2つ目が宝石の個数である。この変数に対して、青い宝石のレベルが1になるまで処理を行うことで結果が求まる。