Codeforce Round #748 (Div. 3)

제주도 여행을 다녀오는 동안 참가 못한 라운드가 많아서 Virtual partipication을 하나씩 하기 시작했다.

Div. 3 라운드인걸 모르고 있다가 문제 A가 너무 쉬워 당황했었다. A, B가 워낙 쉽기 때문에 문제 C부터 복기를 한다.

 

https://codeforces.com/contest/1593/problem/C

Problem - C - Codeforces

0번째 칸에서 한 칸씩 다가오는 고양이를 피하기 위해 k마리의 쥐가 n번째 칸에 있는 구멍으로 이동한다.

한 번에 한 마리의 쥐가 한 칸 움직이고 고양이가 한 칸 움직인다. 그리고 모두 탈출하거나 잡아 먹힐 때까지 반복한다.

입력은 n, k가 주어지고 k마리의 쥐의 시작 위치가 주어진다. 쥐의 시작 위치는 1이상 n-1 이하.

이때 최대로 탈출할 수 있는 쥐의 수를 출력하는 문제.

 

쥐의 시작 위치를 x라고 할 때, n-x를 배열에 넣고 오름차순으로 정렬을 한 후에 누적합이 n보다 작을 때까지 합하고 그 마리 수를 출력하면 된다고 생각했으나 계속 오답이 나와 부호나 부등호에 틀린 게 있나 고쳐봤지만 계속 오답이 나왔고 다른 풀이가 생각나지 않아 D1 문제로 넘어갔었다.

채점 내역을 확인하고 알게 됐는데 기존에 생각했던 알고리즘이 맞았으나 특정 케이스들에서 문제가 생기는 코드였다.

int sum = 0;
int cnt = 0;
for(int i = 0; i < v.size() && sum < n; i++) {
	sum += v[i];
	cnt++;
}
printf("%d\n", cnt - 1);

처음에 사용한 코드, sum < n을 for문에 시작할 때 확인하기 때문에 sum이 n을 넘어가고 나서야 반복문이 종료되고 cnt는 답보다 1만큼 더 클 것이다. 그래서 출력을 cnt - 1로 했다.

문제는 v[i]의 총합이 n보다 작은 경우에는 초과해서 더해지지 않는데 cnt - 1이 적용된다는 점에서 문제가 발생한다.

사실 저 코드를 작성할 때 뭔가 불안정해 보인다는 느낌이 들긴 했는데 생각해낸 알고리즘에 대한 의심이 더 커서 저 부분이 먼저 생각나지 않았다.

int sum = 0;
int cnt = 0;
for(int i = 0; i < v.size(); i++) {
  	if(sum + v[i] >= n) break;
  	sum += v[i];
  	cnt++;
}
printf("%d\n", cnt);

 변경한 코드. 너무 기초적인 실수라 창피하긴 하지만 이런 잘못을 다시 하지 않기 위해 복기를 하는 것이라 생각한다.

 

https://codeforces.com/contest/1593/problem/D1

N개의 양수인 정수 배열이 주어 질 때, 배열 중 한 값을 양의 정수 K로 빼는 연산을 반복해 배열 내의 모든 수를 같게 만드는 과정을 진행한다. 이 조건을 만족할 수 있는 K 중 가장 큰 값을 출력하는 것이 문제 D.

주어진 정수 배열의 값이 모두 같은 경우에는 K값이 무한히 커질 수 있기 때문에 그 경우에는 -1을 출력한다.

배열 내의 값 중 하나를 a1, 다른 값을 a2라고 할 때 k는 a1 = a2 - m * k ( a2 > a1이라 가정)을 만족해야 한다.

이항을 하면 m * k = a2 - a1, 즉 k는 a2 - a1의 약수라는 것을 알 수 있다.

주어진 배열을 오름차순으로 정렬한 후에 a2 - a1, a3 - a1, a4 - a1, ... , an - a1의 최대공약수를 구하면 K의 최댓값을 구할 수 있다. 

https://codeforces.com/contest/1593/problem/D2

D2는 같은 문제지만 N개의 양수 정수 배열 중 최소 반 이상을 같게 만들면 되는 문제.(N은 짝수)

K값을 최대로 하기 위해 절반보다 많이 고를 이유는 없기 때문에 절반을 고르는 문제라고 생각했다.

입력 조건에서 N은 4 이상 40 이하인데 40개 중 20개를 고르는 경우의 수가 너무 크기 때문에 D1의 방법을 그대로 가져올 수는 없었다. 그래서 다른 방법을 가져와야 할 텐데 꽤 많은 시간을 투자했지만 해결하지 못하고 문제를 넘어갔다.

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)

set<int> divs(int n) {  
    set<int> d;
    for (int dd = 1; dd * dd <= n; dd++)
        if (n % dd == 0) {
            d.insert(n / dd);
            d.insert(dd);
        }
    return d;
}

int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        int n;
        cin >> n;
        vector<int> a(n);
        forn(i, n)
            cin >> a[i];
        int k = -1;

        forn(i, n) {
            int minv = a[i];
            int same = 0;
            vector<int> d;
            forn(j, n) {
                if (a[j] == minv)
                    same++;
                else if (a[j] > minv)
                    d.push_back(a[j] - minv);
            }
            if (same >= n / 2) {
                k = INT_MAX;
                continue;
            }
            map<int,int> div_counts;
            for (int di: d)
                for (int dd: divs(di))
                    div_counts[dd]++;
            for (auto p: div_counts)
                if (p.second >= n / 2 - same)
                    k = max(k, p.first);
        }

        cout << (k == INT_MAX ? -1 : k) << endl;
    }
}

코드로 보는 것이 이해가 빨라 해설의 코드를 가져왔다. n개의 정수 중 i번째 정수를 기준으로 정한다. i번째 정수와 값이 같으면 same변수를 증가시키며 같은 값의 숫자를 센다. 그리고 i번째 정수보다 큰 정수들을 골라 ak - ai 값을 배열에 추가한다. 

same 변수가 n/2 이상이면 k값이 무한히 커질 수 있기 때문에 -1을 출력하고 그렇지 않으면 배열에 추가된 값들의 약수들을 map에 추가하고 이미 존재하면 개수를 증가시킨다.

그리고 이 과정이 끝나고 map에 추가된 약수들의 개수를 확인하고 n/2 - same 이상인 값이 있는지 확인한다.

그리고 그중 가장 큰 값이 i번째 정수를 가장 작은 수로 잡았을 때 최대인 k값이 된다.

정수들을 골라서 최대공약수를 구하는 것이 아니라 모든 약수의 개수를 저장하고 기준을 만족하는 약수 중 가장 큰 값을 찾는 방식.