AtCoder Beginner Contest 188

문제링크

atcoder.jp/contests/abc188

AtCoder Beginner Contest 188 - AtCoder

 

A - Three-Point shot

문제 : 농구 양팀의 점수가 주어지고(x,y x!=y), 지고있는 팀이 3점슛을 성공해 역전할 수 있는지 파악하는 문제

 

풀이

작은수에서 +3한수가 큰수보다 크면 되는 간단한 문제

코드

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int n,m;

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    if(min(n,m)+3>max(n,m)){
        cout << "Yes";
    } else cout << "No";
    return 0;
}

 

B - Orthogonality

문제 : 두 벡터가 주어지고 내적이 0인지 확인하는 문제

 

풀이

문제에서 알려주는 대로 각 원소끼리 곱해서 더한 후 0인지만 파악하면 된다

코드

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll n;
vector<ll> v1;
vector<ll> v2;

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    for(int i=0;i<n;i++){
        ll a;
        cin >> a;
        v1.push_back(a);
    }
    for(int i=0;i<n;i++){
        ll a;
        cin >> a;
        v2.push_back(a);
    }
    ll result = 0;
    for(int i=0;i<n;i++){
        result += v1[i]*v2[i];
    }
    if(result) cout << "No";
    else cout << "Yes";

    return 0;
}

 

C - ABC Tournament

문제 : 2의 N제곱의 사람과 그 사람들의 점수가 주어진다. 각 사람들은 토너먼트식으로 경기를 하는데, 즉 1번째 사람은 2번째 사람과 경기를 하고, 3번째사람은 4번째사람과 경기를한다. 둘 중 큰 값을 가진 사람이 승자가 되고 승자는 바로 다음 경기의 승자와 맞붙게 된다. 최종 2등은 누구인가.

 

풀이

문제는 우리가 알고 있는 일반적인 토너먼트 방식과 같다. N이 16인점을 감안하면 완전 이진트리 꼴을 생각했을때 2*2^16번의 연산이 필요하고 이정도는 시간안에 충분히 가능하다.

나는 다음 경기의 승자와 붙는 다는 점을 이용해 큐를 통해 구현을 하였고, 다른 풀이들도 여럿 있는 듯 하다.

코드

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int n;
queue<pair<int,int>> q;

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    for(int i=0;i<pow(2,n);i++){
        int a;
        cin >> a;
        q.push({a,i+1});
    }
    while(q.size()>2){
        pair<int,int> a = q.front();
        q.pop();
        pair<int,int> b = q.front();
        q.pop();
        if(a.first>b.first) q.push(a);
        else q.push(b);
    }
    pair<int,int> a = q.front();
    q.pop();
    pair<int,int> b = q.front();

    if(a.first>b.first) cout << b.second;
    else cout << a.second;

    return 0;
}

 

D - Snuke Prime

문제 : 다양한 서비스가 존재하고 각 서비스를 즐기기 위해서는 매일 ci원의 돈을 내야한다. 하지만 Snuke Prime시스템을 이용해 C(대문자)원을 지불하면 그날은 무료로 이용이 가능하다. 사용하고 싶은 서비스들과 각 서비스의 일일 사용 비용이 주어졌을때, 사용하고 싶은 서비스들을 모두 이용하기 위한 최소 비용은 얼마인가

 

풀이

날짜가 10^9까지 가능하기 때문에 날짜로 그냥 스위핑을 해서는 시간내에 불가능 하다. 하지만 원하는 서비스가 20만개인점을 이용해 일일 사용량이 변하는 시점만 찾아 본다면 O(n)시간으로 충분히 해결이 가능하다.

서비스가 a일에서 b일까지 이용하길 원한다면 내가 매일 지불해야할 비용은 a일부터 b일까지의 구간은 기존에 다른 서비스들을 이용하기 위해 필요한 금액+c만큼 증가한다. 그렇기 때문에 a일에 +c의 비용을 적용해주고 b+1일에 -c의 비용을 적용해주면 스위핑과 누적을 통해 내가 해당 구간에 이용해야 할 금액을 구할 수 있다.

 

나는 대회 당시 맵을 통해서 +c,-c가 적용되는 같은 날들은 모두 합쳐놓고 벡터로 다시 바꿔서 풀었는데, 메모리나 시간적으로 좀 더 효율적이게 수정할 수 있을 듯 하다.

코드

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll n,C;
vector<pair<ll,ll>> v;
map<ll,ll> ma;

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> C;
    for(int i=0;i<n;i++){
        ll a,b,c;
        cin >> a >> b >> c;
        if(ma.find(a)==ma.end()) ma.insert({a,c});
        else ma.find(a)->second+=c;
        if(ma.find(b+1)==ma.end()) ma.insert({b+1,-c});
        else ma.find(b+1)->second-=c;
    }
    for(auto& i : ma){
        v.push_back({i.first,i.second});
    }
    ll ans = 0;
    ll fee = 0;
    for(int i=0;i<v.size();i++){
        if(i!=v.size()-1){
            ll gap = v[i+1].first - v[i].first;
            fee = v[i].second+fee;
            ans += min(C,fee)*gap;
        }
    }
    cout << ans;
    return 0;
}

 

E - Peddler 

문제 : 정점이 N개 간선이 M개인 방향 그래프가 주어지고 각 간선에 금의 가격이 정해진다. 한 지점에서 금을 산 후 간선을 따라 이동하여 다른 지점에서 금을 팔려고 할 때, 최대 이익을 구한다.

 

풀이

이문제는 풀이가 정말 다양할 것 같다는 생각이듭니다. 

당연히 모든 노드에 대해 단순한 dfs로 팔 수있는 모든 경우를 비교해 보는건 시간안에 불가능하기 때문에, 저는 메모이제이션을 통해 각 노드에서 dfs를 통해 팔 수 있는 가장 비싼 금액을 기록하였습니다.

