ARC 103 D - Robot Arms

個人的に学ぶことが多かったのでメモメモ。

学んだこと

• 観察力の足りなさ
• 小さい例でもっと考える
• ちょっとずつ
• マンハッタン距離と45度回転

マンハッタン距離と45度回転

ちょっとここは数学的っぽいのでメモ。
マンハッタン距離を考える。
2次元の場合、

で定義される。例えば、原点から(1,2)までのマンハッタン距離は 3 とかね。

次に、適当にを考えるじゃん。
これから上下左右それぞれdだけ動いた点Bを考える。
上 :
下 :
右 :
左 :
こんな感じになる。

そして、45度回転させた座標系(u,v)を考える。つまり、(u, v) = (x+y, x-y) というような感じ。
正確には、を除いているわけだけど。

これが、ここで、u, v 上では、点Aは

になってるわけだ。
じゃあ、点Bは？

上 :
下 :
右 :
左 :

こんな感じになってるわけ。

ここで、


とすると、
点Bの u座標は , v座標はといったように、u と v を分離することができたわけだ。これを用いるとそれぞれの座標u,vでdの足し引きだけで、次の点にいけるみたいだ。

これを用いたのが、解答

解答

def solve(xy):
    p = False
    if all([(x+y)%2==0 for x,y in xy]):
        p = True
    elif all([(x+y)%2==1 for x,y in xy]):
        pass
    else:
        print(-1)
        return
    m = [2**i for i  in range(30,-1,-1)]
    if p:
        m.append(1)
    anses = []
    for x,y in xy:
        usum, vsum = (0, 0)
        ans = []
        u = x+y
        v = x-y
        anses.append(ans)
        for d in m:
            if usum <= u:
                usum += d
                if vsum <= v:
                    vsum += d
                    ans.append('R')
                else:
                    vsum -= d
                    ans.append('U')
            else:
                usum -= d
                if vsum <= v:
                    vsum += d
                    ans.append('D')
                else:
                    vsum -= d
                    ans.append('L')
    print(len(m))
    print(" ".join([str(i) for i in m]))
    for a in anses:
        print("".join(a))


def main():
    n = int(input())
    xy = []
    for i in range(n):
        xy.append([int(i) for i in input().split()])
    solve(xy)

if __name__ == '__main__':
    main()

ということになる。

参考

最近の 45 度回転事情 - Lilliput Steps
AtCoder ARC 103 D - Robot Arms (600 点) - けんちょんの競プロ精進記録

めちゃめちゃわかりやすかったです。