AtCoder ABC379 振り返り [C++]

最初に

AtCoder ABC379の振り返りを行います。

A - Cyclic

解法

1. 3桁の整数を受けとり、各位ごとに数値を得る
2. その数値を並び替えて出力

反省点

• 解説にもあるとおり、入力から各位ごとに受けとれば簡単
• 出力するだけならわざわざ計算する必要はない

ソースコード

#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

解法

1. 文字列Sを端から走査していく
2. 連続した文字を数える一時的な変数cumと答えを保持する変数ansを用意する
3. 走査した文字が'O'ならcum++, 'X'ならcum = 0とする
4. cumがKに至った時, ans++して連続をリセットするのでcum = 0とする
5. 走査し終えたらansを出力する

ソースコード

#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

解法

1. マスの位置と石の数をペア (XA) にして入力を受けとる
   このとき石の数の和がNと異なると明らかに不可能

2. マスの位置について昇順にソートする
   このとき0番目の石の位置 (XA[0].first) が1以外だと明らかに不可能

3. マスについて端から走査する

   1. (i+1)番目とi番目のマスの石の位置の差をとる(diff)
   2. i番目のマスの石の数を、現在保有している石の数を管理する変数(left)に加える
      このとき、diff > leftだと間の石のマスに石を配置することができないので不可能
   3. leftから石を配置するのでdiff分だけ引く
   4. 石を次の石の位置までそれぞれ配置するときのcostを計算する
      costは初項1, 項数diff - 1、公差+1の等差数列で表される(図を書くとわかりやすい）
   5. leftが1以上の場合（石が次の位置に繰り越される場合）
      costにleft×diff分加える

4. costを出力する

   例) 入力例
   8 3
   1 3 5
   4 2 2
   

ソースコード

#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

解法
2分探索とmulti_setを利用して解く
詳細はソースコードを参照

ソースコード

#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に上がりました。もう少しで入緑です。