이렇게 하면 모든 노드에 대해 두번이상 dfs를 적용하지 않고 가장 비싼 금액을 구해 낼 수 있기 때문에, 노드 수+참조수 만큼의 시간이 걸리게 되고 O(v+e)로 해결 할 수 있습니다.

코드

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int n,m;
int val[200005];
vector<int> adj[200005];
bool visited[200005];
int max_val[200005];

int dfs(int idx){
    if(max_val[idx]!=-1) return max_val[idx];

    visited[idx] = 1;
    int result = INT_MIN;
    for(auto& i : adj[idx]){
        result = max(result,max(val[i],dfs(i)));
    }
    max_val[idx] = result;
    return max_val[idx];
}

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for(int i=0;i<n;i++){
        cin >> val[i];
    }
    for(int i=0;i<m;i++){
        int u,v;
        cin >> u >> v;
        u--,v--;
        adj[u].push_back(v);
    }
    memset(max_val,-1,sizeof(max_val));
    int ans = INT_MIN;
    for(int i=0;i<n;i++){
        int dest = dfs(i);
        if(dest==INT_MIN) continue;
        ans = max(ans,dest-val[i]);
    }
    cout << ans;
    return 0;
}

 

E - +1-1x2

문제 : 숫자 x와 y가 주어지고 우리는 x에 대해 +1 혹은 -1 혹은 *2의 연산만 할 수 있다. 이때 x에서 y로 가는 최소 연산 횟 수를 구하여라

 

풀이

x와 y의 범위가 10^18이기 때문에 일반적인 완전탐색이나 dp로는 풀 수 없는 문제입니다. 저 또한 대회중엔 풀지 못했고 끝나고 멤버분의 풀이조언과 에디토리얼을 참고하여 풀었습니다. 다음의 풀이는 에디토리얼 기반 풀이 입니다.

x->y대신에 y->x로 가는 가장 빠른 경우를 생각해도 답이 같은 것이란것은 자명합니다. 그러면 y를 기준으로 다음의 경우를 생각할 수 있습니다.

 

1. /2연산을 수행하지 않고 +1과 -1만으로 x까지 간다.

2. /2연산을 수행하고 +1과 -1을 활용하여 x까지 간다. 

 

1번의 경우는 당연히 x와 y의 차의 절댓값 만큼의 연산이 필요할 것 입니다. 문제는 2번인데.. 언제 나눗셈을 하는게 최적인가를 생각해보면 됩니다.

 

y가 홀수 일때 부터 생각해 봅시다. 예를들어 -1이 5번 적용되고 /2를 한번 해야하는 상황이 있다고 가정해봅시다. 이는 -1을 5번하는것보다 -1을 두 번 적용 한 후 /2를하고 -1를 한번하는 것이 빠르다는건 당연합니다. 왜냐면 이전에 적용한 -1이 두배로 커졌기때문에 연산 횟수가 줄어드는것은 당연하기 때문이죠. 마찬가지로 여기서 -1을 두번 적용하고 /2하는 것보다 -1을한번 적용하고 /2를 하는것이 더 빠름을 알 수 있습니다. 따라서 -1혹은 +1을 몇번 적용하던 간에 y-1에서 가는 값과 y+1에서 가는 값이 가장 빠름을 알 수 있습니다.

 

y가 짝수 일때는 -1을 여러번 하고 /2를 하는것보다 /2를 하고 -1을 적용하는것이 빠르다는 것또한 당연합니다. -1을 여러번하고 /2를 하는것은 이전에 연산된값이 절반으로 줄기때문에 더 많은 연산이 소모되기 때문입니다.

 

따라서 위의 과정을 재귀적으로 수행하여 최소값을 얻어내면 원하는 결과를 얻을 수 있습니다만... 저는 맨처음에 이게 왜 메모이제이션으로 가능할까라는 생각을 했습니다. 홀수일때 2의 제곱으로 늘어 날꺼라고 생각했기 때문입니다. 그런데 생각을 잘 해보면 y-1을 2로나눈값과 y+1을 2로나눈값은 1차이나는 정수라는 것을 알 수 있습니다. 무조건 하나는 홀수이고 하나는 짝수이죠. 따라서 새롭게 나온 수 두개중에 홀수입장에서 다시 y'-1과 y'+1을 2로나눈 값을 찾게된다면 y'-1과 y'+1중 하나는 반드시 짝수인 수와 겹칩니다. 짝수는 /2만 하기 때문에 나오는 수도 중복이되고 따라서 첫번째단계에서 두개의 수를 요구했던것과 마찬가지로 두번째 단계에서도 두개의 수만 요구하게 됩니다. 따라서 전체에서 필요한 수는 2*log(n)개이기 때문에 해상숫자들만 메모이제이션으로 처리해 주면 O(log(n))으로 답을 구할 수 있습니다.

 

이렇게 값이 엄청 크지만 사실상 필요한 값이 얼마 안되는 dp를 희소dp라고 부르기도 합니다. 저는 희소dp값을 구하기 위해 unordered_map를 이용해 해싱으로 구했고 구지 해싱안하고 map등을 사용해도 충분히 시간내에 구할 수 있습니다.

 

코드

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll x,y;
unordered_map<ll,ll> um;

ll solve(ll num){
    if(num==1) return abs(x-num);
    if(um.find(num)!=um.end()) return um.find(num)->second;
    ll result;
    if(num%2) result = min(abs(x-num),min(solve((num+1)/2)+2,solve((num-1)/2)+2));
    else result = min(abs(x-num),solve(num/2)+1);
    um.insert({num,result});
    return result;
}
int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> x >> y;
    cout << solve(y);
    return 0;
}