Codeforces Round #737 (Div. 2) 후기

A. Ezzat and Two Subsequences

풀이 보기

풀이

후에도 서술하겠지만, 이번 contest에서 C11로 제출한 것은 모두 실패했다. 하지만 같은 코드를 C++14로 제출한 것은 Accepted를 받았다. 이것으로 얻은 페널티는… 하..

A번 문제는 대체로 계산이 필요없는 문제가 많이 나온다. 이번에도 그런 문제였다.

정답은 ‘가장 큰 수를 제외한 수들의 평균 + 가장 큰 수’ 로 출력하면 된다.

코드

#include <stdio.h>

#define max(a, b) (((a) > (b)) ? (a) : (b))
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);

        double sum = 0;
        double maxV = -1e10;
        for (int i = 0; i < n; ++i) {
            double a;
            scanf("%lf", &a);
            sum += a, maxV = max(maxV, a);
        }
        sum -= maxV, sum /= (n - 1);
        printf("%.10lf\n", maxV + sum);
    }
    return 0;
}

B. Moamen and k-subarrays

풀이 보기

풀이

눈앞에 보인 방법으로 시도해서 알고리즘상으로 1번은 틀린 문제이다. 제출은 4번인가 했는데, 알고리즘은 맞춰도 C로 제출한게 문제인지..

푼 방법으로는 우선 모든 입력에 대해 index를 부여하고 저장한다. 이후 숫자를 오름차순으로 정렬한다.

만약 그때의 index들이 붙어있는 형태라면 그 원소는 분리하지 않아도 된다. 만약 아니라면 그 원소들은 정렬 이후 붙어있을 수가 없으므로 분리해주어야한다. 이런 방식으로 최소로 분리해야하는 개수를 셀 수 있다. 이 값을 이용하여 Yes / No를 판단하였다.

코드

#include <stdio.h>

#include <algorithm>
#include <vector>

using namespace std;

typedef struct Node {
    int v;
    int in;
} ND;

bool cmp(const ND& a, const ND& b) {
    return a.v < b.v;
}

#define M 100000
ND arr[M];
int n, k;

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &n, &k);
        for (int i = 0; i < n; ++i) {
            int a;
            scanf("%d", &a);
            arr[i] = (ND){a, i};
        }

        sort(arr, arr + n, cmp);

        for (int i = 1; i < n; ++i) {
            if (arr[i].in != arr[i - 1].in + 1) {
                --k;
            }
        }

        if (k > 0) {
            printf("Yes\n");
        } else {
            printf("No\n");
        }
    }
}

결과

Contest	Start time	Rank	Solved	Rating change	New rating
#737 (Div. 2)	2021/8/9 23:35	6358	2	-64	1418