[CF 538G] Berserk Robot

這題官方解是先轉成一維的問題，我的作法是直接作，雖然本質上好像沒有差很多，不過我還得枚舉一個變數的值，感覺比官方解的麻煩多了......

作法：

一開始大概可以先想到奇偶性的問題：如果走了 $i$ 步停在 $( x , y )$ ，那麼 $i$ 和 $x + y$ 的奇偶性一定要一樣，這件事可以先在讀入條件時過濾掉顯然不可能的解。以下把每個指令都看成一個向量（$U$ 就是 $( 0 , 1 )$ ，以此類推），並且記 $S_i$ 為前 $i$ 個指令的向量和，另外記 $S_L = ( p , q )$ 。首先每個條件告訴我們的東西其實是一個等式： $k  ( p , q ) + S_i = ( x , y )$ ，其中如果輸入為 $t , x , y$ 的話，那麼上式的 $k$ 就等於 $\left \lfloor \frac{t}{L} \right \rfloor$ ，$i$ 等於 $t % L$ 。觀察這條式子可以發現，如果確定好 $( p , q )$ 的值時，就代表現在每個條件都變成了 $S_i = ( ?? , ?? )$ 的型式了，此時處理方法就會變得很簡單：把所有的 $S_i$ 按照 $i$ 值由小到大排序，如果相鄰等式的奇偶性沒有滿足的話就無解，或是相鄰兩個等式要求的 $S_i$ 座標的曼哈頓距離太大了(超過兩式的 $S$ 的下標差值)就無解，反之可以簡單的構造出一組解（先一堆 $U/D$ 再一堆 $R/L$ ，如果還有多的步數就一直加 $LR$ 之類的）。而由上面的處理方法可以反過來得到 $p , q$ 的限制條件，具體來說，首先把所有的等式都改寫成 $S_i = ( a \cdot p + b , c \cdot p + d )$ 這種樣子( 其中$a = c = -k , b = x , d = y$ )，所以可以用 $5$ 個變數$( i , a , b , c , d )$來代表一個等式(當然 $4$ 個也可以，因為 $a = c$ ，不過我覺得用 $5$ 個比較直觀)。把所有的等式按照 $i$ 由小到大排序，不過還要注意到在這之前還得加上兩個潛在的條件：$S_0 = ( 0 \cdot p + 0 , 0 \cdot q + 0 )$ ，還有 $S_L = ( 1 \cdot p + 0 , 1 \cdot q + 0 )$ 。將等式們排序後，看兩條相鄰的等式 $S_i$和 $S_j$ ，假設他們的$4$個係數分別為$a1 , b1 , c1 , d1$ 和 $a2 , b2 , c2 , d2$ ，那麼這樣就得到了一個條件：$| ( a1 - a2 ) \cdot p + ( b1 - b2 ) | + | ( c1 - c2 ) \cdot q + ( d1 - d2 ) | \leq  | j - i |$ ，更一般的可以寫成 $| a \cdot p + b | + | c \cdot q + d | \leq  e$ ，也就是現在我們獲得了很多這樣子的關於 $p$ 和 $q$ 的限制條件，要找出一組可能的 $( p , q )$ 或是輸出無解。（對了，如果相鄰兩等式的 $a$ 值一樣的話，條件就會變成 $| b | + | d | \leq  e$ ，這個可以直接判掉，所以之後可以不用考慮條件中 $a=0$ 或 $c=0$ 的情形。）

如果考慮對某一個限制條件枚舉 $p$ 的話，顯然 $p$ 要滿足 $| a \cdot p + b | \leq  e$ ，所以可以先解出 $p$ 的範圍。當確定 $p$ 的值時，所有的條件就變成 $| c \cdot q + d | \leq  f$  的型式了，於是只要再對每個條件都跑一次，把所有的 $q$ 要滿足的不等式交集起來就好了，但這樣複雜度會爆掉。不過其實可以發現，因為當 $p$ 變動 1 的時候 $a \cdot p + b$ 會變動 $a$ ，所以滿足 $| a \cdot p + b | \leq  e$ 的 $p$ 值大概不會超過 $\frac{2e}{a}$ 個（因為當 $p$ 改變那麼多時 $a \cdot p + b$ 就至少會從 $-e$ 跳到 $e$ 了），也就是我們有 $p$ 要枚舉的個數上限了，但這件事還不夠，因為如果 $e$ 很大的話複雜度還是爆掉的。但是事實上 $e$ 不會總是那麼大！觀察所有條件的 $e$ 值的由來，是由兩個相鄰等式的 $S$ 的下標相減得到的，所以就可以得到所有 $e$ 值的總和 $\leq  L$ ，所以我們只要取 $e$ 值最小的那個等式枚舉 $p$ 的值就好了。這樣的話假設共有 $x$ 條等式，那麼 $e$ 的最小值 $\leq  L / x$ ，所以這樣子的複雜度就會是 $O( x ) \cdot O( L / x ) = O( L )$ ！就成功解決了這個問題了。類似的梗也出現在 CF 526-E Transmitting Levels。

