#659(Div.2) B. Koa and the Beach(Easy Version DP & Hard Version 욕심)

제목 설명
The only difference between easy and hard versions is on constraints. In this version constraints are higher. You can make hacks only if all versions of the problem are solved. Koa the Koala is at the beach! The beach consists (from left to right) of a shore, n+1 meters of sea and an island at n+1 meters from the shore. She measured the depth of the sea at 1,2,…,n meters from the shore and saved them in array d. di denotes the depth of the sea at i meters from the shore for 1≤i≤n. Like any beach this one has tide, the intensity of the tide is measured by parameter k and affects all depths from the beginning at time t=0 in the following way: For a total of k seconds, each second, tide increases all depths by 1. Then, for a total of k seconds, each second, tide decreases all depths by 1. This process repeats again and again (ie. depths increase for k seconds then decrease for k seconds and so on …). Formally, let’s define 0-indexed array p=[0,1,2,…,k−2,k−1,k,k−1,k−2,…,2,1] of length 2k. At time t (0≤t) depth at i meters from the shore equals di+p[tmod2k] (tmod2k denotes the remainder of the division of t by 2k). Note that the changes occur instantaneously after each second, see the notes for better understanding. At time t=0 Koa is standing at the shore and wants to get to the island. Suppose that at some time t (0≤t) she is at x (0≤x≤n) meters from the shore: In one second Koa can swim 1 meter further from the shore (x changes to x+1) or not swim at all (x stays the same), in both cases t changes to t+1. As Koa is a bad swimmer, the depth of the sea at the point where she is can’t exceed l at integer points of time (or she will drown). More formally, if Koa is at x (1≤x≤n) meters from the shore at the moment t (for some integer t≥0), the depth of the sea at this point — dx+p[tmod2k] — can’t exceed l. In other words, dx+p[tmod2k]≤l must hold always. Once Koa reaches the island at n+1 meters from the shore, she stops and can rest. Note that while Koa swims tide doesn’t have effect on her (ie. she can’t drown while swimming). Note that Koa can choose to stay on the shore for as long as she needs and neither the shore or the island are affected by the tide (they are solid ground and she won’t drown there). Koa wants to know whether she can go from the shore to the island. Help her!
Input
The first line of the input contains one integer t (1≤t≤104) — the number of test cases. Description of the test cases follows. The first line of each test case contains three integers n, k and l (1≤n≤3⋅105;1≤k≤109;1≤l≤109) — the number of meters of sea Koa measured and parameters k and l. The second line of each test case contains n integers d1,d2,…,dn (0≤di≤109) — the depths of each meter of sea Koa measured. It is guaranteed that the sum of n over all test cases does not exceed 3⋅105.
Output
For each test case: Print Yes if Koa can get from the shore to the island, and No otherwise. You may print each letter in any case (upper or lower).
Example
input 7 2 1 1 1 0 5 2 3 1 2 3 2 2 4 3 4 0 2 4 3 2 3 5 3 0 7 2 3 3 0 2 1 3 0 1 7 1 4 4 4 3 0 2 4 2 5 2 3 1 2 3 2 2 output Yes No Yes Yes Yes No No
Note
In the following s denotes the shore, i denotes the island, x denotes distance from Koa to the shore, the underline denotes the position of Koa, and values in the array below denote current depths, affected by tide, at 1,2,…,n meters from the shore. In test case 1 we have n=2,k=1,l=1,p=[0,1]. Koa wants to go from shore (at x=0) to the island (at x=3). Let’s describe a possible solution: Initially at t=0 the beach looks like this: [s–,1,0,i]. At t=0 if Koa would decide to swim to x=1, beach would look like: [s,2–,1,i] at t=1, since 2>1 she would drown. So Koa waits 1 second instead and beach looks like [s–,2,1,i] at t=1. At t=1 Koa swims to x=1, beach looks like [s,1–,0,i] at t=2. Koa doesn’t drown because 1≤1. At t=2 Koa swims to x=2, beach looks like [s,2,1–,i] at t=3. Koa doesn’t drown because 1≤1. At t=3 Koa swims to x=3, beach looks like [s,1,0,i–] at t=4. At t=4 Koa is at x=3 and she made it! We can show that in test case 2 Koa can’t get to the island.
제목의 대의.
n개의 해역이 있고 각 해역은 초기 깊이가 있다. 2*k초, 전 k초 초당 깊이+1, 후 k초 초당 깊이-1이다.한 사람이 해안 한쪽에서 다른 한쪽으로 헤엄쳐 가려고 하는데, 1초에 다음 해역으로 이동하거나 현재 해역에 머물 수 있다. 만약 현재 해역의 깊이가 l보다 크면 그는 물에 빠져 죽을 것이다. 그에게 맞은편 기슭까지 헤엄쳐 갈 수 있느냐고 물었다.
Easy Version
제목 분석
이 문제는 dp를 통해 풀 수 있다.상태 표시: f[i][j] // i j 상태 계산: f[i][j] f[i][j-1] // i f[i-1][j-1] // i-1 둘 중 하나의 상태가 합법적이라면 f[i][j]는 도착할 수 있다.그리고 우리는 f[i][j]상태 자체가 합법적인지, 즉 j초에 해역 i의 깊이가 l보다 큰지 증명해야 한다.마지막으로 우리는 f[n][j]의 상태에 합법적인 것이 있는지 찾아보면 된다. 만약에 f[n][j]의 상태에 합법적인 것이 있다면 최종 결과는 Yes이다.
코드는 다음과 같다.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LL long long
#define PII pair
using namespace std;
const int N=1e2+5,M=2e4+5;
int a[N],p[2*N];
int f[N][M];
void init(int k)
{
	for(int i=0;i<=k;i++) p[i]=i;		//         
	for(int i=1;i<k;i++) p[k+i]=k-i;
	
	for(int i=0;i<2*k;i++) f[0][i]=1;	//    ，        [0,2k]   
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		memset(f,0,sizeof f);
		int n,k,l;
		cin>>n>>k>>l;
		for(int i=1;i<=n;i++)
			cin>>a[i];
		
		init(k);
		for(int i=1;i<=n;i++)			//    
		for(int j=0;j<2*k*n;j++)		//    
		{
			f[i][j]=max(f[i][j-1],f[i-1][j-1]);		//    f[i][j]     
			if(l<p[j%(2*k)]+a[i]) f[i][j]=0;		//  f[i][j]      
		}
		bool ok=false;
		for(int i=0;i<2*k*n;i++)
			if(f[n][i]) ok=true;
		
		if(ok) puts("Yes");
		else puts("No");
	}
	return 0;
}

