AtCoder Beginner Contest 379

A - Cyclic

O(1)
abcを、bca、cabと表示します。
文字列を並び替えましょう。

C++

#include <bits/stdc++.h>
#include <atcoder/all>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    string N;
    cin >> N;
    cout << N[1] << N[2] << N[0] << ' ' << N[2] << N[0] << N[1] << endl;
    return 0;
} 

B - Strawberries

O(N)
シミュレートしましょう。

C++

#include <bits/stdc++.h>
#include <atcoder/all>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

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

    int cnt = 0;
    int ans = 0;
    rep(i, N){
        if(S[i] == 'O'){
            cnt++;
        }else{
            ans += cnt / K;
            cnt = 0;
        }
    }
    ans += cnt / K;
    cout << ans << endl;

    return 0;
} 

C - Sowing Stones

O(N)
全探索の実装問題です。
Xの制約が2*10^9の為、imos法が使用できません。
移動回数は、x_j - x_i = dの移動距離を求め、

d * (d - 1) / 2 = 移動回数

として求めます。

C++

#include <bits/stdc++.h>
#include <atcoder/all>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    ll N, M;
    cin >> N >> M;
    vector<pair<ll, ll>> XA(M);
    for(auto& [x, a]:XA) cin >> x;
    for(auto& [x, a]:XA) cin >> a;
    XA.push_back({N+1, 1});
    sort(XA.begin(), XA.end());

    ll cnt = 0;
    ll ans = 0;
    for(int i=0; i<M; i++){
        auto& [x1, a1] = XA[i];
        auto& [x2, a2] = XA[i+1];

        cnt += a1;
        ll d = x2 - x1;
        ans += d * (d - 1) / 2LL;
        cnt -= d;
        ans += cnt * d;

        if(cnt < 0){
            cout << -1 << endl;
            return 0;
        }
    }

    if(cnt != 0) cout << -1 << endl;
    else cout << ans << endl;

    return 0;
} 

D - Home Garden

O(N)
全探索の実装問題です。
シミュレートします。
queueに日付を格納してデータを保持するとクエリに対応できます。
queueに日付を格納するかを閃く問題です。

C++

#include <bits/stdc++.h>
#include <atcoder/all>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    ll Q;
    cin >> Q;

    queue<ll> que;
    ll time = 0;
    rep(i, Q){
        ll query;
        cin >> query;

        if(query == 1){
            que.push(time);
        }

        if(query == 2){
            ll T;
            cin >> T;
            time += T;
        }

        if(query == 3){
            ll H;
            cin >> H;
            ll cnt = 0;
            while(que.size() && time - que.front() >= H){
                que.pop();
                cnt++;
            }
            cout << cnt << endl;
        }
    }

    return 0;
}