AtCoder Beginner Contest 246

A - Four Points

O(1)

長方形の為、２点のx座標は同一の値になります。
y座標も同じです。

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() {
    vector<P> vec(3);
    rep(i, 3) cin >> vec[i].first >> vec[i].second;

    map<int, int> x, y;
    rep(i, 3){
        x[vec[i].first]++;
        y[vec[i].second]++;
    }

    for(auto xi:x){
        if(xi.second%2==1) cout << xi.first << ' ';
    }
    for(auto yi:y){
        if(yi.second%2==1) cout << yi.first << endl;
    }

    return 0;
} 

---

B - Get Closer

O(1)
ベクトルの正規化ですね。
単位ベクトルのX = X / ベクトル長さ
単位ベクトルのY = Y / ベクトル長さ

解法１

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() {
    double A, B;
    cin >> A >> B;

    double d = sqrt(A*A + B*B);

    cout << fixed_setprecision(7) << A/d << ' ' << B/d << endl;

    return 0;
} 

解法２

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

double angle(double x, double y) {
    double r = atan2(x, y);
    if(r < 0){
        r = r + 2 * M_PI;
    }
    return r;
}

int main() {
    double A, B;
    cin >> A >> B;

    double a = angle(B, A);

    cout << fixed_setprecision(7) << cos(a) << ' ' << sin(a) << endl;

    return 0;
} 

---

C - Coupo

O(2N)

1. まずX円以上の商品にクーポンを可能な限り使用します。
2. その後、商品をソートをして値段に対しての降順にします。
3. 残ったクーポンを可能な限り使用します。
   以上の手順で合計金額の最小値を求めることができます。

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

    rep(i, N){
        if(A[i]-X>=0){
            ll m = min(K, A[i]/X);
            A[i] = A[i] - (m*X);
            K = K - m;
            if(K==0) break;
        }
    }

    sort(A.begin(), A.end(), std::greater<ll>());
    rep(i, N){
        if(K==0) break;
        A[i] = 0;
        K--;
    }

    ll ans=0;
     for(auto a:A) ans += a;
     cout << ans << endl;

    return 0;
} 

---

D - 2-variable Function

O(NlogN)
一方の値を固定して、片方の値は二分探索するというたまに出る問題です。

N <= 10^18 に対して、条件は X = a*a*a + a*a*b + b*b*a + b*b*b です。
b = 0 の時、条件式は X = a*a*a となります。
N <= 10^18 を見たすXは、 X　=　a*a*a = １０＾６＾３
a = １０＾６ 　となります。
a, b <= １０＾６ の考察ができます。

二分探索の条件として、
okを最大値、ngを最小値としたとき、
最小値　０
最大値　１００００００
| ok - ng | > 0（誤差0）
f(a, mid) >= Nのとき、ok = mid
それ以外はng = mid　+ 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; }

ll f(ll a, ll b){
    return a*a*a + a*a*b + b*b*a + b*b*b;
}

int main() {
    ll N, m=NUM_MAX;
    cin >> N;

    for(ll a=0; a <= 1000000; a++){
        ll ok = 1000000;
        ll ng = 0;

        while(abs(ok-ng)>0){
            ll mid = (ok + ng) / 2;
            if(f(a, mid) >= N){
                ok = mid;
            }else{
                ng = mid+1;
            }
        }

        if(m > f(a, ok)) m = f(a, ok);
    }
    cout << m << endl;

    return 0;
} 

---