https://beta.atcoder.jp/contests/arc103/tasks/arc103_b
$N$個の座標が入力される。$m$個の腕と$m+1$個の関節からなるロボットアームの片方の端を座標$(0,0)$に設置するとき、$N$個の座標すべてにもう片方の端を重ねることができるようなロボットアームを構成することができるかどうか判定せよ。また、そのようなことが可能である場合にはすべての座標について各腕を曲げる方向（上下左右いずれか）を表した文字列を出力せよ。
座標系45°回転させるやつを使うと見通しがよくなる問題である。座標系を$(v,w)=(x+y,x-y)$とおくと、$v$座標と$w$座標について独立に考えることができるようになるので、すべての$v$座標、$w$座標について到達可能であるようなアームを構成できるか判定すればよい。その条件は、すべての$v$座標、$w$座標の偶奇が一致していることである（実際には$v$座標と$w$座標の偶奇は一致するので、$v$座標の偶奇だけ見ればよい）。
$v$座標と$w$座標は等価なので、以下$v$座標について考える。各腕の長さを$\{1,2,4,...,2^k \}$としたとき、到達可能な座標は各腕を正方向に向けるか負方向に向けるかを各bitに持った2進数として表すことができる。ただし、長さ$l$の腕を正方向に向けたときと負方向に向けたときの到達座標の差は$2l$であるから、実際には0bit目が0であるような2進数で表せるような座標（すべてのbitが0であるときの座標は負方向にすべての腕を伸ばしたときの座標なので、奇数の座標になることがわかる）にしか到達できない。長さ1の腕を１つ追加すれば偶数の座標に到達できるようになるが、その場合は奇数の座標には到達できない。
アームが構成可能であるとき、各座標に到達するような曲げ方は簡単にわかって、アームを長い順に見て目的の座標に近づく方向に曲げていくだけである。上下左右それぞれが$(v,w)=(\pm l,\pm l)$に対応しているので、出力すればよい。
実際にはこの問題には部分点が存在していて、本番中にはそれをすぐに拾ってE問題を見にいったので満点解法については考えていない。考えていたら解けていたような気もするし、解けなかったような気もする。