[Codeforces] Educational Codeforces Round 38 (Rated for Div. 2) 이야기

A. Word Correction :: http://codeforces.com/contest/938/problem/A

간단한 문제이다. 모음이 연속해서 나오면 제거해주면 된다.

이때 조심해야 할 점은 a,e,i,o,u와 y도 포함된다는 점이다.

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

#include <iostream> #include <cstdio> #include <string>   using namespace std;   int main() {     int n;     scanf("%d", &n);       string str;     cin >> str;       int len = str.size();       string ans = "";     for (int i = 0; i < len; i++)     {         if (i != 0 && str[i] == 'a' || str[i] == 'e' || str[i] == 'i' || str[i] == 'o' || str[i] == 'u' || str[i] == 'y')             if (str[i - 1] == 'a' || str[i - 1] == 'e' || str[i - 1] == 'i' || str[i - 1] == 'o' || str[i - 1] == 'u' || str[i -1 ] == 'y')                 continue;         ans += str[i];     }     cout << ans;     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus

B. Run For Your Prize :: http://codeforces.com/contest/938/problem/B

1에서 +1씩 늘리고 100000에서 -1씩 줄여 총 몇번만에 끝나는지 파악해주면 된다.

난이도는 A와 비슷한 것 같다.

복잡도는 O(N)이다.

 

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
 
using namespace std;
 
bool arr[1000002];
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
    {
        int val;
        scanf("%d", &val);
 
        arr[val] = true;
    }
 
    int time = 0;
    int s = 1, e = 1000000;
    int ans = 0;
    while (s + time <=  e - time)
    {
    //    cout << "s + time :: " << s + time << " e - time :: " << e - time << " ans :: " << ans << endl;
        time++;
        if (arr[s + time])
        {
            ans = max(ans, time);
            arr[s + time] = false;
        }
        if (arr[e - time])
        {
            ans = max(ans, time);
            arr[e - time] = false;
        }
    }
    cout << ans;
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

D. Buy a Ticket :: http://codeforces.com/contest/938/problem/D

well-known 문제라고 들었다.

어떤 정점에서 다른 정점으로 갔다가 다시 돌아와야하는데

갔다올때의 최소 비용이 드는 곳으로 다녀와야하는 문제이다.

이 문제를 풀기위해 존재하지 않는 0번정점 -> 1~n번 정점으로 간선의 가중치는 각 정점에 있는 비용을 가중치로 한다.

그리고 각 정점마다의 간선의 가중치는 *2를 해준다.

그렇게되면 0번에서 시작한 다익스트라 한번으로 이 문제의 정답을 구할 수 있게 된다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
#include <memory.h>
 
#define INF 10e18
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, int> pli;
 
vector<pli> vc[200002];
ll dist[200002];
 
int main()
{
    int V, E;
    scanf("%d %d", &V, &E);
 
    for (int i = 0; i < E; i++)
    {
        ll from, to, val;
        scanf("%lld %lld %lld", &from, &to, &val);
 
        val *= 2;
 
        vc[from].push_back({ val, to });
        vc[to].push_back({ val, from });
    }
 
    for (int i = 1; i <= V; i++)
    {
        ll val;
        scanf("%lld", &val);
 
        vc[0].push_back({ val, i });
    }
 
    priority_queue<pli, vector<pli>, greater<> > pq;
 
    pq.push({ 0, 0 });
    fill(dist, dist + 200002, INF);
    dist[0] = 0;
 
    while (!pq.empty())
    {
        int here = pq.top().second;
        ll cost = pq.top().first;
 
        pq.pop();
        if (cost > dist[here])
            continue;
 
 
        for (int i = 0; i < vc[here].size(); i++)
        {
            int next = vc[here][i].second;
            ll nextCost = vc[here][i].first + cost;
 
            if (nextCost < dist[next])
            {
                dist[next] = nextCost;
                pq.push({ nextCost, next });
            }
        }
    }
 
    for (int i = 1; i <= V; i++)
        printf("%lld ", dist[i]);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>