D - Robot Arms AtCoder Regular Contest 103

D: Robot Arms - AtCoder Regular Contest 103 | AtCoder

問題概略
m個の腕があるロボットアームがあり、これらは一つ前の関節からUDLRの方向に曲げることが出来る。
今N個の座標が与えられる。アームの先端がN個全部を指せるような腕の長さと方向の組み合わせがあれば出力せよ。

制約
1 <= N <= 1000

• 10^9 <= x,y<=10^9

解法
うまく数を足し引きして与えられた数を作る問題。
このように使える個数が少ない場合、とりあえず2の冪乗で考えたい。
腕の順番は関係ないので、わかりやすさのために1,2,4,8と持つことにする。
どの様な範囲を指せるのか紙に書いてみると、x,yの合計が奇数の点の市松模様状に取れることがわかる。
ここで、穴抜けがあるが、取れる座標は数のたし引きによるものなので、させる(x,y)のマンハッタン距離とロボットアームの長さのパリティは一致している必要があるため、大丈夫。
合計が偶数の場所を取る問題の時は、1を追加すればいい。

ゴールが分かれば、4方向で1番原点に近い点を貪欲に選んでいけば復元できる。

類題
D - All Your Paths are Different Lengths

 public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        N = ni();
        int[] x = niah(N, 2);
        int[] y = niah(N, 2);
        for (int i = 0; i < N; i++) {
            if (mod(x[i] + y[i], 2) != mod(x[0] + y[0], 2)) {
                System.out.println("-1");
                return;
            }
        }
        ArrayList<Long> len = new ArrayList<>();
        for (int i = 38; i >= 0; i--) {
            len.add((long) pow(2, i));
        }
        if ((x[0] + y[0]) % 2 == 0) len.add(1L);
        System.out.println(len.size());
        for (int i = len.size() - 1; i >= 0; i--) {
            System.out.print(len.get(i) + " ");
        }
        System.out.println("");
        //ゴールから見て右に行きたい時、スタートから見て左へ動く必要がある
        //問題と違い、上がマイナス、下がプラスとして扱っているため、逆の逆でUDはそのまま
        char[] d = {'U', 'D', 'R', 'L'};
        for (int i = 0; i < N; i++) {
            long nx = x[i];
            long ny = y[i];
            for (Long v : len) {
                long minDis = Long.MAX_VALUE;
                int dir = 0;
                for (int j = 0; j < 4; j++) {
                    long tx = nx + x4[j] * v;
                    long ty = ny + y4[j] * v;
                    if (minDis > abs(tx) + abs(ty)) {
                        minDis = abs(tx) + abs(ty);
                        dir = j;
                    }
                }
                nx = nx + x4[dir] * v;
                ny = ny + y4[dir] * v;
                sb.append(d[dir]);
            }
            System.out.println(sb.reverse());
            sb.setLength(0);
        }
    }