ARC103/ABC111 D Robot Arms

これ
D - Robot Arms
を解いた。
解説はこれ
https://img.atcoder.jp/arc103/editorial.pdf。
参考にしたのはこれ
AtCoder ARC 103 D - Robot Arms (600 点) - けんちょんの競プロ精進記録。

という長さのアームがあれば、各格子点のx座標とy座標の和が奇数であり、以下の部分に色がついた、市松模様ができる。
いくつか実験すると、成り立つことが分かる。
あとは、マンハッタンマンハッタンした感じにすると、x軸とy軸を独立に処理できるので、なんとかなる。

というわけで、pythonでの実装はこれ。

def solution(x,y):
    ans = ''
    nowx, nowy = 0,0
    preX = [0]*31
    preY = [0]*31
    for i in range(31):
        if nowx < x:
            nowx += 2**(30-i)
            preX[i] = 1
        else:
            nowx -= 2**(30-i)
            preX[i] = -1
        if nowy < y:
            nowy += 2**(30-i)
            preY[i] = 1
        else:
            nowy -= 2**(30-i)
            preY[i] = -1
    for i in range(31):
        if preX[i] == -1 and preY[i] == -1:
            ans += 'L'
        elif preX[i] == 1 and preY[i] == 1:
            ans += 'R'
        elif preX[i] == -1 and preY[i] == 1:
            ans += 'D'
        else:
            ans += 'U'
    return ans
N = int( input())
X = [0]*N
Y = [0]*N
x, y = map( int, input().split())
X[0] = x
Y[0] = y
evod = (x+y)%2
Flag = True
for i in range(1,N):
    x, y = map( int, input().split())
    X[i] = x
    Y[i] = y
    if (x+y)%2 != evod:
        Flag = False

if Flag:
    D = [2**i for i in range(30,-1,-1)]
    if evod == 1:
        print(31)
        print(' '.join(map(str,D)))
        for i in range(N):
            print( solution(X[i]+Y[i],X[i]-Y[i]))
    else:
        print(32)
        D.append(1)
        print(' '.join(map(str,D)))
        for i in range(N):
            print( solution(X[i]+Y[i]-1,X[i]-1-Y[i]) + 'R')
else:
    print(-1)