ABC 111 D Robot Arms
おもしろい問題。与えられた一連の$ (X_i, Y_i)に対して、適当な数列$ { d_1, \ldots, d_m }を考案する。そして、$ X_i = - d_2 + d_3 - d_6 \ldotsおよび$ Y_i = -d_1 - d_4 - d_5 + \ldotsのように、それぞれの要素を$ X_iと$ Y_iに分配して$ 1か$ -1をかけて合計したものが$ X_iと$ Y_iに一致する、そんな$ {d_j}とそれぞれの$ (X_i, Y_i)への分配のしかたを求めたい。
ぱっと思いつくのは$ 1を適当に並べれば、任意の$ (X, Y)を表せそうという考え。また$ X + Yの偶奇は常に$ d_jの総和の偶奇と一致することにも気付く。つまり$ 1を無限個並べたとしても与えられた$ (X_i, Y_i)のすべての$ X_i + Y_iの偶奇が一致していないと、そもそも表せない。逆に偶奇が一致していれば表せる。
ここまでで部分点の$ -10 \le X \le 10, -10 \le Y \le 10は解ける。
さて、本題の$ -10^9 \le X \le 10^9, -10^9 \le Y \le 10^9にとりかかる。まず一次元の問題で考える。すなわち、偶奇の一致する$ N個の$ X_iが与えられ、何らかの数列$ d_jがすべての$ X_iに対して$ X_i = \sum_{j=1}^m a_{ij} d_j（ただし $ a_{ij} = -1もしくは $ 1）を満たすようにしたい。
このとき2進数が使えそうに見える。実際、$ a_{ij}が$ 1となるような$ jだけを拾って集合$ S_iとすれば、$ X_i = -\sum_{j=1}^m d_j + 2\sum_{j \in S_i} d_jと変形することができ、$ d_j = 2^{j - 1}とすれば$ \sum_{j \in S_i} d_jは任意の整数を表せるので、$ -2^m + 1 \le X \le 2^m - 1の任意の奇数を表すことができる（$ \sum_{j=1}^m 2^{j-1} = 2^m - 1は奇数）。言いかえると$ mを十分大きくすれば与えられた$ X_iに対して$ \dfrac{1}{2} (X_i + 2^m - 1)を2進表記してビットが$ 1のものだけ拾えば目当ての$ S_iを構築できる。$ X_iが偶数の場合は$ d_{m+1} = 1を常に足せばよい。
実際にコードにするとこんな感じだろうか。
code:java
final Scanner scanner = new Scanner(System.in);
final int m = 30;
final int X = scanner.nextInt();
final int r = 1 - Math.abs(X) % 2;
if (r > 0) {
System.out.println(m + 1);
System.out.print("1 ");
} else {
System.out.println(m);
}
for (int i = 0; i < m; i++) System.out.print((1 << i) + " ");
System.out.println();
final StringBuilder sb = new StringBuilder();
if (r > 0) sb.append('R');
int a = (X - r + (1 << m) - 1) / 2;
for (int i = 0; i < m; i++) {
sb.append(a % 2 == 1 ? 'R' : 'L');
a /= 2;
}
System.out.println(sb.toString());
さて、それでは2次元にどう適用するか考えよう。$ X_iに振り分けられて係数が$ 1の$ d_jの集合を$ R_i、$ -1の集合を$ L_i、$ Y_iに振り分けられて係数が$ 1の集合を$ U_i、$ -1の集合を$ D_iとすると、$ X_i + Y_i = \sum_{d_j \in R_i} d_j - \sum_{d_j \in L_i} d_j + \sum_{d_j \in U_i} d_j - \sum_{d_j \in D_i} d_j = \sum_j a_{ij}d_jとなり、先程の1次元の場合と形が一緒になる。しかし、これだと$ d_jの係数$ a_{ij}が分かっても、そこから$ R_iや$ U_iは導けない。ここで$ X_i - Y_iを考えると実は同じ1次元と同じ形$ X_i - Y_i = \sum_{d_j \in R_i} d_j - \sum_{d_j \in L_i} d_j - \sum_{d_j \in U_i} d_j + \sum_{d_j \in D_i} d_j = \sum_j a'_{ij}d_jになることが分かる。そして$ d_jがどの集合に属するかによって$ a_{ij}と$ a'_{ij}が以下のようになることが分かる：
$ d_jが集合$ R_iに属するとき：$ a_{ij} = \phantom{-}1, \quad a'_{ij} = \phantom{-}1
$ d_jが集合$ L_iに属するとき：$ a_{ij} = -1, \quad a'_{ij} = -1
$ d_jが集合$ U_iに属するとき：$ a_{ij} = \phantom{-}1, \quad a'_{ij} = -1
$ d_jが集合$ D_iに属するとき：$ a_{ij} = -1, \quad a'_{ij} = \phantom{-}1
逆に$ a_{ij}と$ a'_{ij}が求まれば、そこからどの集合に属するか判定できる。
以上からつぎのような流れで解けばよいことがわかる。
1. $ X_i + Y_iの偶奇をしらべ、すべて一致することを確認する
2. 奇数だった場合はそのまま、偶数だった場合は向きが$ Rで長さが$ 1の腕を加え、以降では座標を1ずらす
3. 腕の本数は$ 31本とし、長さは$ d_i = 2^0, 2^1, \ldots, 2^{30}とする
4. 各$ iについて$ U_i = X_i + Y_iと$ V_i = X_i - Y_iを計算し、$ \dfrac{1}{2} (U_i + 2^{31} - 1)と$ \dfrac{1}{2} (V_i + 2^{31} - 1)の2進数を求める
5. それぞれの2進数の$ jビット目の値が$ a_j、$ a'_jを調べ、$ 0, 0なら$ L、$ 0, 1なら$ D、$ 1, 0なら$ U、$ 1, 1なら$ Rを印字するという操作を$ j = 1から$ 31まで行う
なお$ X + Y \le 2 \cdot 10^{19} \lt 2^{31} - 1から$ m = 31であれば十分であることがわかる。
code:java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
for (int i = 0; i < N; i++) {
int x = scanner.nextInt();
int y = scanner.nextInt();
}
int r = Math.abs(u0 % 2); for (int i = 1; i < N; i++) {
if (Math.abs(ui % 2) != r) { System.out.println("-1");
return;
}
}
r = 1 - r;
int m = 31;
System.out.println(m + r);
StringBuilder sb = new StringBuilder();
if (r > 0) System.out.print("1 ");
for (int i = 0; i < m; i++) {
int d = 1 << i;
sb.append(d);
if (i < m - 1) sb.append(' ');
}
System.out.println(sb.toString());
long base = (1L << m) - 1 - r;
char[] d = new char[]{'L', 'D', 'U', 'R'};
for (int i = 0; i < N; i++) {
sb.setLength(0);
if (r > 0) sb.append('R');
long uu = (ui + base) / 2; long vv = (vi + base) / 2; for (int j = 0; j < m; j++) {
int u1 = (int) Math.abs(uu % 2);
int v1 = (int) Math.abs(vv % 2);
uu /= 2;
vv /= 2;
}
System.out.println(sb.toString());
}
}
}
感想
2進数を使うっぽいというところまで当たりはつけたけれど、それをどう腕の向きにエンコードするか思いつかなかった。とくに$ Xと$ Yにどう振り分けるか、と考えるのではなく$ (X+Y, X-Y)と座標変換するのは思いつきもしなかった。一方でkmjpさんの解答を見ると、上手な人はとりあえず2の累乗で腕の長さをそろえばいいだろうと考え、貪欲法で解いていたりして感心してしまう。