Educational Codeforces Round 103 (Rated for Div. 2) D. Journey

콘테스트에서 못풀었던 문제입니다.
다시 풀어봤는데 이걸 어떻게 해결할 수 있을지 생각해내지 못했습니다.
에디토리얼을 보고 이해했습니다.

rating : 1700
tags : dfs and similar , dp , dsu , implementation

문제

0~n까지의 n+1개의 도시가 있습니다. 각 i번째 도시는 i+1번째 도시와 도로로 연결되어있습니다. (i:0~n-1)
도로는 방향이 있습니다. 현재 도시에서 왼쪽 또는 오른쪽 둘 중 한 방향으로 갈 수 있습니다. 어떤 도시에서 여행자가 여행을 출발합니다. 여행자의 이동 방향과 도로의 방향이 같아야 그 도로를 이용해 다른 도시로 이동할 수 있습니다. 여행자는 매번 이동을 해야만 합니다. 이동할 수 없으면 여행은 종료됩니다. 그런데 한 번 이동할 때 마다 모든 도로는 방향이 반대로 바뀝니다. 구하는 값은 여행자가 각 도시를 출발점으로 여행을 출발할 때, 최대 몇개의 도시들을 방문할 수 있는지 구하는 것 입니다.

어려움

1. 설계
   일단 모든 도로가 방향이 바뀐다, 모든 도시에서 최대 방문 도시를 구하라... 등 복잡했습니다. 이러한 조건들로 생기는 특성을 파악하지 못했습니다.

2. 구현
   약간의 힌트를 보고 LRLR... RLRL... 이런 패턴이 답에 결정적인 영향을 미친다는 사실은 파악했습니다. 그런데 이런 패턴을 어떻게 처리할지 떠올리지 못했습니다..

해결

LRLR... RLRL... 이런 패턴이 답에 결정적인 영향을 미칩니다.

*R (현재 도시)
LL (현재 도시)
RL (현재 도시)

현재 도시의 가장 가까운 왼쪽 도로 2개의 경우의 수는 위 3가지입니다.
일단 바로 왼쪽이 R이면 전혀 이동하지 못합니다.
바로 왼쪽이 L이면 일단 갈 수 있습니다.
왼쪽왼쪽이 L이면 도로의 방향이 바뀌기 때문에 못가고
R이면 갈 수 있습니다.

그리고 dp 테이블에 기록해두면서 연산량을 줄일 수 있습니다.
이런 식으로 각 도시에서 왼쪽으로 최대 도달 도시를 구할 수 있습니다.
오른쪽 방향도 마찬가지로 최대 도달 도시를 구할 수 있습니다.
이 범위가 답이 됩니다.

피드백

1. 설계
   몇 가지 경우의 수라도 종이에 써봤으면 패턴이 보였을지도 모르겠습니다. 막막해서 시도조차 하지 않았습니다..
   특징이 안 보이면 특징을 관찰하려는 시도를 해야합니다.
   "도달 가능 범위"란 개념은 떠올리지도 못했습니다.
2. 구현
   꽤 새로운 dp였습니다. 점프하는 dp를 좀 어렵다고 생각했었는데 그런 dp 유형을 응용한 dp 문제였습니다.
   (그래프 풀이도 있는데 이해하지 못했습니다.)

const int MAX=3e5+10;
int n;
string s;
int Left[MAX],Right[MAX];

int main(){
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	
	//After the traveler moves to a neighboring city, all roads change their directions to the opposite ones. 
	
	int tc; cin>>tc;
	while(tc--){
		cin>>n;
		cin>>s;
		
		memset(Left,0,sizeof(int)*(n+2));
		memset(Right,0,sizeof(int)*(n+2));
		
		//left reachability
		Left[0]=0;
		for(int i=0;i<n;i++){
			if(s[i]=='R'){
				Left[i+1]=i+1;
				continue;
			}
			
			//s[i]!='R' here
			if(i==0 || s[i-1]=='L'){
				Left[i+1]=i;
				continue;
			}
			
			//s[i-1]='R', s[i]='L' here
			Left[i+1]=Left[i-1];
			
		}
		//for(int i=0;i<=n;i++) cout<<Left[i]<<" "; cout<<"\n";
		
		
		//right reachability
		Right[n]=n;
		for(int i=n-1;i>=0;i--){
			if(s[i]=='L'){
				Right[i]=i;
				continue;
			}
			
			//s[i]='R' here
			if(i==n-1 || s[i+1]=='R'){
				Right[i]=i+1;
				continue;
			}
			
			Right[i]=Right[i+2];
		}
//		for(int i=0;i<=n;i++) cout<<Left[i]<<" "; cout<<"\n";
//		for(int i=0;i<=n;i++) cout<<Right[i]<<" "; cout<<"\n";
		for(int i=0;i<=n;i++) cout<<Right[i]-Left[i]+1<<" "; cout<<"\n";
	}	

}