[20/07/12] ucpc 연습문제

2020 / 07 / 03 (금) 코드포스 연습문제

후기

전에 공부했던 개념이 많이 나와서 좋았다! 항상 처음 접하는 개념만 나온다고 생각했는데 내가 풀었던 내용이 다시 나오니 확실히 빨리 풀 수 있었다.

A 수열과 시프트 쿼리 (17499)

 

 

혼자서 풀어보려하다가 자꾸 꼬여서 북님 코드 참고했다. 난 offset을 기존 배열을 이동한 만큼을 저장하려 했는데 그것보다 출력할 때 i + offset을 출력하면 되게 만드는 게 더 쉬운 것 같다. 인덱스 같은 경우는 n이 넘어가면 안 되므로 n을 나눈 나머지를 저장해야 한다. 전에 원형 큐를 공부할 때 인덱스를 넘기지 않게 하기 위해 n을 나눠서 인덱스를 접근했는데 이와 비슷한 것 같다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <cstring>
#include <map>
#define xx first
#define yy second
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;


int main() 
{
    int n, q;
    scanf("%d %d", &n, &q);
    
    vector<int> v(n);

    for (int i = 0; i < n; i++)
        scanf("%d", &v[i]);

    int offset = 0;

    for (int i = 0; i < q; i++)
    {
        int t;
        scanf("%d", &t);

        if (t == 1)
        {
            int p, x;
            scanf("%d %d", &p, &x);
            p--;
            p = (p + offset) % n;
            v[p] += x;
        }
        else
        {
            int s;
            scanf("%d", &s);
            if (t == 2)
                s = -s;
            offset = (offset + n + s) % n;
        }
    }

    for (int i = 0; i < n; i++)
        printf("%d ", v[(offset + i) % n]);

    return 0;
}

B 4연산 (14395)

 

 

dfs를 사용해서 연산의 최소 횟수를 구하는 문제. bfs.. 낯설지만 ucpc로 강제로 친해지는 중. bfs를 풀다가 전에 풀던 다익스트라 문제도 최단거리 구할 때 썼던 것 같은데 무슨 차이일까 싶었다. 알고보니 edge에 weight가 있다면 다익스트라로 풀고 weight가 1이면 bfs로 푸는 것 같다. 이 문제처럼 최단거리를 거치는 경로를 물어보는 문제를 역추적 문제라고 한다.

 

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int main()
{
	i64 s, t;
	scanf("%lld %lld", &s, &t);
	
	if (s == t)
	{
	    printf("0\n");
	    return 0;
	}
	
	map<i64, pair<i64, char>> visited;
	visited[s] = pair<i64, char>(s, '.');
	
	queue<i64> q;
	q.push(s);
	
	while (!q.empty())
	{
	    auto now = q.front();
	    q.pop();
	    
	    if (now * now <= t && visited.find(now * now) == visited.end())
	    {
	        visited[now * now] = pair<i64, char>(now, '*');
	        q.push(now*now);
	    }
	    
	    if (now + now <= t && visited.find(now + now) == visited.end())
	    {
	        visited[now + now] = pair<i64, char>(now, '+');
	        q.push(now+now);
	    }
	    
	    if (now / now <= t && visited.find(now / now) == visited.end())
	    {
	        visited[now / now] = pair<i64, char>(now, '/');
	        q.push(now/now);
	    }
	}
	
	if (visited.find(t) == visited.end())
	{
	    printf("-1");
	    return 0;
	}
	
	i64 last = t;
	string ans;
	
	while (last != s)
	{
	    ans.push_back(visited[last].yy);
	    last = visited[last].xx;
	}
	
	reverse(all(ans));
	
	cout << ans << "\n";

	return 0;
}

 

 

 

 

이 문제에서 시간복잡도를 구하는 게 애매했다. bfs의 시간복잡도는 e + v이지만 v가 몇 개인지 알 수 없기 때문이다. 그래서 대략적으로 얼마나 걸릴지 계산해보았다.

 

 

 

C 학생 번호 (1235)

 

학생 수가 최대 1000이고 문자열의 길이가 100보다 작거나 같다. 최대 십만 번 반복하므로 완전탐색해도 시간 내에 돌아갈 것이다. 그래서 substr을 사용해서 뒷자리부터 학번을 자르고 중복인 학번을 제거한 다음 남은 수의 개수가 n과 같은지 확인했다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <cstring>
#include <map>
#define xx first
#define yy second
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;


