KEYENCE Programming Contest 2021

KEYENCE Programming Contest 2021

KEYENCE Programming Contest 2021

 

KEYENCE Programming Contest 2021에 대한 해설입니다.

 

 * 이 글은 code-review 항목의 포스트입니다. code-review 항목에 대해 자세히 알아보고 싶다면, 클릭!

 * 문항 원문은 아래 주소에서 확인 가능합니다.

 - atcoder.jp/contests/keyence2021 [ 바로 가기 ]

 

[2021.01.17] 초판 발행

 

 ARC 수준으로 출제된 KEYENCE Programming Contest 2021에 대한 후기입니다. 초반에 A번과 B번은 빠르게 풀이하였지만, 그 이후로는 풀이를 못 했습니다. 나머지 문제는 풀이한 다음에 업데이트하겠습니다.

 

[A번] Two Sequences 2

 

[문제 및 풀이]

 

 두 수열 ${a_i}$와 ${b_i}$가 주어졌을 때, 다음을 구하는 문제이다.

 

$c_n = \max_{1 \leq i \leq j \leq n } a_i b_j$

 

[구현]

 

 $N$ 제한이 $2 \times 10^5$이기 때문에, $O(N^2)$로 풀이할 수 없다. 그런데 ${c_i}$를 모두 구하는 것이기 때문에, 어떤 항을 구할 때 그 이전에 구한 정보를 이용해야 한다. 어떤 항은 바로 전 항과 검토했던 $a_i$ 중에 최댓값과 새로운 $b_i$의 곱만 비교하면 된다. 최댓값만 구하는 것이기 때문에 그 이외는 검토할 필요가 없기 대문이다.

 

[예시 답안]

 

#include <stdio.h>
#define Max 250000
 
int N;
long long a[Max], b[Max], Ans, A_Max;
 
int main() {
    int i;
 
    scanf("%d", &N);
    for (i = 0; i < N; i++) scanf("%lld", &a[i]);
    for (i = 0; i < N; i++) scanf("%lld", &b[i]);
 
    for (i = 0; i < N; i++) {
        A_Max = (A_Max > a[i]) ? A_Max : a[i];
        Ans = (Ans > A_Max*b[i]) ? Ans : A_Max * b[i];
        printf("%lld\n", Ans);
    }
 
    return 0;
}
 

 

[B번] Mex Boxes

 

[문제 및 풀이]

 

 $K$개의 상자와 수가 적혀 있는 $N$개의 공이 있다. 각 공을 상자에 넣은 후에, 각 상자에 $0$ 이상의 수 중에서 상자에 들어있지 않은 최소의 수를 구해서 상자에 적는다. 이렇게 상자에 적힌 수의 값의 합이 최대가 되도록 하면 된다.

 

 욕심쟁이 기법으로 접근하면 된다. (1) 공에 적힌 수를 정렬하고, (2) 상자는 작은 것부터 우선순위가 높은 것으로 간주한다. 각 공을 처리할 때, 공에 적힌 수보다 $1$이 작은 원소가 들어있는 상자 중에서 우선순위가 제일 높은 것에 추가를 한다.^[각주:1] 이 경우가 한 원소를 추가할 때, 실질적으로 구하고자 하는 정답을 크게 하는 것으로 이어지고, 이 경우가 최선이다. 각 상자에는 상자에 들어있는 공 중에서 최댓값을 항상 갱신한다.^[각주:2]

 

[구현]

 

 공을 지칭하는 위치(소스코드에서의 $i$)와 상자를 지칭하는 위치(소스코드에서의 $u$)를 동시에 바꾸어 나간다. 공을 하나하나 검토하는 것이기 때문에 공을 지칭하는 위치는 차례로 하나 넣어가면 된다. 만약, 상자에 공을 넣게 되면 상자의 위치를 하나 증가시킨다. (1) 증가를 시키다가 범위를 넘어서거나, (2) 지칭하는 상자의 위치가 조건에 많지 않으면, 그 이외에 상자를 지칭하는 위치를 초기화 시킨다. 만약 새로 넣으려는 상자에 적힌 수가 공에 적힌 수보다 작으면 더 이상 진행할 필요가 없다. 이는 $n$을 넣으려고 하는데, $n$미만의 수 중에서 가장 큰 수가 $n-2$라면, $n$이상의 수를 아무리 넣어도 정답에 영향을 미치지 않는다.

 

[예시 답안]

 

#include <stdio.h>
#include <algorithm>
#define Max 350000
 
using namespace std;
 
int N, K, Ans;
int d[Max], D[Max];
 
int main() {
    int i, u;
 
    scanf("%d%d", &N, &K);
    for (i = 0; i < N; i++) scanf("%d", &d[i]);
    sort(d, d + N);
 
    for (i = 0; i < K; i++) D[i] = -1;
 
    for (i = u = 0; i < N; i++) {
        if ((u == K) || (D[u] != d[i] - 1)) u = 0;
 
        if (D[u] == d[i] - 1) {
            D[u]++, u++;
            continue;
        }
 
        if (D[u] < d[i] - 1) break;
    }
 
    for (i = 0; i < K; i++) Ans += D[i] + 1;
    printf("%d", Ans);
 
    return 0;
}
 

[C번] (작성 전)

 

[문제 및 풀이]

 

[구현]

 

[예시 답안]

 

 

 

[D번] (작성 전)

 

[문제 및 풀이]

 

[구현]

 

[예시 답안]

 

 

 

[E번] (작성 전)

 

[문제 및 풀이]

 

[구현]

 

[예시 답안]

 

 

 

[F번] (작성 전)

 

[문제 및 풀이]

 

[구현]

 

[예시 답안]

 

 

 

1. 문제에서는 모든 공을 어떤 상자에 넣어야 된다고 나오지만, 조건을 만족하는 경우가 없으면 넘어가면 된다. 그냥 넘어가는 경우나 조건에 만족하지 않은 곳에 넣는 것이나 정답에 영향을 주지 않기 때문이다. [본문으로]
2. 조건에 맞도록만 상자에 넣었기 때문에, 어떤 상자의 최댓값이 $n$이면 $0$부터 $n$까지 모든 수가 들어있는 것이다. [본문으로]