LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@RubyLrving(ruby lrving)

AtCoder Beginner Contest 388

Posted at

A - ?UPC

O(1)

C++
s.substr(0, 1) + "UPT"
C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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;
    cout << s.substr(0, 1) + "UPC" << endl;
    return 0;
}

B - Heavy Snake

O(K*N)
2重ループです。
シミュレートしましょう。
kを1ずつループで増やして、T_i * (L_i + k)を計算し、最も大きな数を求めましょう。

C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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, D;
    cin >> N >> D;
    vector<int> T(N), L(N);
    rep(i, N) cin >> T[i] >> L[i];
    
    for(int k=1; k<=D; k++){
        int ans = 0;
        for(int i=0; i<N; i++){
            ans = max(T[i] * (L[i] + k), ans);
        }
        cout << ans << endl;
    }
    
    return 0;
}

C - Various Kagamimochi

O(NlogN)
二分探索です。
b / 2以下の餅の数を探索します。
upper_boundでb / 2以下より一つ大きい要素のイテレータを取得できます。

C++
ll a = upper_bound(A.begin(), A.end(), b/2) - A.begin();

b / 2以下の餅の数aを探索できるので、ansでaの合計を求めましょう。

C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];

    ll ans = 0;
    for(auto b:A){
        auto a = upper_bound(A.begin(), A.end(), b/2);
        ans += a - A.begin();
    }
    cout << ans << endl;

    return 0;
}

D - Coming of Age Celebration

O(N)
imos法です。

成人した人が何人まで石を渡せるのかを配列Bで管理します。
成人した人が石を渡せる最初の人の要素B[i]にB[i]++を行います。
成人した人が石を渡せなくなる人の要素B[i]にB[i]--を行います。
ここまで考察すると、imos法だとわかります。

B[i]のiがsizeを超えないように、

C++
min(i + A[i] + 1, N)

A[i]は0未満にならないので、

C++
A[i] = max(0, A[i] - (N - 1 - i));

を行いましょう。

C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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, 0), B(N+1, 0);

    rep(i, N) cin >> A[i];
    rep(i, N){
        A[i] += B[i];
        B[i+1] += B[i] + 1;
        B[min(i + A[i] + 1, N)]--;
        A[i] = max(0, A[i] - (N - 1 - i));
    }

    rep(i, N){
        cout << A[i];
        if(i<N-1) cout << ' ';
        else cout << endl;
    }
    
    return 0;
}

E - Simultaneous Kagamimochi

O(N)
貪欲法、尺取法です。
N個の餅をN/2に分けます。

C++
while(b < N && A[i] * 2 > A[b]) b++;

A[i] * 2未満の時は、bのカウントを進めます。
A[i] * 2以上の時は、b、ansのカウントを進めます。

C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#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

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;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];

    ll ans = 0;
    ll m = N / 2;
    ll b = m;
    for(int i=0; i<m; i++){
        while(b < N && A[i] * 2 > A[b]) b++;
        if(b==N) continue;
        ans++;
        b++;
    }
    cout << ans << endl;

    return 0;
}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?