ARC 103 D - Robot Arms (600)

• 問題

解法

sample2をじっと見ると,必要条件として

• X_i, Y_i の和のパリティが全て一致する

というのがあることがわかる
パリティに注目するのはよくやるのでこれは気づかないとどうにもならない.

実際に,そのときdとして1を20個/21個用意すれば300点は取れる.
(例えば (-3,2) のとき LLLUU(UD)*8 )

このような構築ゲーで2冪に注目するのが定跡なことを念頭に置いて,
アームを 2⁰ , 2¹, 2² , ..と増やしていくことにしよう.
すると 2^k まで使ったときに, abs(x) + abs(y) <= 2^k+1 - 1 のひし形内の和が奇数の点を全て取れることがわかる.
abs(x),abs(y) < 2³⁰ - 1 だから, abs(x) + abs(y) < 2³¹ - 2 で k = 30としてやれば十分.
和がevenの時は 2⁰, 2⁰, 2¹, .. , 2³⁰ とすれば良い.
このようにすれば必ず構築できることもわかったので,列挙した必要条件が必要十分条件だったこともわかった.(よくあるパターン)

実際の構築に関しては 2^k のkが大きい方から決めていき,
abs(x+dx) + abs(y+dy) が0に近くなるようにしてやれば良い
そうしていけば最終的に(0,0)に一致することは上で確かめられている.

メモ

2冪は頭にあったけど実際に書いて見なかったのがよくなかった.

コード