AtCoder Beginner Contest 195

A - Health M Death

O(1)
余りを求めます。

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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 M, H;
    cin >> M >> H;

    if(H % M == 0) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

B - Many Oranges

O(1)
We Love Golfの数学的な解法を読んでO(１)で解いてみようと思いました。

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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 A, B, W;
    cin >> A >> B >> W;

    W = W * 1000;

    int min_v = (W / A);
    int max_v = (W + B - 1) / B;
    int ok = 0;

    if(abs(W - (W + B - 1)) <= (B - A) * max_v) ok = 1;
    if(W - (W / A) * A <= (B - A) * min_v) ok = 1;

    if(ok) cout << max_v << " " << min_v << endl;
    else cout << "UNSATISFIABLE" << endl;

    return 0;
}

O(N)
こっちの解き方はB問題っぽいです。
自分はプログラムで解きたいのでこっちのが好きです。

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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 A, B, W;
    cin >> A >> B >> W;

    W = W * 1000;
    int ok = 0;
    int min_v = 1e9+7;
    int max_v = 0;

    for(int i=1; i<10000000 ;i++){
        if(!(A*i<=W && W<=B*i)) continue;
        min_v = min(min_v, i);
        max_v = max(max_v, i);
        ok = 1;
    }

    if(ok) cout << min_v << " " << max_v << endl;
    else cout << "UNSATISFIABLE" << endl;

    return 0;
}

C - Comma

O(N)
４桁目から1,000と一つ,がつきます。
1000の場合は1000 - 999 = 1です。
1000000の場合は1000000 - 999999 = 1です。
3桁増える事に999*1000+999を行い、[,]をカウントしていきます。

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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 = 0;
    cin >> N;

    ll cnt = 999;
    ll res = 0;
    while(cnt<=N){
        res += N - cnt;
        cnt = cnt * 1000 + 999;
    }
    cout << res << endl;

    return 0;
}

D - Shipping Center

O(N)
貪欲法です。
Wの要素、Xの要素をどのタイミングでソートをするかが大事です。

C++

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; 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<ll,ll>;
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, Q;
    cin >> N >> M >> Q;

    vector<P> W(N);
    rep(i, N) cin >> W[i].first >> W[i].second;

    sort(W.begin(), W.end(), []( const auto &x, const auto &y )
    {
        return get<1>( x ) == get<1>( y ) ? get<0>( x ) > get<0>( y ) : get<1>( x ) > get<1>( y );
    });

    vector<ll> X(M);
    rep(i, M) cin >> X[i];


    rep(i, Q){
        int L, R;
        cin >> L >> R;
        L = L - 1;
        R = R - 1;

        ll res = 0;
        vector<P> temp_W(W.size());
        copy(W.begin(), W.end(), temp_W.begin());

        vector<ll> temp_X(X.size());
        copy(X.begin(), X.end(), temp_X.begin());
        temp_X.erase(temp_X.begin() + L, temp_X.begin() + R + 1);
        sort(temp_X.begin(), temp_X.end());

        for(int j=0; j<temp_X.size(); j++){
            for(int k=0; k<temp_W.size(); k++){
                if(temp_X[j]>=temp_W[k].first){
                    res += temp_W[k].second;
                    temp_W.erase(temp_W.begin() + k);
                    break;
                }
            }   
        }
        cout << res << endl;
    }

    return 0;
}

感想

自己最高のパフォーマンスが出せました。