int main() 
{
    int n;
    scanf("%d", &n);

    vector<string> v(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];

    int s_size = v[0].size();
    for (int k = 1; k <= s_size; k++)
    {
        vector<string> s(n);
        for (int i = 0; i < n; i++)
            s[i] = v[i].substr(s_size-k);

        sort(s.begin(), s.end());
        s.erase(unique(s.begin(), s.end()), s.end());
        if (s.size() == n)
        {
            printf("%d\n", k);
            return 0;
        }
    }
    printf("%d\n", n);
    return 0;
}

D 집 구하기 (13911)

 

다익스트라! 저번 ucpc 연습 때 다익스트라를 사용해야 하는 문제가 나와서 공부했었다. 이번 문제에 또 나와서 조금 편했음ㅋㅋ 이 문제는 맥도날드와 스타벅스까지의 최단거리를 구한 다음 x, y를 만족하는 노드 중 최단 노드를 구하면 되는 문제이다. 처음에 x를 만족하는 노드와 거리를 구하고 y를 만족하는 노드와 거리를 따로 저장한 다음 두 pair벡터의 교집합을 구하려 했는데 이러려면 n^2이 된다. 그래서 x, y를 따로 구분하지 않고 1부터 n까지 dist 배열을 돌면서 x, y이하인 점을 찾고 최솟값을 저장했다. 다 풀고 지금 드는 생각인데 집이 존재하지 않으면 -1을 출력해야 했다. 따로 지정해주지 않았는데 왜 맞았나 싶었더니 최솟값을 초기에 -1로 설정해줘서 그런 것 같다. 맞아서 다행이다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <cstring>
#include <map>
#define xx first
#define yy second
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;


struct Edge
{
    Edge(int to_, int w_) : to(to_), w(w_) {}
    int to, w;
};

vector<Edge> edge[300005];
bool visited[300005];

vector<int> calc(int v, int x, vector<int> m)
{
    vector<int> dist(v+1, -1);
    memset(visited, false, sizeof(visited));
    
    priority_queue<ii, vector<ii>, greater<ii>> pq;
    
    for (int i = 0; i < m.size(); i++)
    {
        dist[m[i]] = 0;
        pq.emplace(0, m[i]);
    }
    
    while (!pq.empty())
    {
        
        auto now = pq.top();
        pq.pop();
        
        if (visited[now.yy])
            continue;
        
        visited[now.yy] = true;
        
        for (auto & e : edge[now.yy])
        {
            int newD = dist[now.yy] + e.w;
            
            if (dist[e.to] != -1 && dist[e.to] < newD)
                continue;
            
            dist[e.to] = newD;
            pq.emplace(dist[e.to], e.to);
        }
    }
    
    return dist;
}

int main() 
{
    int v, e;
    scanf("%d %d", &v, &e);
    
    for (int i = 1; i <= e; i++)
    {
        int a, b, t;
        scanf("%d %d %d", &a, &b, &t);
        
        edge[a].emplace_back(b, t);
        edge[b].emplace_back(a, t);
    }

    int m, x;
    scanf("%d %d", &m, &x);
    vector<int> vm(m);
    for (int i = 0; i < m; i++)
        scanf("%d", &vm[i]);

    int s, y;
    scanf("%d %d", &s, &y);
    vector<int> vs(s);
    for (int i = 0; i < s; i++)
        scanf("%d", &vs[i]);
        
    vector<int> mdist;
    vector<int> sdist;

    mdist = calc(v, x, vm);
    sdist = calc(v, y, vs);
    
    i64 min = -1;
    for (int i = 1; i <= v; i++)
    {
        if (!(0 < mdist[i] && mdist[i] <= x && 0 < sdist[i] && sdist[i] <= y))
            continue ;

        if (min == -1 || mdist[i] + sdist[i] < min)
            min = mdist[i] + sdist[i];
    }
    
    printf("%d", min);
    return 0;
}

 

    for (int i = 1; i <= v; i++)
    {
        if (0 < mdist[i] && mdist[i] <= x && 0 < sdist[i] && sdist[i] <= y)
        {
            if (min == -1)
                min = mdist[i] + sdist[i];
            else
            {
                if (mdist[i] + sdist[i] < min)
                    min = mdist[i] + sdist[i];
            }
        }
    }

 

처음 짤 떄 if문을 이렇게 설정했다. 지금 보니 똑같은 기능을 if 문 두 개로 나눴구나. if문은 되도록 중첩을 안 하는 게 좋아서 아래처럼 구현했다. 3중 if문을 하나로 나눔..

 

    for (int i = 1; i <= v; i++)
    {
        if (!(0 < mdist[i] && mdist[i] <= x && 0 < sdist[i] && sdist[i] <= y))
            continue ;

        if (min == -1 || mdist[i] + sdist[i] < min)
            min = mdist[i] + sdist[i];
    }

 