但這樣傳上去之後爛掉了OAO，後來我發現是因為忘記判斷相鄰兩個等式之間的奇偶條件了......也就是當我們得到一條 $| ( a1 - a2 ) \cdot p + ( b1 - b2 ) | + | ( c1 - c2 ) \cdot q + ( d1 - d2 ) | \leq  | j - i |$ 這樣的條件時，奇偶性的條件其實就會等價於「左式和右式的奇偶性一樣」。我的解決方法是：因為當在枚舉 $p$ 時會再把所有條件跑過一遍，那麼只要在那時候多回傳「 $q$ 是否可以是奇數」和「 $q$ 是否可以是偶數」這兩件事就好了。另外一個小細節是，我們會需要解形如 $a \leq  k \cdot x \leq  b$ 的等式，其中 $a , b , k$ 給定，這要把 $a$ 和 $b$ 的正負分開處理才可以，因為「 / 」這個運算子是往 $0$ 的方向捨去的。

code :

#include<bits/stdc++.h>
#define LL long long
#define ABS(x) ((x)>0 ? (x) : (-(x)))
#define INF (1LL<<60)
using namespace std;
const int maxn=200000+10 ;
 
struct pll{LL x,y;};
pll cal(LL k,LL a,LL b) /// a <= kx <= b  -->  ? <= x <= ? , k>0
{
    pll p ;
    p.x = (a>0  ? (a-1)/k+1 : a/k) ;
    p.y = (b>=0 ? b/k : (b+1)/k-1) ;
    return p ;
}
 
struct P
{
    int id ; LL a,b,c,d ;
    bool operator < (const P &rhs) const
    {
        return id<rhs.id ;
    }
}p[maxn];
 
struct cond{LL a,b,c,d,e;}con[maxn] ;
int ccnt ;
pll get_interval(LL x,int &pa) /// parity , 1 : odd ok , 2 : even ok
{
    pll ret=(pll){-INF,INF} ;
    pa=3 ;
    for(int i=0;i<ccnt;i++)
    {
        if(con[i].a%2)
        {
            int z=((con[i].e-x-con[i].d-con[i].b)%2+2)%2 ;
            if(z==0 && (pa&1)) pa^=1 ;
            if(z==1 && (pa&2)) pa^=2 ;
        }
        LL val=con[i].e-ABS(x*con[i].a+con[i].b) ;
        pll tmp=cal(con[i].c,-val-con[i].d,val-con[i].d) ;
        ret.x=max(ret.x,tmp.x) ;
        ret.y=min(ret.y,tmp.y) ;
    }
    return ret ;
}
 
int n,L ;
void found_ans(LL x,LL y)
{
    for(int i=0;i<n+1;i++)
    {
        if(p[i].id==p[i+1].id) continue ;
        LL x1=x*p[i].a+p[i].b , y1=y*p[i].c+p[i].d ;
        LL x2=x*p[i+1].a+p[i+1].b , y2=y*p[i+1].c+p[i+1].d ;
        LL dx=x2-x1 , dy=y2-y1 , dis=p[i+1].id-p[i].id ;
        dis-=ABS(dx)+ABS(dy) ;
        while(dx<0) putchar('L') , dx++ ;
        while(dx>0) putchar('R') , dx-- ;
        while(dy<0) putchar('D') , dy++ ;
        while(dy>0) putchar('U') , dy-- ;
        while(dis) putchar('L') , putchar('R') , dis-=2 ;
    }
}
 
main()
{
    scanf("%d%d",&n,&L) ;
    for(int i=1;i<=n;i++)
    {
        LL t,x,y ; scanf("%I64d%I64d%I64d",&t,&x,&y) ;
        if((t+x+y)%2){printf("NO\n") ; return 0 ;}
        LL u=t/L ; int v=t%L ;
        p[i]=(P){v,-u,x,-u,y} ;
    }
    p[0]=(P){0,0,0,0,0} ;
    p[n+1]=(P){L,1,0,1,0} ;
    sort(p,p+n+2) ;
    for(int i=0;i<n+1;i++)
    {
        LL a=p[i].a-p[i+1].a , b=p[i].b-p[i+1].b ;
        LL c=p[i].c-p[i+1].c , d=p[i].d-p[i+1].d ;
        if(!a)
        {
            if(ABS(b)+ABS(d)>p[i+1].id-p[i].id)
                {printf("NO\n") ; return 0 ;}
            continue ;
        }
        if(a<0) a=-a , b=-b , c=-c , d=-d ;
        con[ccnt++]=(cond){a,b,c,d,p[i+1].id-p[i].id} ;
    }
 
    int mi=L+1 , mid ;
    for(int i=0;i<ccnt;i++) if(con[i].e<mi)
        mi=con[mid=i].e ;
    pll tmp=cal(con[mid].a,-con[mid].e-con[mid].b,con[mid].e-con[mid].b) ;
 
    for(LL i=tmp.x;i<=tmp.y;i++)
    {
        int pa ;
        pll tmp2=get_interval(i,pa) ;
        if((tmp2.x%2) && !(pa&1)) tmp2.x++ ;
        if((tmp2.x%2==0) && !(pa&2)) tmp2.x++ ;
        if(tmp2.y>=tmp2.x && pa){found_ans(i,tmp2.x) ; return 0 ;}
    }
    printf("NO\n") ;
}