AtCoder ABC 181

작성일 | In

총평

~

A. Heavy Rotation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++14 -DLOCAL
******************************/

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    cout << (n%2 ? "Black" : "White");
}

B. Trapezoid Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++14 -DLOCAL
******************************/

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

ll N, S;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++){
        ll a, b; cin >> a >> b;
        S += b*(b+1)/2;
        S -= a*(a-1)/2;
    }
    cout << S;
}

C. Collinearity

CCW

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++14 -DLOCAL
******************************/

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<ll, ll> Point;

ll CCW(const Point &a, const Point &b, const Point &c){
    return (b.x - a.x)*(c.y - b.y) - (c.x - b.x)*(b.y - a.y);
}

int N;
Point A[111];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i].x >> A[i].y;
    for(int i=1; i<=N; i++){
        for(int j=1; j<i; j++){
            for(int k=1; k<j; k++){
                if(CCW(A[i], A[j], A[k])) continue;
                cout << "Yes"; return 0;
            }
        }
    }
    cout << "No";
}

D. Hachi

뒤에 3자리가 8의 배수면 8의 배수입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++14 -DLOCAL
******************************/

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

string S;
int C[10];

void Naive(){
    sort(all(S));
    do{
        int now = 0;
        for(const auto c : S) now = now * 10 + (c - '0');
        if(now % 8 == 0){ cout << "Yes"; return; }
    }while(next_permutation(all(S)));
    cout << "No";
}

void Update(int x, int v){
    for(int i=0; i<3; i++) C[x%10] += v, x /= 10;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> S;
    if(S.size() <= 4){ Naive(); return 0; }
    for(const auto c : S) C[c-'0']++;
    for(int i=0; i<1000; i+=8){
        Update(i, -1);
        if(*min_element(C, C+10) >= 0){
            cout << "Yes"; return 0;
        }
        Update(i, +1);
    }
    cout << "No";
}

E. Transformable Teacher

정렬되어있는 수열 $H$에서 $W_i$의 lower bound를 기준으로 앞/뒤 원소의 부호를 알면 됩니다.
간단한 Casework를 통해 풀이를 찾을 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++14 -DLOCAL
******************************/

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

int N, M, H[202020], W[202020];
ll S[202020];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(int i=1; i<=N; i++) cin >> H[i]; sort(H+1, H+N+1);
    for(int i=1; i<=M; i++) cin >> W[i]; sort(W+1, W+M+1);
    for(int i=1; i<=N; i++) S[i] = S[i-1] + (i%2 ? -H[i] : H[i]);

    ll X = 1e18, P = 0;
    for(int i=1; i<=M; i++){
        while(P+1 <= N && H[P+1] <= W[i]) P++;
        ll now = S[P] - (S[N] - S[P]);
        now += (P%2 ? W[i] : -W[i]);
        X = min(X, now);
    }
    cout << X;
}

F. Silver Woods

문제 풀이보다 지문 해석이 훨씬 어려운 문제입니다.

각 점과 $y=100$, $y=-100$인 직선을 각각 정점으로 잡고, 정점의 거리를 가중치로 하는 완전 그래프를 생각해봅시다.
그 그래프의 MST를 만들 때, $y=100$인 직선과 $y=-100$인 직선이 Union되는 시점의 간선 가중치가 가능한 최대 지름($= 2r$)입니다. (Union 되는 시점의 간선 가중치) / 2를 출력하면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++14 -DLOCAL
******************************/

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<int, int> Point;
istream& operator >> (istream &in, Point &t){
    in >> t.x >> t.y; return in;
}

struct Edge{
    int s, e, x;
    Edge() = default;
    Edge(int s, int e, int x) : s(s), e(e), x(x) {}
    bool operator < (const Edge &t) const { return x < t.x; }
};

inline int D(const Point a, const Point b){
    int dx = a.x - b.x, dy = a.y - b.y;
    return dx*dx + dy*dy;
}

int N, P[111];
Point A[111];
vector<Edge> E;

int Find(int v){ return v == P[v] ? v : P[v] = Find(P[v]); }
void Merge(int u, int v){ if(Find(u) != Find(v)) P[Find(u)] = Find(v); }

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i];
    for(int i=1; i<=N; i++) for(int j=1; j<i; j++) E.emplace_back(i, j, D(A[i], A[j]));
    for(int i=1; i<=N; i++){
        E.emplace_back(N+1, i, (A[i].y+100)*(A[i].y+100));
        E.emplace_back(N+2, i, (100-A[i].y)*(100-A[i].y));
    }
    sort(all(E)); iota(P, P+111, 0);
    for(const auto &i : E){
        Merge(i.s, i.e);
        if(Find(N+1) == Find(N+2)){
            cout << fixed << setprecision(10) << sqrt(i.x)/2 << "\n";
            return 0;
        }
    }
}