[코드포스] Grakn Forces 2020

대회 링크: codeforces.com/contest/1408

A번 문제: codeforces.com/contest/1408/problem/A

 

  세 개의 수열(Sequence) a, b, c가 존재한다. 이때 수열의 길이는 모두 n으로 동일하다. 또한 각 인덱스에 따른 ai, bi, ci는 서로 다르다. 이때 다음의 조건을 만족하는, 길이가 n인 수열 p를 하나라도 찾으면 된다.

 

[ 문제 해설 ]

 

  기본적으로 ai, bi, ci가 서로 다르다는 조건이 있다. 따라서 일단 a[0]를 출력한 뒤에 그다음부터는 그리디(greedy)하게 하나씩 출력하면 된다. 이때 (순환적으로) 인접한 두 수가 서로 달라지도록 하면 된다. 매번 바로 이전에 출력했던 수를 제외하고 다른 수를 하나 출력하도록 하자. 단, 마지막 수를 출력할 때는 첫째 수 또한 제외하고 출력해야 한다.

 

[ 정답 코드 ]

 

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    c = list(map(int, input().split()))

    # 첫 번째 수 출력
    now = a[0]
    print(now, end=' ')

    # n - 2개의 수 출력
    for i in range(1, n - 1):
        if now != a[i]:
            now = a[i]
        elif now != b[i]:
            now = b[i]
        elif now != c[i]:
            now = c[i]
    print(now, end=' ')
    
    # 마지막 수 출력
    if now != a[n - 1] and a[n - 1] != a[0]:
        now = a[n - 1]
    elif now != b[n - 1] and b[n - 1] != a[0]:
        now = b[n - 1]
    elif now != c[n - 1] and c[n - 1] != a[0]:
        now = c[n - 1]
    print(now)

 

B번 문제: codeforces.com/contest/1408/problem/B

 

  길이가 n인 0 이상(non-negative)의 정수로 구성된 비내림차순(non-decreasing) 배열 a가 있다. 우리는 m개의 0 이상(non-negative)의 정수로 구성된 비내림차순(non-decreasing) 배열의 집합 b를 찾는 것이다. 또한 k 값이 입력으로 주어진다. 이때 다음과 같은 조건을 만족하는 가장 작은 m을 찾으면 된다.

 

 

[ 문제 해설 ]

 

  이 문제는 테이블 형태로 그려보면 아이디어를 쉽게 찾을 수 있다. 예를 들어 n = 9, k = 4라고 하자.

 

  a = [0, 1, 2, 2, 3, 3, 3, 4, 4, 4, 4]라고 하면 다음과 같은 수열 b들을 찾을 수 있다.

 

	2	2	3	5	7	11	13	13	17
b1	2	2	3	5	7	7	7	7	7
b2	0	0	0	0	0	4	6	6	10

 

  결과적으로 m의 최솟값은 2이다. 문제 해결 아이디어는 간단하다. 먼저 배열 a에서 서로 다른 원소의 개수를 cnt라고 하자. 이때 cnt를 줄여나가는 방식을 사용한다. b1은 항상 k개만큼의 cnt를 줄일 수 있다. 이후에 b2부터 모든 배열은 (k - 1)개 만큼의 cnt를 줄일 수 있다.

 

[ 정답 코드 ]

 

import math

for _ in range(int(input())):
    n, k = map(int, input().split())

    # 서로 다른 원소 개수
    cnt = len(set(map(int, input().split())))

    if cnt > 1 and k == 1: # (k - 1)이 0이므로 만들 수 없는 경우
        print(-1)
    elif cnt <= k:
        print(1)
    else:
        print(1 + math.ceil((cnt - k) / (k - 1)))

 

C번 문제: codeforces.com/contest/1408/problem/C

 

  길이가 l인 도로가 있다. 이 도로는 좌표 0부터 l까지의 정수로 구성된다. 왼쪽 차는 0에서 시작해서 오른쪽으로 간다. 오른쪽 차는 l에서 시작해서 왼쪽으로 간다. 처음 두 자동차의 속력은 1/s이다. 그리고 n개의 깃발(flag)이 존재한다. 두 자동차는 깃발을 지날 때마다 속력이 1/s씩 증가한다.

 

  결과적으로 두 자동차가 만나는 시간을 출력하면 된다.

 

