AtCoder ABC379 振り返り [C++] 

# 最初に
[AtCoder ABC379](https://atcoder.jp/contests/abc379)の振り返りを行います。

# [A - Cyclic](https://atcoder.jp/contests/abc379/tasks/abc379_a)
解法
1. 3桁の整数を受けとり、各位ごとに数値を得る
1. その数値を並び替えて出力

反省点
- [解説](https://atcoder.jp/contests/abc379/editorial/11318)にもあるとおり、入力から各位ごとに受けとれば簡単
- 出力するだけならわざわざ計算する必要はない 
## ソースコード
```cpp
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
using namespace std;

int main() {
    int N;
    cin >> N;
    int a = N/100;
    int b = N/10 % 10;
    int c = N % 10;
    
    cout << 100*b + 10*c + a << " " << 100*c + 10 * a + b << endl;
}
```
# [B - Strawberries](https://atcoder.jp/contests/abc379/tasks/abc379_b)
解法
1. 文字列Sを端から走査していく
1. 連続した文字を数える一時的な変数cumと答えを保持する変数ansを用意する
1. 走査した文字が'O'ならcum++, 'X'ならcum = 0とする
1. cumがKに至った時, ans++して連続をリセットするのでcum = 0とする
1. 走査し終えたらansを出力する

## ソースコード
``` cpp
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    string S;
    cin >> S;

    int size = S.size();
    int cum = 0;
    int ans = 0;
    for(int i = 0; i < size; i++){
        if (S[i] == 'O') {
            cum++;
            if(cum >= K){
                ans++;
                cum = 0;
            }
        } else {
            cum = 0;
        }
    }
    cout << ans << endl;
}
```

# [C - Sowing Stones](https://atcoder.jp/contests/abc379/tasks/abc379_c)
解法
1. マスの位置と石の数をペア (XA) にして入力を受けとる
このとき石の数の和がNと異なると明らかに不可能
1. マスの位置について昇順にソートする
このとき0番目の石の位置 (XA[0].first) が1以外だと明らかに不可能
1. マスについて端から走査する
    1. (i+1)番目とi番目のマスの石の位置の差をとる(diff)
    1. i番目のマスの石の数を、現在保有している石の数を管理する変数(left)に加える
    このとき、diff > leftだと間の石のマスに石を配置することができないので不可能
    1. leftから石を配置するのでdiff分だけ引く
    1. 石を次の石の位置までそれぞれ配置するときのcostを計算する
    costは初項1, 項数diff - 1、公差+1の等差数列で表される(図を書くとわかりやすい）
    1. leftが1以上の場合（石が次の位置に繰り越される場合）
    costにleft×diff分加える
1. costを出力する


    例) 入力例
    8 3 
    1 3 5
    4 2 2
    ![コストの計算の図](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3781894/a17c0b91-c2fd-9551-f63c-6546af7ef4b5.png)


    


## ソースコード
```cpp
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
using namespace std;

int main() {
    ll N, M;
    cin >> N >> M;
    vector<pair<ll, ll>> XA(M);
    ll total = 0;
    rep(i, M) { cin >> XA[i].first; }
    rep(i, M) {
        cin >> XA[i].second;
        total += XA[i].second;
    }

    if (total != N) {
        cout << "-1" << endl;
        return 0;
    }
    sort(XA.begin(), XA.end());
    if (XA[0].first != 1) {
        cout << "-1" << endl;
        return 0;
    }
    ll left = 0;
    ll cost = 0;
    rep(i, M) {
        ll next = (i != M - 1) ? XA[i + 1].first : N + 1;
        ll diff = next - XA[i].first;
        left += XA[i].second;
        if (diff > left) {
            cout << -1 << endl;
            return 0;
        } else {
            left -= diff;
            cost += diff * (diff - 1) / 2LL;
            if (left > 0) {
                cost += left * diff;
            }
        }
    }
    cout << cost << endl;
}
```
# [D - Home Garden](https://atcoder.jp/contests/abc379/tasks/abc379_d)
解法
2分探索とmulti_setを利用して解く
詳細はソースコードを参照
## ソースコード
```c++
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
using namespace std;


int main() {
    int Q;
    cin >> Q;
    multiset<ll> heights;
    ll total_increment = 0;
    rep(i, Q){
        int type;
        cin >> type;
        if(type == 1){  
            //植木鉢を1個用意しその植物の高さは0
            heights.insert(-total_increment);
        }else if(type == 2){
            ll T;
            cin >> T;
            //全ての植物の高さがT伸びる
            total_increment += T;
        }else if(type == 3){
            ll H;
            cin >> H;
            // 高さがH以上の植物を全て刈り取る、その植物の個数を出力する
            ll x = H- total_increment;
            auto it = heights.lower_bound(x);
            ll count = distance(it, heights.end());
            cout << count << endl;
            heights.erase(it, heights.end());
        }
    }
}
```


# まとめ
D問題よりC問題の方が圧倒的に難しいです。

BTW,
レートが799に上がりました。もう少しで入緑です。