AtCoder Beginner Contest 476

A - Appender

問題文

O(1)
最後の一文字が'e'か判定して'r'か'er'を追加しましょう。

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() {
    string s;
    cin >> s;
    int n = s.size();
    if(s[n-1] == 'e'){
        s += "r";
    }else{
        s += "er";
    }
    cout << s << endl;
    return 0;
} 

B - Wild Card

問題文

O(N)
'*'の箇所意外の文字を判定しましょう。

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;
    cin >> n;
    string s, t;
    cin >> s >> t;
    rep(i, n){
        if(t[i] == '*') continue;
        if(s[i] != t[i]){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
} 

C - Third Largest Number

問題文

データ構造の問題です。
multisetに要素を追加してイテレータを2つ進めましょう。

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;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    multiset<int> mst;
    mst.insert(a[0]);
    mst.insert(a[1]);
    for(int i=2; i<n; i++){
        mst.insert(a[i]);
        auto rit = mst.rbegin();
        rep(j, 2) rit++;
        cout << *rit << endl;
    }
    return 0;
} 

D - Automat

問題文

二分探索の問題です。
片方を固定してもう片方を二分探索する典型問題です。
bの配列に0を追加してるのは、bの要素を一つも購入しないパターンを想定しています。

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() {
    ll n, m, k;
    cin >> n >> m >> k;
    ll x, y;
    cin >> x >> y;
    vector<ll> a(n), b(m), aa(n+1);
    rep(i, n) cin >> a[i];
    rep(i, m) cin >> b[i];
    b.push_back(0);
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    rep(i, n) aa[i+1] = aa[i] + a[i];
    ll ans = 0;
    rep(i, m+1){
        ll bb = 0;
        if(k * y >= b[i]){
            ll num = (b[i] + k - 1) / k;
            x += num * k - b[i];
            y -= num;
            bb = i;
        }
        auto it = upper_bound(aa.begin(), aa.end(), x + y * k);
        ll index = max(it-aa.begin()-1LL, 0LL);
        ans = max(ans, bb+index);
    }
    cout << ans << endl;
    return 0;
}