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

실제 참여는 하지 않고 이번 라운드의 문제를 풀어보고 푼 내용에 대해 기록해두고자 한다.

A. Garden :: http://codeforces.com/contest/915/problem/A

k % a[i]가 된다면 k / a[i]의 최솟값을 구해달라는 문제이다.

#include <iostream>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
int main()
{
    int n, k;
    cin >> n >> k;
 
    int ans = 98754312;
    for (int i = 0; i < n; i++)
    {
        int val;
        cin >> val;
 
        if (k % val == 0)
            ans = min(ans, k / val);
    }
    cout << ans;
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

B. Browser :: http://codeforces.com/contest/915/problem/B

구현으로 문제를 해결하였다.

특정 범위에 어떻게 존재하는지 조건에 맞게 식을 세워 문제를 풀면 해결이 가능하다.

좀 더 간결한 코드들이 존재하는 것 같아서 스터디를 통해 좀더 파악해보려 한다.

#include <iostream>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
int main()
{
    int n, pos, l, r;
    cin >> n >> pos >> l >> r;
 
    int ans = 0;
 
    if (l == 1 && r == n)
        ans = 0;
 
    else if (l < pos && pos < r)
    {
        if (l == 1)
            ans += (r - pos) + 1;
        else if (r == n)
            ans += (pos - l) + 1;
        else
            ans += (r - l) + min(r - pos, pos - l) + 2;
    }
    else if (pos == l)
    {
        if (l == 1)
            ans = r - l + 1;
        else
        {
            if (r == n)
                ans = 1;
            else
                ans = r - l + 2;
        }
    }
    else if (pos == r)
    {
        if (r == n)
            ans = r - l + 1;
        
        else
        {
            if (l == 1)
                ans = 1;
            else
                ans = r - l + 2;
        }
    }
 
    else if (pos < l)
    {
        if (r == n)
            ans  = l - pos + 1;
        else
            ans = l - pos + (r - l) + 2;
    }
    else if (pos > r)
    {
        if (l == 1)
            ans = pos - r + 1;
        else
            ans = pos - r + (r - l) + 2;
    }
    cout << ans;
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

C. Permute Digits :: http://codeforces.com/contest/915/problem/C 

개인적으로 가장 재미있는 문제였다.

필자가 생각한 알고리즘은 다음과 같다.

예를들어보자.

4950

5500이 주어졌을 때 우리는 가장 앞자리수가 뭔지 파악할 수 있다.

4가 가장 앞자리 수이고, 4950이 최대 수여도 5500보다 작으므로 4는 가능하고, 5는 5049에서 5940까지 만들 수 있기에 5도 가능하다.

9는 불가능하고 0은 가능하다.

따라서 우리는 최대 수를 찾아야하기에 4950을 내림차순 정렬하여 9540으로 잡아 둔 후 문제를 풀어본다.

first, last를 이용하여 현재수를 오름차순, 내림차순으로 정렬해서 앞자리수를 고정시킨 후 최소 ~ 최대 수를 만들어본다.

이때 한계치에 해당하는 한계수보다 작거나 같다면 이 수는 후보가 될 수 있다.

즉, 5를 기준으로두고 049를 오름차순, 내림차순하면 5049 ~ 5940이 된다.

그 후 확정된 자리수는 지워가며 한자리수가 남을 때 까지 반복해준다. 이때 가정이 답은 무조건 존재한다이기에 좀 더 쉽게 접근이 가능하다.

이렇게 그리디하게 수를 하나씩 찾아 내려가면 우리는 문제를 해결 할 수 있게된다.

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
 
using namespace std;
 
 
bool comp(const char &a, const char &b)
{
    return a > b;
}
int main()
{
    string str, tmp, ans = "";
    cin >> str >> tmp;
 
    // 가정 :: 정답은 항상 존재한다.
    // 예외처리 1 :: 두수가 같거나 두 수의 크기가 1일때
    if (stoll(str) == stoll(tmp) || str.size() == 1 && tmp.size() == 1)
    {
        cout << str << endl;
        return 0;
    }
    // 예외처리 2 :: 한계수가 더 클때는 그냥 내림차순이 정답
    if (str.size() < tmp.size())
    {
        sort(str.begin(), str.end(), comp);
        cout << str << endl;
        return 0;
    }
 
    bool same = true; // 마지막 수가 한계수의 마지막 수와 같다면 true
    sort(str.begin(), str.end(), comp);
    
    while (1)
    {
        // 하나 남았을 때 그대로 추가해주면 된다.
        if (str.size() == 1)
        {
            ans += str[0];
            break;
        }
 
        // 현재까지 본 수중 마지막 수가 서로 다르다면
        // 즉, 한계수가 현재 내가 만들고있는 수보다 더 큰 값일테니
        // 내림차순 후 정답을 구할 수 있다.
        if (!same)
        {    
            sort(str.begin(), str.end(), comp);
            ans += str;
            break;
        }
 
        for (int i = 1; i < str.size(); i++)
        {
            string first = str, last = str;
            sort(first.begin() + 1, first.end());
            sort(last.begin() + 1, last.end(), comp);
 
            // 현재수를 오름차순, 내림차순한 두 수중 하나라도 
            // 한계수보다 작거나 같다면 마지막 자리수로 가능하다.
            if (stoll(first) <= stoll(tmp) || stoll(last) <= stoll(tmp) )
            {
                ans += str[0];    
                if (tmp[0] == last[0])
                    same = true;
                else
                    same = false;
                str.erase(str.begin(), str.begin() + 1);
                tmp.erase(tmp.begin(), tmp.begin() + 1);
            
                break;
            }
 
            else
                swap(str[0], str[i]);
        }
    }
 
    cout << ans;
 
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

D. Almost Acyclic Graph :: http://codeforces.com/contest/915/problem/D

위상정렬로 문제를 해결할 수 있다.

결국 DAG를 찾아야한다는 것은 사이클이 존재하면 안된다는 것이다.

그렇다면 우리는 각 노드마다 간선을 하나씩 지운다 가정하고 이 그래프가 DAG인지 확인해보면 된다.

DAG인지 확인하는 방법은 위상정렬 알고리즘을 이용하면 확인 할 수 있다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
 
using namespace std;
 
vector<int> vc[502];
int line[502]; 
 
int main()
{
    int n, m;
    cin >> n >> m;
 
    for (int i = 0; i < m; i++)
    {
        int from, to;
        cin >> from >> to;
        vc[from].push_back(to);
 
        line[to]++;
    }
 
    for (int t = 1; t <= n; t++)
    {
        bool chk = true;
 
        int tline[502];
        for (int i = 1; i <= n; i++)
            tline[i] = line[i];
 
        if (tline[t] == 0)
            continue;
        tline[t]--;
        queue<int> q;
        for (int i = 1; i <= n; i++)
            if (tline[i] == 0)
                q.push(i);
 
        for (int j = 0; j < n; j++)
        {
            if (q.empty())
            {
                chk = false;
                break;
            }
 
            int cur = q.front();
            q.pop();
 
            for (int j = 0; j < vc[cur].size(); j++)
            {
                int next = vc[cur][j];
 
                if (--tline[next] == 0)
                    q.push(next);
            }
        }
 
        if (chk)
        {
            cout << "YES" << endl;
            return 0;
        }
 
        tline[t]++;
    }
    cout << "NO" << endl;
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>