[Codeforces Round 996(Div.2)] - D. Scarecrow

https://codeforces.com/contest/2055/problem/D

Codeforces Round 996(Div.2) - D. Scarecrow

문제 유형: 그리디, 구현, 수학

시간 제한: 2초

메모리 제한: 256MB

 

문제

A crow is sitting at position 0 of the number line. There are n scarecrows positioned at integer coordinates a1,a2,…,an along the number line. These scarecrows have been enchanted, allowing them to move left and right at a speed of 1

unit per second.

The crow is afraid of scarecrows and wants to stay at least a distance of k

ahead of the nearest scarecrow positioned at or before it. To do so, the crow uses its teleportation ability as follows:

• Let x be the current position of the crow, and let y be the largest position of a scarecrow such that y≤x. If x−y<k, meaning the scarecrow is too close, the crow will instantly teleport to position y+k.

This teleportation happens instantly and continuously. The crow will keep checking for scarecrows positioned at or to the left of him and teleport whenever one gets too close (which could happen at non-integral times). Note that besides this teleportation ability, the crow will not move on its own.

 

Your task is to determine the minimum time required to make the crow teleport to a position greater than or equal to ℓ, assuming the scarecrows move optimally to allow the crow to reach its goal. For convenience, you are asked to output twice the minimum time needed for the crow to reach the target position ℓ.

It can be proven that this value will always be an integer.

Note that the scarecrows can start, stop, or change direction at any time (possibly at non-integral times).

 

까마귀가 0번위치에 있다. n개의 허수아비가 a1, a2, ...an위치에 있다.

마법이 부여된 허수아비들이라서, 초당 1칸씩 좌 또는 우로 이동가능하다.

까마귀는 허수아비의 왼쪽으로부터 k칸이상 떨어지기를 바란다.

그래서 까마귀는 순간적으로 다음과 같이 이동한다:

까마귀의 왼쪽에서 가장 큰 위치 y를 가진 허수아비에 대해, 까마귀는 y+k로 순간이동한다.

 

이 순간이동은 계속 사용되고, 발동시간이 없다.

까마귀의 다른 이동방안은 없다.

당신은 이 허수아비들을 조작해서 l이상의 위치로 까마귀를 옮겨야 한다.

까마귀를 l 이상으로 쫓아내는 최소 시간을 구하시오.

 

입력

Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤10^4). The description of the test cases follows.

The first line of each test case contains three integers n,k,ℓ(1≤n≤2⋅10^5, 1≤k≤ℓ≤10^8) — the number of scarecrows, the teleportation distance, and the target position of the crow, respectively.

The second line of each test case contains n integers a1,a2,…,an (0≤a1≤a2≤…≤an≤ℓ) — the initial positions of the n

scarecrows.

It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5.

 

TC의 수 t가 주어진다.

각 TC의 첫 번째 줄에 n, k, l이 주어진다.

두 번째 줄에 허수아비의 위치 a1, a2, ... an <=l로 주어진다.

 

출력

For each test case, output a single integer representing the twice the minimum time required for the crow to teleport to a position greater than or equal to ℓ.

 

까마귀를 l이상으로 이동시키기 위한 최소 걸리는 시간을 구하여 출력하시오. 시간을 두 배 곱해서 출력하시오.

 

풀이

Editorial:https://codeforces.com/blog/entry/138343

우선, 가장 왼쪽의 허수아비는 0번 자리로 이동해야 한다. 그래야 까마귀가 출발을 한다.

p위치에 허수아비가 있다면, [p, p+k]구간에 까마귀가 있는 경우를 p위치의 허수아비가 까마귀를 가진다고 말하자.

까마귀를 가진 허수아비는 왼쪽으로 이동할 이유가 없다. 까마귀를 가진 이상 오른쪽으로만 이동할 뿐이다.

특정 시간 T에 허수아비가 더 오른쪽으로 이동한 경우, 최소한 더 나쁘지 않은 경우이다. 즉, 오른쪽으로 최대한 멀리 까마귀를 보내는 것이 좋다.

가장 효율적인 방법은 까마귀가 순간이동하는 거리 d를 최대로 늘리는 것이다. 즉, 허수아비들 간의 전달을 통해서 d를 최대화해야 한다.

 

T를 현재까지의 이동하는 최대 거리,

d를 까마귀가 순간이동한 총 거리,

bi를 허수아비 i가 까마귀를 받는 지점의 위치,

ai를 허수아비 i가 처음 이동을 시작하는 위치라 하자.

 

최종 시간은 a1 + l -d가 된다.

이고,

은 마지막 순간이동 후 최종 위치이다.

 

각 허수아비 위치 b_i를 결정하기 위해, 세 가지 케이스가 있다:

1. 
   허수아비 i가 이전 허수바이보다 오른쪽이라, 두 허수아비는 중간에서 만나기 위해 중간으로 이동해야 한다.
2. 
   현재 허수아비가 이전허수아비의 이동 범위에 있는 경우이다. 
   즉, 연속으로 까마귀를 이동시키도록 현재 허수아비를 이전 허수아비 +k로 오른쪽 이동해야 한다.
3. 
   현재 허수아비를 그냥 다른 허수아비들 움직이는 거리 T만큼만 오른쪽으로 밀어서 최대한 까마귀를 오른쪽으로 보내려 노력한다.

즉, 다음과 같이 나온다:

 

이를 이용해서 최종적인 순간이동 거리를 구해서 l + a[0]에 빼주면 된다.

 

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

void solve() {
  int n, k, l;
  cin >> n >> k >> l;

  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }

  double K = k;
  double L = l;

  double T = a[0];
  double last_pt = 0;
  double S = 0;

  for (int i = 1; i < n; ++i) {
    double this_pt =
        min(L, min(a[i] + T, max(last_pt + K, (a[i] - T + last_pt + K) / 2.0)));
    T += max(0.0, this_pt - last_pt - K);
    S += min(K, this_pt - last_pt);
    last_pt = this_pt;
  }

  S += min(K, L - last_pt);
  cout << (int)round(2 * (L - S + a[0])) << "\n";
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int t;
  cin >> t;
  while (t--)
    solve();

  return 0;
}