AtCoder Beginner Contest 478

A - Grapes

問題文

除算と余りの問題です。

C++

#include <bits/stdc++.h>
 
#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, m;
    cin >> n >> m;
    int a = m / n;
    int b = m % n;
    rep(i, n){
        if(i < b) cout << a + 1 << endl;
        else cout << a << endl;
    }
    return 0;
} 

B - Topping

問題文

3重ループの問題です。

C++

#include <bits/stdc++.h>
 
#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, v;
    cin >> n >> v;
    vector<int> w(n);
    rep(i, n) cin >> w[i];
    int ans = 0;
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            for(int k=j+1; k<n; k++){
                if(i+j+k+3 <= v){
                    ans = max(ans, w[i]+w[j]+w[k]);
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
} 

C - Sort Subarray

問題文

ソートの問題です。
配列aをコピーした配列bを作成します。
aとbを比較して、異なる要素の最大のindex、最小のindexを探索します。
最大のindex - 最小のindex < k
なら"Yes"になります。

C++

#include <bits/stdc++.h>
 
#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;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    vector<int> b(a);
    sort(b.begin(), b.end());
    int r = 0;
    int l = n-1;
    rep(i, n){
        if(a[i] != b[i]){
            l = min(l, i);
            r = max(r, i);
        }
    }
    if(r-l<k){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
} 

D - Range Set Insertion Query

問題文

イベントソートの問題です。
現在、いくつの要素があるか保持するvectorを思いつくのが難しいです。

C++

    vector<int> counter(q, 0);
    for(auto [e, x, v]:event){
        while(now < e){
            now++;
            cout << ans << ' ';
        }
        if(counter[x] == 0) ans++;
        counter[x] += v;
        if(counter[x] == 0) ans--;
    }

C++

#include <bits/stdc++.h>
 
#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, q;
    cin >> n >> q;
    vector<tuple<int, int, int>> event;
    rep(i, q){
        int l, r, x;
        cin >> l >> r >> x;
        l--;
        x--;
        event.emplace_back(l, x, 1);
        event.emplace_back(r, x, -1);
    }
    event.emplace_back(n, 0, 0);
    sort(event.begin(), event.end());
    int now = 0;
    int ans = 0;
    vector<int> counter(q, 0);
    for(auto [e, x, v]:event){
        while(now < e){
            now++;
            cout << ans << ' ';
        }
        if(counter[x] == 0) ans++;
        counter[x] += v;
        if(counter[x] == 0) ans--;
    }
    cout << endl;
    return 0;
}