AtCoder Beginner Contest 234

A - Weird Function

O(1)
f(x)の関数を作成して計算式の処理を行います。

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 f(int x){
    return x*x+2*x+3;
}

int main() {
    int t;
    cin >> t;

    cout << f(f(f(t)+t)+f(f(t))) << endl;

    return 0;
}

B - Longest Segment

O(N＾２)
２点間の距離は、sqrt((x2-x1)^2+(y2-y1)^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<double> x(N), y(N);
    rep(i, N)cin >> x[i] >> y[i];

    double ans = 0;
    rep(i, N){
        repx(j, i+1, N){
            double xx = abs(x[i] - x[j]);
            double yy = abs(y[i] - y[j]);
            double zz = sqrt(xx * xx + yy * yy);
            ans = max(ans, zz);
        }
    }
    cout << fixed_setprecision(7) << ans << endl;

    return 0;
}

C - Happy New Year!

O(N)
問題文は２進数を０と２で表現するとどのような表示になるかを聞いています。
int型や、long long型だと対応できないです。
文字列で表示します。

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 K;
    cin >> K;

    string ans;
    while(K>0){
        if(K%2==1) ans = "2" + ans;
        else ans = "0" + ans;
        K = K / 2;
    }
    cout << ans << endl;

    return 0;
}

D - Prefix K-th Max

O(N)
なぜかコンテスト本番中は解けませんでした。
プライオリティーキューを使用すると解決します。
単純に処理を行うとO(N^2)でTLEになります。

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

    priority_queue<int, vector<int>, greater<int>> pque;
    rep(i, K) pque.push(P[i]);
    cout << pque.top() << endl;

    repx(i, K, N){
        if(pque.top()<P[i]){
            pque.pop();
            pque.push(P[i]);
        }
        cout << pque.top() << endl;
    }
 
    return 0;
}