ACM-ICPC 2020 예선 후기

ACM-ICPC 인터넷 예선 늦은 후기입니다.

 

ACM-ICPC 인터넷 예선 3솔로 마무리했습니다...

 

마지막에 F번에서 좀 비벼봤지만 안타깝게도 맞지는 못했더라구요ㅠ

 

풀었던 순서대로 리뷰를 좀 해보려고 합니다.

 

I. Project Teams

 

www.acmicpc.net/problem/20044

20044번: Project Teams

 

2*N명의 사람으로 N개의 팀을 꾸리기 위해 2명씩 짝지어야하는데, 팀원들의 코딩 역량의 합을 최대한 일정하게 유지한다는 문제.

 

2*N개의 수를 정렬한 다음  i번째 사람과 2*N-i-1 번째 사람의 코딩역량의 합의 최소를 출력하면 되는 문제입니다.

 

 

대회 당시 등록문제를 찾으려했는데 보이지 않아서 일단 한국어로 된 문제부터 읽다가 운좋게도 문제를 빨리 읽고 파악해서 5분만에 풀 수 있었던 문제.

 

5min.

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int n;
    cin>>n;
    vector<int> v(n*2);
    for(int i=0;i<2*n;i++)
        cin>>v[i];
        
    sort(v.begin(), v.end());
    
    lld mn = v[0]+v[2*n-1];
    for(int i=0;i<n;i++)
        if(mn>v[i]+v[2*n-i-1]) mn = v[i]+v[2*n-i-1];
 
    cout<<mn;
    return 0;
}

 

E. Cycle game

www.acmicpc.net/problem/20040

20040번: 사이클 게임

n개의 점이 주어지고, 매 차례마다 두 점을 선택해서 이를 연결하는 선분을 긋는다. (n개의 점 중 어느 세 점도 일직선 위에 놓이지 않는다.)

n개의 점이 사이클이되면 종료되는데, 몇번째 차례에서 사이클이 완성되는 지 출력하면 되는 문제.

 

Union-Find를 이용하여 merge를 할 때, 이미 부모가 같다면 사이클이므로 그때를 출력하면 되는 문제입니다.

 

문제를 읽자마자 Union-Find가 생각나서 풀 수 있었던 문제.

하지만 두번째 예제가 복붙이 안되었는데 된줄알고 계속 예제출력이 다르다고 생각해서 시간을 끌었던ㅠㅠ

 

36min.

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
int parent[500005];
int flag;
 
int find(int n)
{
    if(parent[n]==n) return n;
    return parent[n] = find(parent[n]);
}
 
void merge(int v, int u, int i)
{
    v = find(v);
    u = find(u);
    if(v==u)
    {
        if(flag==0) flag = i;
        return;
    }
    parent[v] = u;
}
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, m;
    cin>>n>>m;
    vector<vector<int>> v(n);
    for(int i=1;i<=n;i++) parent[i] = i;
    for(int i=0;i<m;i++)
    {
        int a, b;
        cin>>a>>b;
        merge(a, b, i+1);
    }
    cout<<flag;
    return 0;
}

 

K. Road Reconstruction

www.acmicpc.net/problem/20046

20046번: Road Reconstruction

N*M 좌표평면에서 (1, 1) -> (N, M) 까지 가는데 0인 곳은 이미 도로,  1 또는 2인 곳은 도로를 건설할 때의 비용, -1은 가지 못하는 곳.

 

최소 도로 건설 비용을 구하면 된다.

 

DP인줄 알고 골똘히 생각하는데 팀원과 몇마디 나누다보니 다익스트라 같아서 그대로 짰더니 운좋게 맞았던 문제.

 

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
class Compare
{
public:
    bool operator()(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b)
    {return a.first>b.first;}
};
 