Hard Version
제목 분석
우선 각 해역의 a[i]가 어느 시간대에 [li,ri] 안에 통과할 수 있는지(즉:a[i]+p[t]<=l,li<=t<=ri)를 요구합니다.그러나 만조의 주기는 ∧형(0-k-0)이다. 그러면 [li,ri] 구간은 분리되어 계산하기 어렵다.따라서 우리는 먼저 만조의 주기를 새롭게 정의하여 V형(k-0-k, 용수를 고려하지 않기 때문에 k초를 뒤로 미루어도 상관없다)으로 바꿀 수 있다.이렇게 하면 [li,ri]는 하나의 연속적인 구간이어서 계산하기 편리하다.li l（a[i]+k-l），ri li ， ri=2*k-li。 그리고 우리는 리시각으로 들어가는 것을 선택하면 된다.1-n의 바다에서 만약에 어떤 해역이 a[i]+k<=l이면 안전한 해역이다. 그러면 우리는 이 해역에 얼마나 머물러도 괜찮다. 이때 우리는 시간을 조정할 수 있다. 다음 해역이 li에 도착하면 계속 앞으로 나아가면 된다.만약 어떤 해역이 안전해역이 아니라면 머무르지 마라. 왜냐하면 비안전해역에서 시간이 지날수록 (만조) 나는 물에 빠져 죽을 수 있기 때문이다.만약에 어떤 해역에 도착했을 때 a[i-1]의 시간이 t, t+1>ri라면 우리는 다음 해역에서 물에 빠져 죽을 것이기 때문에 헤엄쳐 갈 수 없다(No).그렇지 않으면 다음 해역으로 순조롭게 진입, t+1.마지막으로 n에 도달할 수 있는 위치는 Yes입니다.
코드는 다음과 같다.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LL long long
#define PII pair
using namespace std;
const int N=3e5+5;
int a[N]; 
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n,k,l;
		scanf("%d %d %d",&n,&k,&l);
		int maxv=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
			maxv=max(maxv,a[i]);
		}
		if(maxv>l) 
		{
			puts("No"); continue;
		}
		else if(maxv+k<=l)
		{
			puts("Yes"); continue;
		}
		int t=-1;
		bool st=0;
		for(int i=1;i<=n;i++)
		{
			int li=max(0,k+a[i]-l),ri=2*k-li;	//  li ri，li       0
			if(a[i]+k<=l)		//       
			{
				st=true;
				continue;
			}
			if(st)				//           ，        li     
			{
				t=li;
				st=false;
				continue;
			}
			if(ri>=t+1) t=max(li,t+1);	//   ri       
			else {t=-1; break;}			//    
		}
		if(t<0) puts("No");
		else puts("Yes"); 
	}
	return 0;
}