[ 문제 해설 ]

 

  예를 들어 l = 7이고, 다음과 같이 5개의 깃발이 있다고 해보자.

 

0	1	2	3	4	5	6	7
왼쪽 차	깃발(flag)	깃발(flag)	깃발(flag)	깃발(flag)		깃발(flag)	오른쪽 차

 

  아이디어는 간단하다. 총 n개의 깃발(flag)을 확인하면 된다. 다시 말해 n번을 반복하는데, 반복할 때마다 매번 ① 왼쪽 차 기준으로 다음 깃발까지의 남은 시간, ② 오른쪽 차 기준으로 다음 깃발까지의 남은 시간을 계산하자. 이때 시간이 더 짧은 쪽이 해당 깃발까지 이동하도록 만들면 된다. 그 시간 동안 상대방 차 또한 이동하도록 만들면 된다. 결과적으로 n개의 깃발을 다 처리한 뒤에, 두 자동차가 만나기 위해 걸리는 시간까지 계산해 더해주면 된다.

 

  거리 = 속도 X 시간

 

  위와 같은 공식(거속시)을 이용하여 코드를 작성하면 다음과 같다.

 

[ 정답 코드 ]

 

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    int testCase;
    cin >> testCase;
    for (int tc = 0; tc < testCase; tc++) {
        int n, l;
        cin >> n >> l;

        // n개의 깃발(flag) 정보 입력받기
        vector<int> data;
        for (int i = 0; i < n; i ++) {
            int x;
            cin >> x;
            data.push_back(x);
        }

        // 처음 A와 B의 정보 초기화
        long double aPos = 0;
        int aNext = 0;
        int aSpeed = 1;

        long double bPos = l;
        int bNext = n - 1;
        int bSpeed = 1;

        // A와 B가 만나기까지 걸리는 총 시간(time)
        long double time = 0.0;

        // n개의 깃발에 대하여 하나씩 처리
        int cnt = 0;
        while (cnt != n) {
            // A와 B의 다음 깃발까지의 거리
            long double aDistance = data[aNext] - aPos;
            long double bDistance = bPos - data[bNext];

            // A와 B의 다음 깃발까지의 시간
            long double aTime = aDistance / aSpeed;
            long double bTime = bDistance / bSpeed;

            // 더 짧은 시간이 걸리는 자동차를 기준으로 이동
            if (aTime <= bTime) {
                aPos = data[aNext];
                bPos -= aTime * bSpeed;
                aNext += 1;
                aSpeed += 1;
                time += aTime;
            }
            else {
                bPos = data[bNext];
                aPos += bTime * aSpeed;
                bNext -= 1;
                bSpeed += 1;
                time += bTime;
            }
            cnt++;
        }

        // 마지막으로 A와 B가 서로 만나도록 하기
        long double distance = bPos - aPos;
        time += distance / (aSpeed + bSpeed);

        cout.precision(15);
        cout << fixed;
        cout << time << '\n';
    }
}

 

D번 문제: codeforces.com/contest/1408/problem/D

 

[ 정답 코드 ]

 

n, m = map(int, input().split())

robbers = []
lights = []

for i in range(n):
    a, b = map(int, input().split())
    robbers.append((a, b))

for i in range(m):
    c, d = map(int, input().split())
    lights.append((c, d))

v = [0] * 1000002

for a, b in robbers:
    for c, d in lights:
        # 현재 robber보다 light의 x가 더 크거나 같다면 감시 가능
        if a <= c:
            # 그때 robber가 y 방향으로 얼마만큼 이동해야 숨을 수 있는지 계산
            v[c - a] = max(v[c - a], d - b + 1)

result = 1000001 # 1000001만큼 움직이는 것이 최악의 경우
dy_max = 0 # 가장 큰 dy 값

# 1000001부터 0까지 1씩 줄여가며, 모든 dx에 대하여
for dx in range(1000001, -1, -1):
    dy_max = max(dy_max, v[dx])
    # (dx + dy_max) 값이 가장 작은 경우를 출력
    result = min(result, dx + dy_max)

print(result)