E 겹치는 선분 (1689)

 

처음에 이 문제를 좌표 압축으로 풀어보려 했었다. 선분의 개수가 1000000개이므로 좌표압축을 해서 선형으로 풀면 되지 않을까? 싶었는데 O(N)만에 못 풀고 N^2으로 해서 해당 영역을 세어야 했다. 이 문제는 해당 구간 내의 값은 상관 없고 구간이 시작할 때 1을 세어주고 끝날 때 1을 감소시켜 주면 된다. 그러므로 시작과 끝을 따로 저장을 해서 시작이면 +1을 끝나면 -1을 해주도록 저장한 다음, 시점을 전부 정렬해서 세어주면 된다. 문제에서 선분의 끝 점에서 겹치는 것은 세지 않는다 해서 난 이전 점을 저장한 다음 점이 바뀔 때 세도록 했었다. 이건 먼저 감소 시킨 다음 증가 시키면 해결할 수 있다. pair로 정렬하면 자동으로 감소하는 것이 먼저오므로 이 부분은 상관하지 않고 계산하면 된다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;


int main() {
    int n;
    scanf("%d", &n);
    
    vector<ii> event;
    for (int i = 0; i < n; i++)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        event.emplace_back(x, 1);
        event.emplace_back(y, -1);
    }
        
    sort(all(event));

    int count = 0;
    int max = 0;
    for(int i = 0; i < event.size(); i++)
    {
        count += event[i].yy;
        if (max < count)
        {
            max = count;
        }
    }
    
    printf("%d\n", max);
    
    return 0;
}

F 삼삼한 수 (17252)

 

숫자가 작은 것 같아서 부분집합을 만들어서 풀 수 있을 것 같았다. 계산해보니 21억보다 작은 수 중 가장 큰 3의 제곱은 19제곱이었다. 0부터 19까지 3의 제곱수를 미리 구한 다음에 이 배열의 부분집합을 만들어서 모든 삼삼한 수를 만들었다. 혹시 메모리 초과가 날 까봐 모든 삼삼한 수의 개수를 확인해보았더니 대략 천만 개였다. 메모리 제한에 걸리지 않아서 다행이다. 다음으로 입력을 받고 배열 안에 삼삼한 수가 있다면 YES를 아니면 NO를 출력한다. 저번주에 부분집합 만드는 걸 배웠는데 오늘 써먹어서 뿌듯했다ㅋㅋ

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
 
int main() {
    int n;
    scanf("%d", &n);
    
    if (n == 0)
    {
        printf("NO");
        return 0;
    }
    
    i64 num = 1;
    
    vector<i64> t(20);
    for (int i = 0; i <= 19; i++)
    {
        t[i] = num;
        num *= 3;
    }
    
    vector<i64> ans;
    for (int i = 0; i < (1 << 20); ++i) 
    { 
        i64 sum = 0;
        for (int j = 0; j < 20; ++j)
        { 
            if (i & (1 << j)) 
                sum += t[j];
        }
        ans.push_back(sum);
    }
    
    if (find(ans.begin(), ans.end(), n) != ans.end())
        printf("YES");
    else
        printf("NO");
    return 0;
}

 

G 시간 관리 (1263)

 

마감 시간이 가장 긴 것부터 차례대로 구했다. 전에 비슷한 문제를 풀었는데 그 떄도 끝나는 시간 순서로 풀었던 게 기억났다. 아무튼.. 마감 시간이 가장 깉 것부터 수행하고 다음으로 긴 걸 수행하고 하다가 모든 일이 다 끝나는 시점이 0보다 작으면 -1을 출력했다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

bool sortbyfirst(const pair<int,int> &a, const pair<int,int> &b) 
{ 
    return (a.yy > b.yy); 
}

int main() {
    int n;
    scanf("%d", &n);
    
    vector<ii> v(n);
    for (int i = 0; i < n; i++)
        scanf("%d %d", &v[i].xx, &v[i].yy);
        
    sort(v.begin(), v.end(), sortbyfirst);
    
    int start = v[0].yy - v[0].xx;
    for (int i = 1; i < n; i++)
    {
        if (v[i].yy < start)
            start = v[i].yy;
        start -= v[i].xx;
    }
    
    if (start < 0)
        printf("-1");
    else
        printf("%d", start);
    
    return 0;
}