[Codeforces 1073C] Vasya and Robot

[Codeforces 1073C] Vasya and Robot - 1800

문제 설명 : 

상하좌우(U,D,L,R)로 움직일 수 있는 로봇이 있다. 이 로봇은 처음에 (0,0)부터 출발하여 목표지점 (x,y)까지 이동하고자 한다. 로봇이 어떻게 움직일지는 입력에서 (U,D,L,R)로 이루어진 문자열로 주어진다. 이 문자열대로 움직였을 때 목표지점에 도착하지 못할 수도 있다. 그래서 그 문자열의 이동 명령을 0번 이상 임의로 변경할 수가 있다. 여기서 목표 지점까지 도달하기 위해서 문자열을 변경할 때, 가장 처음 변경된 인덱스와 가장 끝에 변경된 인덱스의 거리차이를 최소화하는 문제이다.

풀이 : 

일단 어떻게 변경하더라도 절대로 불가능한 경우가 있다. abs(x) + abs(y) 가 문자열의 길이(n)보다 크다면 절대로 불가능하고, 또 문자열대로 이동하였을 때의 최종 좌표의 절댓값의 합은 abs(x) + abs(y)와 짝, 홀수 여부가 일치해야 한다. 이 두 경우를 통과한다면 반드시 가능하다는 것은 확실하다. 여기서부터 최소 길이를 구하는 방법은 이분탐색을 이용하는 것이다. 이분탐색 각 시행마다 최대 문자열의 길이를 윈도우로 정해놓고 윈도우에 포함된 문자열은 임의로 변경할 수 있는 문자열, 윈도우 밖은 변경하지 않을 문자열로 가정한다. 이렇게 두면 윈도우 밖 이동명령의 결과와 윈도우 내부의 문자열을 취합하여 목표지점까지 도달할 수 있는지를 판단하면 된다. 그런데 윈도우 내부는 아무렇게나 구성할 수 있기 때문에 (아래 코드 93줄처럼) 절대값의 합이 현재 윈도우의 사이즈와 크기를 비교해주기만 하면 된다. 이렇게 해서 lower_bound를 구하면 된다. 윈도우 외부 이동명령의 결과는 x좌표, y좌표를 따로 부분합 배열을 사용하면 O(1)만에 구할 수 있다.

주의할 점 : 

-

배운 점 : 

이분탐색으로 푼다는 아이디어가 기발했다. 인덱스 간의 거리차이를 미리 윈도우 사이즈로 정해놓고 그 내부에서는 이동명령을 아무렇게나 구성할 수 있고, 모든 string을 순회하면서 가능한 케이스가 하나라도 있으면 윈도우 사이즈를 줄여나간다.

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<assert.h>
#include<stdlib.h>
#include<stack>
using namespace std;
/*********************Contest Template***********************/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,int> Cord;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(0);
struct S{
    int a,b;
 
    S(){}
    S(int _a,int _b){
        a=_a;
        b=_b;
    }
 
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int,vector<int>,greater<int>> mpq;
#define SPACE 0
#define NL 1
inline void showAll(vector<int> &v,int NL_or_space){ 
    //0 is space, 1 is NL
    for(int &here:v){
        printf("%d",here);
        printf("%c",(NL_or_space)?'\n':' ');
    }
}
/*********************Contest Template***********************/
const int SIZE= 200009;
 
char str[SIZE];
int psum_x[SIZE],psum_y[SIZE];
 
int main(){
    int n;    scanf("%d",&n);
    scanf("%s",str+1);
    int x,y;    scanf("%d %d",&x,&y);
 
    for(int i=1 ; str[i] ; i++){
        if(str[i]=='R') {
            psum_x[i]=psum_x[i-1]+1;
            psum_y[i]=psum_y[i-1];
        }
        else if(str[i]=='L') {
            psum_x[i]=psum_x[i-1]-1;
            psum_y[i]=psum_y[i-1];
        }
        else if(str[i]=='U'){
            psum_y[i]=psum_y[i-1]+1;
            psum_x[i]=psum_x[i-1];
        }
        else{
            psum_y[i]=psum_y[i-1]-1;
            psum_x[i]=psum_x[i-1];
        }
    }
 
    int ans=0;
    int sumxy=abs(x)+abs(y);
 
    if(sumxy>n || sumxy%2 != n%2 ){
        printf("-1\n");
        return 0;
    }
 
    int l=-1,r=n+1;
    while(l+1<r){
        int mid=(l+r)/2;
 
        for(int i=1 ; i+mid<=n+1 ; i++){
            int xx=0,yy=0;
            xx+=psum_x[i-1],yy+=psum_y[i-1];
            xx+=psum_x[n]-psum_x[i+mid-1],yy+=psum_y[n]-psum_y[i+mid-1];
 
            if(abs(x-xx)+abs(y-yy)<=mid){
                r=mid;
                break;
            }
        }
        if(r!=mid) l=mid;
    }
 
    printf("%d\n",r);
 
    return 0;
}