[Java]ABC111-D(ARC103-B)
問題
ABCの方の
ARCの方のリンク
提出したやつ
多分30分以上考えてたけど分からなかったので素直にPDF見た。
考え方
- 1,2,4,8,...2^kのアームを持っているロボットは長いアームから上手く方向を選ぶことによって(x+y)=1(mod 2)かつ|x+y|<=sum(1+2+4+...+2^k)の点(x,y)に到達できる。
- (x+y)=0(mod 2)である点は最後に長さ1のアームを足して調整する。
くそムズイ...言われないと気付かないな。
色々紙で試した結果、このやり方だと多分1次元上の点(x)や3次元の点(x,y,z)に対しても(mod 2)が一致していれば到達できる気がする。
3次元で考えると分かりやすいが、1,2,4,...2^(k-1)までのアームを使って到達できる点を2^kの長さのアームを使って6方向(上下左右と手前と後ろ)にコピーしているように見える。
そのコピーの時に隙間が発生しないのは多分1+2+...2^(k-1)が2^k-1を満たすからだろうな。
他人の回答
見た限り上位の人は全員この1,2,4...の長さのアームを用意してるのでこれも典型問題と覚えた方が良いのか？
自分の回答ではU,D,L,Rを表すのにenum使ってその中でabstract関数書いて自分が混乱しないようにしてるがARCの全提出見たけど皆配列しか使ってない。(assert文使ってる人はいた)
そう書いたほうが早い気がするが今の自分がそう書けるかといわれると...
