[codeforces] Codeforces Round #748 (Div. 3) A, C

1. A

- 간단한 수학 문제

- 세개의 숫자중 가장큰것에서 +1 해주면된다

- 이때 가장 큰 수가 유일한 한 값이라면 0을 출력해주는 예외처리만 해주면된다.

    while (T--)
    {
        int maxC;
        int A[3];
        cin >> A[0] >> A[1] >> A[2];
        maxC = max(A[0], max(A[1], A[2]));
        map<int, int> dic;
        for (int i = 0; i < 3; i++)
        {
            dic[A[i]]++;
        }
        int a[3];
        for (int i = 0; i < 3; i++)
        {
            a[i] = maxC - A[i];
            a[i]++;
            if (dic[maxC] == 1 && a[i] == 1)
            {
                a[i]--;
            }
            
        }
        cout4(a[0], " ", a[1], " ");
        cout2(a[2], " \n");
    }

 

 

2. B

- 구현문제

- 25로 나누어지는 수를 만들어야하는데

- 이때 일의자리와 십의자리수만 보면된다

- 끝 두자리로 "25", "50", "75" , "00" 이 와야 25로 나눌 수 있기 때문

- 그러므로 문자열로 입력을 받고, 앞에서부터 인덱스를찾아 몇개를 제외시켜야하는지 계산 후

- 가장 작은 값을 출력한다.

반성: 하드코딩으로 문제를 해결하려다가 꼬이고 꼬여 틀렸다.

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int T;
    cin >> T;
    while (T--)
    {
        string a;
        cin >> a;
        reverse(a.begin(), a.end());
        int answer[4] = {1111, 1111, 1111, 1111};
        map<int, vector<int>> dic;
        for (int i = 0; i < a.size(); i++)
        {
            dic[a[i] - '0'].push_back(i);
        }
        pair<int, int> find[] = {{2, 5}, {5, 0}, {7, 5}, {0, 0}};
        for (int i = 0; i < 4; i++)
        {
            auto [s, f] = find[i];
            if ((dic[f].size() > 0 && dic[s].size() > 0) || (dic[f].size() > 1 && f == 0 && s == 0))
            {
                int ff = dic[f][0];
                auto ss = lower_bound(dic[s].begin(), dic[s].end(), ff + 1);
                if (ss != dic[s].end())
                {
                    answer[i] = ff + (*ss - ff - 1);
                }
            }
        }
        cout << *min_element(&answer[0], &answer[0] + 4) << "\n";
    }
}

 

3. C

- 그리디 + 정렬 + 이진검색

- 가장 많은 쥐를 탈출시켜야한다.

- 한턴에 한번씩 쥐를 한마리만 움직일 수 있다.

- 이때 최대한 많이 탈출시키는것.

 

- 가장 구멍과 가까운 쥐들을 포함시키는것이 최대가된다.

- 그렇지 않은 경우에서 답이나왔다고 가정해보면,

- 선택한 한마리를 가장 구멍과 가까운쥐들로 교체해도 손해는 없음을 알 수 있다.

 

- 그러므로 쥐들을 정렬하고, 이진 검색으로 

- 구멍에서 mid번째 쥐부터시작해서 n번째 쥐 까지 전부 탈출가능한지를 조사해야한다.

 

반성 : 이진 검색을 잘못 설정하여 한번 틀렸다. => https://www.acmicpc.net/blog/view/109

bool go_hole(int idx)
{
    int cat = 0;
    for (int i = idx; i < m.size(); i++)
    {
        if (cat >= m[i])
        {
            return false;
        }
        cat += (n - m[i]);
    }
    return true;
}
 
int bisearch()
{
    int lo = 0, hi = m.size() - 1;
    int mid = 0;
    while (lo != hi)
    {
        mid = (lo + hi) / 2;
        if (go_hole(mid))
        {
            hi = mid;
        }
        else
        {
            lo = mid + 1;
        }
    }
    return m.size() - hi;
}

4. D1

- GCD 문제

- 주어진 배열에서 가장 최소값과 나머지와의 차이들을 계산하여

- 이들의 최대 공약수를 구하는 문제.

- 주의해야할점은 차이들의 최대 공약수가 0일때, 즉 모든 값들이 같을 때 -1 처리해줘야한다 

반성: 차이가 0일때 0을 출력하게했다.

int gcd(int x, int y)
{
    if (y == 0)
    {
        return x;
    }
    else
    {
        return gcd(y, x % y);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        map<int, int> dic;
        for (int i = 0; i < n; i++)
        {
            int a;
            cin >> a;
            dic[a]++;
        }
        if (dic.size() >= 2)
        {
            auto before = dic.begin();
            int min1 = before->first;
            int min2 = next(dic.begin(), 1)->first;
            int answer = abs(min1 - min2);
            for (auto it = next(dic.begin(), 2); it != dic.end(); it++)
            {
                int b = abs(it->first - min1);
                answer = gcd(answer, b);
                before = it;
            }
            cout << answer << "\n";
        }
        else
        {
            cout << -1 << "\n";
        }
    }
}

 

5. D2

?

6. E

- BFS 문제

- 주어진 트리에서 간선이 1개인 노드들을 전부 없애는것

- 이런 제거를 k 번 했을 때 남아있는 노드들의 개수를 구하는 문제이다.

 

- bfs에서 시작점을 "잎"노드들로 설정하여 문제를 해결하였다.

- 즉, queue 에 "잎"노드들을 담아,

- 잎과 연결된 간선을 제거하면서,

- 연결된 노드가 잎이되는지 검사한 후

   (set 을 사용해서 간선을 제거하고 잎이되는지 검사하였다.)

- 잎이되면 queue에 삽입하도록 하였다.

vector<set<int>> adjList;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;
    while (T--)
    {
        int n, k;
        cin >> n >> k;
        adjList.clear();
        adjList.resize(n);
        queue<pair<int, int>> q;
        // 입력
        for (int i = 0; i < n - 1; i++)
        {
            int a, b;
            cin >> a >> b;
            a--;
            b--;
            adjList[a].insert(b);
            adjList[b].insert(a);
        }
        // 잎들을 queue에 넣는다.
        for (int i = 0; i < n; i++)
        {
            if (adjList[i].size() <= 1)
            {
                q.push({0, i});
            }
        }
        
        int answer = 0;
        // bfs
        while (!q.empty())
        {
            auto [d, here] = q.front();
            q.pop();
            // K번째에 도달
            if (d == k)
            {
                break;
            }
            answer++;
            // 만약 간선이 0 인 노드이면 계속 계산할 필요가 없다.
            if (adjList[here].size() == 0)
            {
                answer = n; // 두개의 노드들만 있을 경우 노드 한개가 큐에 두번들어가게된다.
                continue;
            }
            int b = *adjList[here].begin();

            adjList[b].erase(here);
            if (adjList[b].size() <= 1)
            {
                q.push({d + 1, b});
            }
        }
        cout << n - answer << "\n";
    }
}