int dy[] = {0, 0, 1, -1};
int dx[] = {1, -1, 0, 0};
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n, m;
    cin>>n>>m;
    vector<vector<int>> cost(n, vector<int>(m));
    vector<vector<int>> mp(n, vector<int>(m, INT_MAX));
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>cost[i][j];
    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, Compare> pq;
    if(cost[0][0]==-1)
    {
        cout<<-1;
        return 0;
    }
    mp[0][0] = cost[0][0];
    pq.push({mp[0][0], {0, 0}});
    while(!pq.empty())
    {
        int ncost = pq.top().first;
        int y = pq.top().second.first;
        int x = pq.top().second.second;
        pq.pop();
        for(int i=0;i<4;i++)
        {
            int ny = y+dy[i], nx = x+dx[i];
            if(ny>=n || nx>=m || ny<0 || nx<0) continue;
            if(cost[ny][nx]==-1) continue;
            if(ncost+cost[ny][nx]<mp[ny][nx])
            {
                mp[ny][nx] = ncost+cost[ny][nx];
                pq.push({mp[ny][nx], {ny, nx}});
            }
        }
    }
    if(mp[n-1][m-1]==INT_MAX) cout<<-1;
    else cout<<mp[n-1][m-1];
    return 0;
}

 

그 다음은 대회 당시에는 못풀었지만 나중에 풀었던 F번입니다.

 

F. Escaping

무한 정수 좌표 평면에서 N명의 경찰이 1명의 도둑을 잡는데 경찰과 도둑은 한번에 1만큼 이동할 수 있다.

도둑이 영원히 잡히지 않을 수 있으면 YES, 도둑이 잡힌다면 NO를 출력하는 문제입니다.

 

대회당시를 생각하면 이미 나는 머리속에 문제가 들어오지도 않는 상태였고 팀원이 뭐라고 하는지 제대로 이해 못한 채 그냥 못풀어버린 문제.

 

지금 다시 생각해보면 정신만 차렸어도 풀었을 문제....

 

도둑입장에서 경찰과의 x축 거리 > 경찰입장에서 도둑과의 y축거리

도둑입장에서 경찰과의 y축 거리 > 경찰입장에서 도둑과의  x축거리

 

이 둘의 명제가 모두 참이면 (사실 오른쪽, 왼쪽, 위, 아래로 따져야 하긴 함.) NO

아니면 YES

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    vector<lld> yv(n), xv(n);
    for(int i=0;i<n;i++)
    {
        lld x, y;
        cin>>x>>y;
        yv[i] = y;
        xv[i] = x;
    }
    lld tx, ty;
    cin>>tx>>ty;
    bool right, left, down, up;
    right = left = down = up = false;
    for(int i=0;i<n;i++)
    {    
        //right
        if(abs(ty-yv[i])<=xv[i]-tx && xv[i]>=tx) right = true;
        //left
        if(abs(ty-yv[i])<=tx-xv[i] && tx>=xv[i]) left = true;
        //down
        if(abs(tx-xv[i])<=yv[i]-ty && yv[i]>=ty) down = true;
        // up
        if(abs(tx-xv[i])<=ty-yv[i] && ty>=yv[i]) up = true;
    }
    if(right && left && down && up) cout<<"NO";
    else cout<<"YES";
 
    return 0;
}

 

 

L. 동전 옮기기

o와x로만 이루어진 문자열이 있다.

여기서 두개를 골라 두 손가락 이동 을 한다.

두 손가락 이동이란?

두 문자의 순서는 유지하기만 하면(누가 앞이고 누가 뒤인지) 어디든 이동할 수 있다.

그렇게 이동하여서 제시된 문자열이 될 수 있는지 판별하는 문제.

 

현장에서는 너무 어렵게 느껴졌지만 다시 풀어보니 DP중에서도 가장 기초적이고 기초적이면서 기초적인 문제였다.

딱 정석으로 완전탐색으로 먼저 생각해본 뒤, 중복되는 연산을 줄이기 위해 메모이제이션을 하면 된다.

 

진짜 이 문제 못푼 내 자신이 너무 한심했다...;

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
int n, l, r;
 
bool dp(string& a, string& b, int pos, int n, int check, int aindex)
{
    if(pos==n && check==2) return true;
    bool ret = false;
    if(aindex==l || aindex==r) aindex++;
    if(aindex<n && b[pos]==a[aindex])
        ret |= dp(a, b, pos+1, n, check, aindex+1);
    if(check==0 && b[pos]==a[l])
        ret |= dp(a, b, pos+1, n, 1, aindex);
    if(check==1 && b[pos]==a[r])
        ret |= dp(a, b, pos+1, n, 2, aindex);
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    string a, b;
    cin>>a>>b;
    cin>>l>>r;
    if(dp(a, b, 0, n, 0, 0)) cout<<"YES";
    else cout<<"NO";
    return 0;
}

 

 

다른 문제도 풀게된다면 추가하도록 하겠습니다.