AtCoder Beginner Contest 446

A - Handmaid

問題文

大文字を小文字に変換できるか、文字列の結合ができるか。
上記を問われています。

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;

    s[0] = s[0] - 'A' + 'a';
    s = "Of" + s;
    cout << s << endl;

    return 0;
} 

B - Greedy Draft

問題文

シミュレーションをしましょう。

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;
    vector<bool> used(m, false);
    vector<vector<int>> x(n, vector<int>());
    rep(i, n){
        int l;
        cin >> l;
        x[i].resize(l);
        rep(j, l){
            cin >> x[i][j];
            x[i][j]--;
        }
    }

    rep(i, n){
        int l = x[i].size();
        bool ok = true;
        rep(j, l){
            if(used[x[i][j]] == false){
                ok = false;
                used[x[i][j]] = true;
                cout << x[i][j] + 1 << endl;
                break;
            }
        }
        if(ok){
            cout << 0 << endl;
        }
    }

    return 0;
} 

C - Omelette Restaurant

問題文

データ構造の問題です。
キューを使用して日付、卵の数を管理しましょう。
先頭の卵から配列bの要素を引いて行きます。
保存の日付dを超えたらキューから破棄します。

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; }

void solve(){
    int n, d;
    cin >> n >> d;
    vector<int> a(n), b(n);
    rep(i, n) cin >> a[i];
    rep(i, n) cin >> b[i];

    int sum = 0;
    int cnt = 0;
    queue<pair<int, int>> que;
    rep(i, n){
        sum += a[i];
        que.push({i, a[i]});
        while(b[i]){
            int m = min(que.front().second, b[i]);
            sum -= m;
            que.front().second -= m;
            b[i] -= m;
            if(que.front().second == 0){
                que.pop();
            }
        }
        while(que.size() && que.front().first <= i - d){
            sum -= que.front().second;
            que.pop();
        }
    }
    cout << sum << endl;
}

int main() {
    int t;
    cin >> t;
    rep(i, t){
        solve();
    }
    return 0;
} 

D - Max Straight

問題文

動的計画法と言われる単元でLISの分類の問題です。
最長増加ではなく条件として

dp_{a_i} = dp_{a_i-1} + 1

で漸化式を組めます。
最大を求めましょう。

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];
    map<int, int> mp;
    int ans = 0;
    rep(i, n){
        mp[a[i]] = max(mp[a[i]], mp[a[i]-1] + 1); 
        ans = max(mp[a[i]], ans);
    }
    cout << ans << endl;
    return 0;
}